脳log[20250802]

2025年08月02日 (土) [AtCoder] 今日は AtCoder Beginner Contest 417 があった。D 問題が難しすぎる。30 分以上かけて AC に至れなかったので捨てて E、F に行った。得点に至らない時間消費は得られたはずのパフォーマンスを下げるムーブ。時間をかけていいのは解けるか解けないかの最後の１問だけ。■A 問題 A Substring。出力する文字数が問題文に書かれてるの親切。最初の文字のインデックスが 0 始まりで A であることを確認したら、書いてある通りに。■B 問題 Search and Delete。どうやっても通る制約ではあるけども、ソートして NlogN で。A 数列が広義単調増加なのに B 数列がソートされていないなんて思いませんでした(サンプルが合わなくてデバッグした)。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 解を終了３分前に提出するのが精一杯だった。全部で１時間近く費やしてこれ。クエリの大きさははったりだなと思ったけど、クエリの数もそうなんかな。■■■遅延セグメント木の扱いについてコメントを書いた。提出 #68173358。自分はこういうのはパクリパクられで良いと思ったものをどんどん取り入れて手を入れていけばいいと思ってるんだけど、思ってるだけではどうにもならないわけで。ac-library-rb のような形が一番いいのだろうと思う。AtCoder では前回の言語アップデートからだったか require するだけで利用できるようになっている。遅延セグメント木に関しては制限時間のせいで貼るだけやるだけとはいかないらしいのが、AtCoder における Ruby の立場を弱くしている。■セグメント木に関して prod という用語が自分はわからないんだよね(調べない)。id という名前も同じようにわからなかったんだけど、昨日 ac-library-rb/lib/lazy_segtree.rb での使われ方を読んでいてわかった気がする。IX = XI = X であるような行列 I を単位行列と呼ぶはずだけど、I がたぶん Identity の頭文字。英語では習わなかったけども。ということは、id の名前で返すべきは何の作用ももたらさない操作なのかなと。e と id の区別が難しかったんだよね。最大値を求める操作に対しての負の無限大、最小値を求める操作に対しての正の無限大、数を数える操作に対してのゼロみたいな、初期値としての e とは別に用意される id という「値」はなんだろう、というのが疑問だった。物理的な形式はともかくとして概念としての id は操作ですよね？ ということを納得すると、自分の実装で Op#nop? の名前を与えられている機能は Op#id? が相応しかったんじゃないかなあと思ったり。■コンテスト中の提出 #68152111 (AC / 1796 Byte / 2984 ms) と冒頭にコメントを付加しただけの提出 #68173358 (AC / 2433 Byte / 2596 ms)。ジャッジサーバーが使い回しではなく新規立ち上げだから１ケース目だけ 100 ms 余計にかかってる、みたいな話ではなく、全体的に１割程度の時間差がついている。再提出で 100 ms も差がつくことはないだろうと思っていたから意外に大きな差に驚いている。こんなんではコンテスト中に TLE だったものが終了後の再提出では AC になった、みたいなことが十分に起こりうる。特に遅延セグメント木と３乗の DP が解法となる問題ではシビアな定数倍低減が AC と TLE を分けるのでしゃれにならないよ。■■■@2025-08-07 精進。D 問題。提出 #68259724 (AC / 471 Byte / 1172 ms)。コメントに書いたけど「ひとたびテンションが 0..1000 の範囲に入ったら抜け出せない」ことが見抜けるかどうか。見抜けたらその範囲で DP をする。自分は見抜けなかったので 0..500 の範囲＋それ以上という括りでクエリ全体を一括シミュレートしてサンプルしか通らなかった (TLE×27/AC×3)。さらにもうひとつどこ以降の DP 結果を参照するかを決めるのに二分探索をする必要もあったらしい。すべてのネタバレ後に実装をした。実装だけなら D 問題だったけど考察ポイントが２つもあると問題を総合的に理解していないと解けない。断片的な手がかりからあれかなこれかなというアプローチでは解けない。「クエリの大きさははったりだなと思ったけど、クエリの数もそうなんかな」と先に書いていた。大きすぎるクエリには二分探索で対応する。(シミュレートするには)多すぎるクエリは 1001 種類の入力にだけ対応した DP で予め答えを出しておく。それでいいそれでできるという判断に必要だったのが「ひとたびテンションが 0..1000 の範囲に入ったら抜け出せない」という洞察。ありませんでした。