2025年08月02日 (土)[AtCoder] 今日は AtCoder Beginner Contest 417 があった。D 問題が難しすぎる。30 分以上かけて AC に至れなかったので捨てて E、F に行った。得点に至らない時間消費は得られたはずのパフォーマンスを下げるムーブ。■A 問題 A Substring。出力する文字数が問題文に書かれてるの親切。最初の文字のインデックスが 0 始まりで A であることを確認したら、書いてある通りに。■B 問題 Search and Delete。どうやっても通る制約ではあるけども、ソートして NlogN で。Hash を使うと定数倍は重いけどオーダーはさらに良くなるのかな。■C 問題 Distance Indicators。苦手な部類だけど式が直で問題文に書いてあるのであればさすがに式で考える。必要なものをカウントしながら数え上げるのだけど、ポイントは i と A_i、j と A_j を等式の左右に分けること。値と添字を足し引きしたものは位置(添字)から独立した指標になる。■E 問題 A Path in A Dictionary。小さい頂点番号を優先して深さ優先探索でパスを見つける。再帰関数で実装していて TLE を出している人は訪問済みフラグをクリアしているのが原因ではないかと思う。過去にゴールに至れなかった頂点にあとから再訪して、良い結果が出ることがあるのかどうか。スタックで実装すると再帰関数では出さない TLE を出すことがあって、これは隣接頂点リストを何度も先頭からスキャンさせられることで出る。スタックに保存する状態を (頂点番号, 隣接頂点リストの位置) のペアにする。自分はスタックで実装して隣接頂点リストを破壊的に消費した。■F 問題 Random Gathering。20241218 で実装した遅延セグメント木をコピペするだけ。３秒制限のところ 2984 ms で通ったのはめでたいようで気持ちは虚無だ。ABC だから基礎知識の確認という意味はあるかもしれない。でもなあ。■D 問題 Takahashi's Expectation。まず問題設定が難しい。高いテンションはさらに高く、低いテンションはさらに低くなるようなイメージで長らくいたけど、実は逆で、高いテンションは下がりやすく低いテンションは上がりやすい。その交差部分をうまくマージしたいが、愚直 TLE 解を終了３分前に提出するのが精一杯だった。全部で１時間近く費やしてこれ。クエリの大きさははったりだなと思ったけど、クエリの数もそうなんかな。