第四回日本最強プログラマー学生選手権-予選-(AtCoder Beginner Contest 313)
まとめ
ABCの3完。
事前に宣言されていた通り、問題がかなり難しかった。
よくなかった
A, B 問題をそれぞれ難しく捉えすぎたところがあるか。時間をかけすぎてしまった。
Cは解けたけど、未証明で直感的にいけるやろ、みたいな投げ方でACした。
よかった
前回に続いてノーペナだった。
Dは解けなかったけど、たくさん考察をして実装に起こすことができた。
問題ごとの感想
✅ A - To Be Saikyo
タイブレークに気をつけて実装する。
1人目だけじゃなくて全員分の出力が必要だと誤読してしまって時間をかけてしまった。
✅ B - Who is Saikyo?
有向グラフと見立ててDFSで解いた。
1 2 みたいな辺は 2 -> 1 の辺と見なす。そうすると、最終的に最強候補にたどり着く感じのグラフになる。
全員から辿って、最強候補が1人しかいないならそれを出力、そうでないなら -1 とした。
✅ C - Approximate Equalization 2
平均値 と 平均値 + 1 だけの数列を作ることになるだろう、というのは直感で想定。
平均値を avg として、 Ai < avg なら avg になるまで加算、 Ai > avg + 1 なら avg + 1 になるまで減算するのが最も無駄がなさそうに見えたのでそんな感じに実装する。
最終的な加算回数と減算回数が一致するとは限らないのだけど、どっちか大きい方を採択して操作回数と決め打ってしまえば良いのでは?ということでそうした。サンプルがあったので、深く考えずに提出してACだった。
❌ D - Odd or Even
色々実験したのだけど、 Kが奇数 なのでクエリ結果から特定の値を判断することはできそうに見える。
❌ E - Duplicate
Dが解けないのでチラ見したけど、難しそうなのでDに戻った。
板書