ABC201の感想
マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）に参加したのでその感想を書いてきます。
問題はこちらから。
結果はこんな感じでした。
ABCD(88:48+1WA)
順位：1342 / 8739
パフォーマンス：1333
飛びぬけてできたわけでもなく、ダメダメだったわけでもなくという感じです。しかし、個人的には「ゲームの勝敗」のD問題が解けてとっても満足しております。何度かこの形式の問題には出会ってますが、今まで全く手が出ませんでした。今回、ボロボロになりながらもコンテストで通せて本当に嬉しいです。ACしたとき変な声が出ました。
感想です。
A問題
順列を判定する問題です。はじめ
即ち、A3−A2=A2−A1を満たすようにAを並び替えることはできますか？
この部分を先に読んでしまい、逆に混乱しました。a1,a2,a3を入れ替えて全てのパターンを試せばいいのかな？などと考えていました。もう一度問題文を落ち着いて読んだところ、長さ3の等差順列の判定をすればよいことに気が付きました。
ですので、配列に要素を入れまして、ソートをし上記式を試せばおしまいです。
A問題でしたがなかなか焦りました。
B問題
2番目の大きさの山の名前を出力する問題です。この手の問題はちょくちょく見ます。過去問だとたしか3要素のソートがあったような気がします。
今回は名前と高さの２要素です。pairに両方を入れて、高さで降順ソートをして2番目の要素をとりだしておしまいです。
C問題
暗号をパターンを試す問題です。
制約をみて解法はぱっと浮かびました。
4桁の数ですので、0000から9999までを全部試します。このとき、
確実に含まれる数が 1 個でも抜けてたらダメ
確実に含まれない数が 1 個でも入ってたらダメ
で判定ができます。
ただ、判定を文字列のfindでやっていたため、なかなか答えが合わずに苦戦しました。調べてみると
見つかればその位置を返し、見つからない場合は basic_string::npos を返す。
らしいです。よくわからないものを使うのは良くないですね。そのため、for文を追加で回して判定しました。とはいってもやることは上の通りなので分かってしまえば何とかなります。
これで無事ACでした。
D問題
ゲームの問題です。今までは解き方が良くわかってなかったのですが、最近学びました。こういうのは後ろから考えるといいらしいです。
ということで、高橋君の得点を正、青木君の得点を負として
その場所から最適に行動すると何点獲得できるか
というdpで解くことを考えました。このdpを後ろから前に（h-1,w-1から0,0に向かって）解くと答えが求まります。
各手番の盤面の座標の偶数奇数で判断できますので、その辺は探索しながら計算しました。手番が高橋君の時にはその遷移先の2つの値の大きいほうに遷移することになります。逆に青木君の時にはより小さいほうに遷移することになります。
この辺がゲーム問題の「最適な行動」につながってくるのですが、この考え方が最近ようやくわかるようになりました。
このまま、実装をしてACとなれば嬉しいのですが、そうもいきませんでした。まず、dpの各状態に自分のマスの情報も含めて考えていました。そうすると、0,0の値も遷移に含まれるのでなんかおかしいな、となり変更。今思えば、あとから引けばこれでも良かったのかもしれません。
次に、+と-の扱いがこんがらがりました。高橋君の手番の時には遷移先の+,-の通りに得点が変化し、青木君の番にはその逆となります。ただし、それは遷移前の座標により決定される手番です。ここを間違えてました。（0,0から移動するのは高橋君なので0,1か1,0の+,-は 0,0 の手番）
この辺を直して、何とかACでした。途中、こんがらがりすぎてよくわからないまま出して１WAを貰いましたがまあ良しとしましょう。
E問題
5分ぐらい考えましたが時間切れでした。
F問題
見てないです。
あとがき
今回はD問題が解けたのがとっても大きな収穫でした。何と言いますか、レート以上に成長が感じられました。レートも大切ですが、こういうところで成長を感じながら取り組むのがとっても大切な気がしています。
ただ、解けたものの情報を整理するのに１時間ぐらいかかってしまいました。1回成功体験ができましたので、速く正確に実装することを次のステップの目標にして取り組んでいきます。
ただ、正直言いますとこんなに解く方がいることに驚いています。難しくなかったですか？ぼくはボロボロになりながらなんとかACという感じでしたが、1400人ほど解かれていて、ホントですか？ってなりました。
また、今回も解説を書くつもりです。時間がかかってしまうかもしれませんがもし興味のある方がいらっしゃいましたら、のんびりとお持ちいただけると幸いです。
この記事が気に入ったらサポートをしてみませんか？