脳log[20231118]

2023年11月18日 (土) [AtCoder] 今日はＳｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329）があった。自分のすべての提出。コンテスト成績証。ABCDF の５完で低め安定といった成績。E 問題がおもしろかった。そしておもしろい問題にはやられてしまう。ABC って基本的に筋トレだと思うんだよね。反復練習であり、反射神経とタイプ速度を競っている。どの問題までがそうかというのは人それぞれだけど、自分の場合は D 問題までは常にそう(本当に？)。E、F 問題はどちらとも言えなくて、だけど解けるものは典型度が高め。だから昨日の E 問題みたいなのにはやられる。ではふりかえりと精進を。■A 問題「Spread」。はい。■B 問題「Next」。罠がありますね。最大値が複数あるときに１位タイの値を２番目の数として出力してはいけない。サンプルがちゃんと仕事をしていたので罠ではあるけどひっかけではない。■C 問題「Count xxx」。14 分かけました。ループで書くことはできるし、各アルファベットごとに単純化した問題を解くこともできる。でも書きたくないと思ってしまった。String#scan メソッドだとか /(.)\1*/ みたいな正規表現パターンでうまくできないかとあれこれ考えて、できなかった。同じ文字の繰り返しを意味するパターンって難しくない？ キャプチャを使うとできるけどそうすると String#scan メソッドが役立たずになるので困ってしまった。■D 問題「Election Quick Report」。D 問題で BIT とかプライオリティキューとか使いたくないよね。考えました。最高得票者が入れ替わる瞬間がつかまえられさえすればいいので、誰が最高得票者で得票がいくつかがわかればそれでいい。■E 問題は解けなかったのでひとまずとばして F 問題「Colored Ball」。ただのマージテク。考える時間も書く時間もいらない。E 問題を考えていたせいで F 問題の AC が 30 分近く遅れたのを挽回するためには、最終的に E 問題も通すほかなかったんだけど、結果はあのとおり。残念無念。■■■E 問題「Stamp」。難しかったよね。時間内のこの提出 #47726211 (WA×5) だけど、19 行目が嘘貪欲なのはわかっていて、でも残り数分で新しい方針をでっちあげることもそれを実装することもできない。昨日はもうお手上げだった(あ、この日記は翌日に書いています)。■提出 #47752502 (AC / 515 Byte / 393 ms)。これは翌日の今日なんとなく転がしていたアイディアを実装したもの。貪欲なのは同じ。違うのは起点が複数あること。昨日は左右端を起点にしてスタンプを上から押したり下に差し込んだりする操作を考えていた。今日は T と完全一致するすべての場所を起点にして、そこから(端でなければ)左右にスタンプを繰り返し差し込む操作を考えた。操作の起点を複数考えることでスタンプを上から押す操作を考えなくて済んだのが昨日との違い。複数の可能性を考えなくてよくなり貪欲法がはまるようになった。最終行の判定がやや複雑で条件が３つある。両端の条件に２つで、貪欲法と貪欲法の狭間に残る部分の判定に１つ。■たしかに D 問題とのあいだで配点はひらいているけども、これを E 問題に配置しようって判断が、それもあの F 問題の前に配置しようって判断が謎すぎる。でも考えるのが楽しい問題だった。知識問題というよりのーみそこねこね(コンパイル)な問題だったのでは。