水色コーダーになるための100問をしばく（1/3）
最近、実生活のほうでかなり実力不足を痛感して悔しい思いをしまして、「この思いをどのように晴らしてくれようか」と煮えくり返っていたところ、以下の様な素晴らしい記事が目につきました。
この中に『初中級者が解くべき過去問精選100問』という章があり、AtCoderで水色コーダーになるのに適切な教育的良問が100問挙げられています。また、100問全部解けたら青色コーダーくらいの実力が付く、との言及もあります。
1年弱水色コーダーで定着してしまっている私ですが、どうにか青になりたいと思っていましたし、一方で基本的な部分が抜け落ちているような気もしていました。
ということで、悔しさをエネルギーにこの100問をしばき倒すことで、精神の解放と青色になるための基礎力を手に入れてやろうと決意しました。
で、いざやってみると100問解くというのは想像以上に大変でした。。。
金曜の夜からやっていますが、ようやく三分の一が終わったところです。（実際は解けずにスキップしているものもあるのでほんとは三分の一も終わっていない。）
当初はこの3連休で全部終わらせるつもりでしたが、主に体力的に厳しそうなので、三連休後も少しずつでもしばいていこうと思っています。
問題を解いた後に1行ずつくらい感想を書き留めているので、それを記録代わりに記載しておきます。（これも当初は100問分一気にブログにするつもりでしたが、3回くらいに分けることにしました。挫折に次ぐ挫折。）
各問題の感想
全探索：全列挙
1 ITP1_7_B - How Many Ways?
さすがに基本的過ぎて飛ばすか悩んだけど、選ばず全部やる！ってことでやってみたらなれない形式のINPUT/OUTPUTでちょっとつまずいた。
幸先の悪いスタート。
2 AtCoder Beginner Contest 106 B - 105
AC済み。
200点にしてはちょっと難しそうな見た目だけど結局全列挙なので。
3 AtCoder Beginner Contest 122 B - ATCoder
AC済み。
苦手な文字列。最後にtmpが暫定解より大きい時に代入するのを忘れて１WA。
4 パ研杯2019 C - カラオケ
全探索、全列挙の問題として見ていなかったらDPとか余計なこと考えていたかもしれない。
落ち着いて制約を見てN*M^2の3重ループで行けることをすぐに見抜く。
全探索：工夫して通り数を減らす全列挙
5 AtCoder Beginner Contest 095 C - Half and Half
AC済み。
以前ACした時とかなりコードが一致していた。成長していない。。？
6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
AC済み。
以前ACした時に比べてStringクラスのindexOf(str, fromIndex)メソッドを利用するなどしてスッキリかけた。成長している。
★7 JOI 2007 本選 3 - 最古の遺跡
TLEするのでスキップ
8 Square869120Contest #6 B - AtCoder Markets
何とかAC。難しい。勉強になる。
N個の数a1,a2,…aNについて|x-a1|+|x-a1|+...+|x-aN|が最小となるxは「a1,a2,...,aNの中央値」
★9 JOI 2008 予選 4 - 星座探し
見た目的に無理なのでスキップ
全探索：ビット全探索
10 ALDS_5_A - 総当たり
bit全探索だといわれているのに最初なぜかDPやろうとしてた。
11 AtCoder Beginner Contest 128 C - Switches
AC済み。
以前より少しだけスッキリかけていた。
12 AtCoder Beginner Contest 002 D - 派閥
最大クリーク問題というNP困難な問題らしい。
13 JOI 2008 予選 5 - おせんべい
実行制限時間10secってどのくらいの計算量まで許容されるかわかんねーと思いながらひとまず提出したら417msで全然余裕だった。
bit全探索だけでなく、論理和と排他的論理和も普通に使えるようになってて、競プロはじめてbit演算耐性がついたなと実感。
14 Square869120Contest #4 B - Buildings are Colorful!
オーバーフローで１WA。入力で10^9とかあったら迷わずlongを使いなさい。
全探索：順列全探索
★15 AtCoder Beginner Contest 145 C - Average Length
未参加ABCで今後バチャをやる可能性があるのでスキップ
16 AtCoder Beginner Contest 150 C - Count Order
AC済み。
結構最近やったやつなのにどうするか迷った。順列全探索苦手っぽい。
17 ALDS_13_A - 8 クイーン問題
見た瞬間無理と思ったけど愚直にDFSで全探索して通した。これも順列全探索と扱うのか？
二分探索
18 ALDS_4_B - 二分探索
シンプルすぎて逆にOKとNGの判定をどうすべきか悩んだ。
★19 JOI 2009 本選 2 - ピザ
MLEが取れずスキップ。
20 AtCoder Beginner Contest 077 C - Snuke Festival
AC済み(2回)
二分探索に持っていくことができれば、あとはただの二分探索。
リンクミスがあったっぽくARC037C億マス計算を↑の先にAC。（この問題はAC済み。最近これと似たような二分探索の中で二分探索するような問題がABC出会った気がする）
21 AtCoder Beginner Contest 023 D - 射撃王
AC済み。
問題文が「最大値の最小化」という二分探索典型パターンを醸し出そうとしていて変な問題文になっている気がする。
intとlongで行き来するのが苦手。というかそもそもやらないようにすべきな気がするがどうした良いものか。
22 AtCoder Regular Contest 050 B - ムーアの法則
解説AC。
できなくて色々ググった結果、三分探索を習得した。
★23 JOI 2008 本選 5 - ダーツ
分からなすぎるのでスキップ
深さ優先探索
24 ALDS_11_B - 深さ優先探索
純度100%のDFS
25 AOJ 1160 - 島はいくつある？
何かもう少しいい感じにできそうな気がするけど、とりあえず愚直に。
26 AtCoder Beginner Contest 138 D - Ki
AC済み
imos法をDFSでやる感じ。
27 JOI 2009 予選 4 - 薄氷渡り
DFSやるだけ。
幅優先探索
28 ALDS_11_C - 幅優先探索
普段ほとんど幅優先探索やることないので慣れてなくて手間取る。
29 AtCoder Beginner Contest 007 C - 幅優先探索
普段ほとんど幅優先探索やることないので慣れてなくて手間取る。
問題名で解法をお知らせしていて、かなりビギナー向けだと感じた。
30 JOI 2011 予選 5 - チーズ
幅優先探索を複数回。
31 JOI 2012 予選 5 - イルミネーション
BFSで外側から行けるところを判定した後、外から行けるところと行けないところの接点の数を数える。
四角が並んだ普通のグリッドでなく正六角形なため、各ブロックの隣接を列挙するのが少し悩む。
32 AOJ 1166 - 迷図と命ず
ブロック間に壁があるので、行けるいけないの判定に少し工夫が必要。各ブロックから行ける方向をbitで管理した。
33 AtCoder Beginner Contest 088 D - Grid Repainting
BFS自体はシンプルで、最短経路を見つければよいことに気づければ勝ち。
BFSに全然慣れていなかったけど、これで結構慣れた気がする。（というかどれも実装がかなり似ていて、ノイローゼになりそうだった。。）
残り、67問。最後までやり通せるかなこれ。
