AtCoder Beginner Contest 119
昨日のABCはunratedだし朝7時から始まるので流石に参加はしなかったが、自分の実装力をあげるためにABCのCD問題を埋めていこうと思うので、まずは昨日のものを解いてみた。蟻本を読み進める予定だったが、今のところコンテストに出てもアルゴリズムを知らない問題にまで達することができないので、実装力の向上を優先することにした。
C問題は制約が小さいので全探索できるということが分かる。わかりやすい方法として使用する棒の集合をNビットで考えれば良いのだが、上手い探索の仕方が分からなくて2のN乘の3乘回（Nビットを3個全探索する）ループを回して条件を満たさないもの（3つの集合で同じ棒を選んでいる場合）を考えないという方法で行った。そんなこんなで実装に35分くらいかかってしまった。
想定解も本質的には同じだが、無駄にビットとかは使わずに幅優先探索で実現していた。コードとしては明らかに短くて効率的だが、僕のやり方のほうが直感的ではあると思う。
D問題はシンプルに二分探索をする問題で、スタート地点から左右それぞれで最も近いもの（寺か神社）を探す。左右それぞれについて、まだ行っていない方のもの（寺か神社）で一番近いものまでの距離を足す。それで最初に右が左に行った場合の短い方が答えになる。これで最短距離が求められることは簡単に証明できる。
右か左に何もないことがあるが、二分探索で近いものを求める場合には問題にならない。つまり、スタート地点の右に何もないときには神社か寺で一番右にあるものが返される（これは左に行ったときの一番近いものと一致する）。
Editorialを読んで知ったのだが、無知すぎて二分探索が標準ライブラリに入っていることを初めて知った。自分で実装したので上記の挙動になると分かるが、標準ライブラリのものだとどういう挙動になるのかは良く分からない。想定解だと適当に遠い位置に左右に寺と神社を作っていた。
想定解法も方針は同じだったが、pythonを使っていたのでずるい。僕は二分探索はともかくとして左右に行ってから左右に行くという部分のコーディングに時間をかけてしまった。僕の方法が効率悪すぎるのはともかくとして、pythonなら確かに楽にかけるなと思った。しかしpythonがどれくらいの時間で回るのか感覚的に分からないので怖くて使えない。
Dは45分くらいかかった。
CDで80分かかっているので、実際にABCに参加していたら全完できたか怪しい。CもDも解法はすぐに分かったが実装にはそれなりに時間がかかってしまった。想定解と方針は同じような感じだったので、想定解ほどではなくても、もう少し効率良くかけるようになりたい。
