notepad.exe

つまり覚え書き

ABC112参加記録

久々にABCで全完できた回でした。 今回は練習もかねて初めてRubyで出ました。

A - Programming Education

問題ページ

1行だけ受け取って分岐して出力するだけの問題。

提出コード

B - Time Limit Exceeded

問題ページ

時間T以内に帰れる方法でコストが最小なものを出力する問題。
入力[c, t]のペアでリストをもってT以下でフィルターをかけます。 残ったリストの中にあるcの最小値を出力して、 フィルターをかけた時にリストの長さが０であればその時はTLEを出力して完成。

提出コード

C - Pyramid

問題ページ

ピラミッドの高さと中心座標を求める問題。
中心座標は101*101個なので全探索できます。 各候補座標に対して仮の高さを一度計算してその高さとしたときに与えられているすべての座標に矛盾がないか調べます。 矛盾がないか調べるときに候補座標から十分に距離が遠いもの（本来は高さがマイナスになるもの）を都度除外してから矛盾のチェックをしないとWAになってしまうので、その点で苦労しました。

提出コード

D - Partition

問題ページ

N個の整数の和が Mになるときにそれらの整数の最大公約数の最大値を求める問題。 a_iが kの倍数であるとき Mも kの倍数であるので、 kの候補は Mの約数となります。
kが Mの約数であるとき、 N \leq \frac{M}{k}であれば問題の制約を満たせるので、約数を全探索すれば答えを見つけられます。約数の片方は必ず \sqrt{M}以下であるので1から \sqrt{M}までループすれば十分間に合います。
答えの候補ですが、 kが Mの約数であるとき M/kも答えの候補になりうることがあるので、それを忘れるとWAになります。

提出コード

Future Meets You Contest、ARC103/ABC111 参加記録

同日に開催されたのでまとめて書きます

Future Meets You Contest (ふみこん)

サイトページ

オンサイトにて参加しました。

マラソン形式のコンテストに参加するのは今回が初めてでした。そもそもマラソン形式をやるのが初めてだったので事前準備としてChokudai Contest 001だけ試しに解いて参加しました。

まず簡単な感想を述べると、アルゴリズムとは考えるべきことが違っているように感じてしまい、だいぶ苦戦しました。コンテストが始まる前までは0点を取ってしまうのではないかという不安があり、緊張してしまいましたが、本番では何とか点数を取ることができました。
通したのは適当な貪欲をランダムにした程度のものなので点数はあまり高くないですが、マラソン形式の感覚を感じることができたのよい経験になったと思います。

コンテスト終了後には懇親会と面談にも参加しました。懇親会では何度かお会いしたことある方や初めてのお会いする方含め、楽しくお話をさせていただきました。面談ではフューチャー(株)様での想定なオファー金額を提示していただけるもので(詳細は割愛します)、自社以外での一つの目線を感じることができたのでとても素晴らしい機会でした。

今回の企画をしていただいた、つかもさん、当日のスタッフをしていた社員の皆様、本当にありがとうございました。

ABC111/ARC103

サイトページ

こちらは言えることは何もないです。そもそも自分の参加記録を見ていたらRatedに参加したのが約1か月半ぶり、リアルタイムのコンテストに参加したのが約1か月ぶりとサボっていたのがバレバレで、結果もその通りになりました。

今回の問題は問題に対する考察はある程度あっていたものの実装がうまくいかず正解をすることができなかったパターンでした。

本当に言うことが何もないので、とにかく精進の流れを取り戻します。

Elmハンズオンに参加しました

こちらのイベントに参加しました

elm-jp.connpass.com

やったこと

こちらのスライドをなぞりながら実際にElmのコードを書きました https://gitpitch.com/ababup1192/elm-handson2

ハンズオンの後半では、同スライド内にある「Incremental Search」を自分で考えながら実装しました。 時間は1時間ほどだったのですが、発展問題の実装まで終わるには至りませんでした。ただ基本問題まではすんなりと実装することができたのでよかったと思います。(15分か20分くらい？)

ハンズオン後には4名の方によるLTを聞きました。
なんど一名スペシャルゲストで外国から来た方(!!)がLTをしていました。

やってみた感想

ハンズオン前

  • elmは5分くらいちらっと見た程度
  • 実際にコードは全然書いてない
  • なんかわかりにくいなと思ってた

ハンズオン後

  • 実際に説明を聞きながらコードを書いていたのですんなりと理解できた
  • 分かりにくいと思っていたものが実際に書いてるときに見るとむしろわかりやすかった
  • コード自体も本当に必要なものだけ書くのですっきりとしたコードにすることができた

この3つの中でも説明を聞きながらコードを書くというのが一番自分のElmに対する理解を深める手助けになりました。 (ハンズオンなので当然といえば当然ですが…)

Elmそのものについてもドキュメントを見てもわかる通り覚えるべきことが少なく、むしろプログラム初心者に向いているような気がしました。かといって必要なものがないかと言われるとそうでもなく、（少なくとも今自分が書いている段階での認識ですが）洗練された言語である印象を受けました。

LTについて

LTの内容はそれぞれ以下の通りでした。

どれも内容は素晴らしかったです。全員に言えることですが、本当にElmが好きなんだなという気持ちが伝わってきました。

最後に

Elmは本当に書き始めたばかりなので、もう少しコードを書いて理解度を深めます。 少しだけ書いた程度ですが、とても書きやすいので楽しくWebアプリの作成ができそうです。

スライドにも書かれていることですが、もう一つ。 Webアプリを作るよりによくあると思われることですが、コンポーネントが増えたり、ページが増えたりすると、だんだん破綻してきてひどいコードになってしまうという問題があります。これはどのフロントエンドのフレームワークを触っていても気になる所です。また、実際の業務でも苦労する所です。この問題をElmではどのように解決するのかを、実際に書きながら理解することでElmの真の力を見極めていきたいです。

本日のハンズオンを企画、運営いただいたABAB↑↓BAさん、ありがとうございました！！

windowsでもかっこいいCUI環境を作りたかった

Windowsのコマンドプロンプトってよくわからないですよね？ だからと言ってbash on Windowsインストールしても結局ウィンドウはWindowsのものなのでダサいですよね？

どうせなら少しでもかっこよくしようということで環境を作ったのでメモ

まずはbashを入れる

こちらの記事を参考にbashをwindowsで使えるようにします。 これだけでbashは使えるようになるのでlsコマンドとかが使えるようになります。

Cドライブは /mnt/cにマウントされている状態なのでwindowsのファイルシステムで管理されているファイルも普通にアクセスできます。

見た目をどうにかする

一番重要な見た目ですがcmderという素晴らしいソフトウェアがあるのでこれをダウンロードして使います。 初期状態だとcmd.exeが上がるようになってるのでbashが上がるようにします。

ついでに全画面にしたときに余計な部分が消えるように設定すると見た目をだいぶかっこよくできます。 設定方法はこちらのサイト

あとはzshにしたりtmuxいれたり

このあたりを見ながらbashではなくzshにしてtmuxとか入れると楽しくなります

(スクショはまだまだカスタム中なので省略)

ARC098/ABC098 D - Xor Sum 2

復習日記

問題ページ

問題概要

  • 長さ Nの整数列 Aが与えられる
  • A_l xor A_{l+1} xor ... xor A_r = A_l + A_{l+1} + ... + A_rを満たす (l, r)の組の個数を求める

考え方

サンプルを見てみると、

  • 2 = 0 0 1 0
  • 5 = 0 1 0 1
  • 4 = 0 1 0 0
  • 6 = 0 1 1 0

となっていて、 (l, r) = (1, 2)の時にちょうど1の位置がお互いに干渉していないことがわかります。 例えば、1がどこかの桁に2つ以上あるときに xorをとると0になってしまいますが、加算をすると繰り上がって1の位置がずれてしまいます。
ということは、区間のすべての桁について1の個数が1個または0個になるような区間を求めれば答えを求めることができることがわかります。

というのが解説にもありますが、区間を尺取りで実際に計算しながら求めれば答えを求めるのには十分です。

提出コード

数える実装が上手くきれいに書けなくてサンプルがなかなか通らなかったです。 結局右側を順番に回して左側を詰めていく実装に落ち着きました。 あとほかの人の実装が頭よかったので参考にしました。

ABC109参加してない記録

本番は参加できませんでしたが解いてみた感じで書きます

A - ABC333

A * B * Cが奇数になるCが存在するか確かめる問題

偶数に何をかけても偶数なので A * Bが偶数かどうかで判定

提出コード

B - Shiritori

しりとりが正しいか判定する問題

これは本当にやるだけ。出現済みかどうかはHashSet等で管理すれば楽だと思います。

提出コード

C

すべての都市を訪れることが可能な最大の移動距離を求める問題

Dずつ移動するので移動距離は Dの倍数になります。 i番目と j番目の都市を移動するときの距離が必ず Dの倍数でないといけないので、 逆を言うとすべての都市の Xからの距離が Dの倍数であればどの順番であってもちょうどたどりつくことができます。
以上のことから、すべての都市の座標のXからの距離の最大公約数を求めると以上の条件に当てはまる最大の移動距離を求めることができることがわかります。

提出コード

D

指定された操作を行いコインが偶数枚置かれたマスを最大化する問題

マス目上の全てのコインを足したときに偶数枚であれば何らかの操作ですべてのマスのコインのマスを偶数枚にすることができると予想できます。 また、奇数枚であればどこか1か所を除いて偶数枚にすることができると予想できます。 ということはどこか一か所に向かってコインを集めるような操作をすればうまく偶数枚にすることができそうです。
実装として簡単なのは全体を横に移動してから端の縦を下に移動させる方法だと思います。

提出コード

ARC101/ABC107 D - Median of Medians

復習日記

解説その他諸々を見ながらやっていきます。

問題ページ

問題概要

  • 長さ Mの数列を昇順に並べたときの \frac{M}{2} + 1番目の要素の値を中央値とする
  • 長さNの数列の各 (l, r) (1 \leq l \leq r \leq N)について \{ a_{l}, a_{l+1}, ..., a_{r} \}の中央値を m_{l,r}と置く
  • すべての (l, r)に対しての m_{l,r}を集めた数列を作り、その数列の中央値を求める

考え方

まず、中央値について考え方を整理します。問題概要には中央値の定義は、

長さ Mの数列を昇順に並べたときの \frac{M}{2} + 1番目の要素の値を中央値とする

と書かれていますが、これを言い換えると、長さ Mの整数列 bの中央値を xとしたときに、

  • bの中に x以上の要素が \lceil \frac{M}{2} \rceil個以上含まれる xの中で最大の整数

であるといえます。
この「条件 Pを満たすものの中で最大のもの」という考え方に注目すると二分探索で解くことができることがわかります。
これは連続部分列の中央値 m_{l,r}を並べた数列にも同様のことが言えて、最終的にこの問題は、

  • m_{l,r} (1 \leq l \leq r \leq N) のうち x以上の要素は何個か？

という質問に置き換えることができます。
ここで m_{l,r} (1 \leq l \leq r \leq N)について言及するように言い換えると、

  • a の連続部分列 a[l, r] (1 \leq l \leq r \leq N) のうち， x 以上の要素を \lceil \frac{r−l+1}{2}\rceil個以上含むものは何通りか？

という質問になります。

次に、この質問に対してどのような解法をとるかを考えます。
毎回数えてしまうと計算量が多く間に合いません。そこで xより大きい数を1、 xより小さい数を-1に置き換えて累積和を取ります。 そうするとその区間の累積和が0以上であれば xより大きい数の個数が過半数であるということがわかります。
さらに言えば、 1から Mまでの累積和を取っておけば、

  • m_{l,r} (1 \leq l \leq r \leq N) = m_{1,r} - m_{1,l}

と計算をすることで求めることができます。

最後に、区間の累積和が0以上である区間の個数を求める方法ですが、 S_i = \sum_{j=1}^{i}{a_{i}}としたときに、

  • S_i \leq S_j (i \lt j)である (i, j)の組み合わせの個数

と言い換えることができます。これは反転数を求めるアルゴリズムを使うと高速に求めることができます。 反転数のアルゴリズムについては蟻本のp162または螺旋本のp175に載っています。

提出コード(諸々を写経)

かなり難しい700点ですね…
これを時間内に解くだけパフォーマンスが2000を超えるので、目標にしたいところです。