脳log[20240525]

2024年05月25日 (土) [AtCoder] 今日は東京海上日動プログラミングコンテスト2024（AtCoder Beginner Contest 355）がなかった。いいね、そんなものはなかった。だから残念な結果も存在しない。少なくとも自分は確認していない。だけれども問題はあり、解けた問題もあるので、ふりかえりは行う。■A 問題「Who Ate the Cake?」。Ruby の配列は集合演算も行えて便利。■B 問題「Piano 2」。A 数列と B 数列をマージしてソートして、A 数列由来の要素が連続しているかどうか。愚直に線形探索をしても許される制約。どうとでもやる。■C 問題「Bingo 2」。１列が最大 2000 要素。縦横斜めが最大 4002 行(列)あり、それぞれに対して 2000 要素のスキャンを行ってもおよそ 800 万なので許される。ビンゴカードに何ターン目に呼ばれるかを書き込んで、行(列)ごとに最大値を読み取る。呼ばれない番号もあるので、それはテキトーに T より大きい値にする。Ruby で 800 万の処理はちょーーっと不安だったので、ターン数を知るのに Hash を使う代わりに Array を使うようにした。他所で読んだけども、制約がひと桁以上大きければ、ターンに沿ってビンゴゲームを進行し、ビンゴが成立したかどうかの判定を行列対角ごとに用意したカウンターで行うしかなかった。■D 問題「Intersecting Intervals」。タイムラインに沿って入りと出を管理して、現在を中に含んでいる区間の数を数える。数がわかれば組み合わせが数えられる。サンプルをよく読めば書いてあったけど、閉区間なのである値で隣り合っている２つの区間は共通部分を持つ。同時に起こる入りと出の処理順に注意する。■E 問題「Guess the Sum」。ABC349-D Divide Interval の記憶も新しいので(20240413)、今度はセグメント木をすぐにイメージすることができた。でも解けなかった。クエリ回数を最小化しないといけない。そのためには、与えられた区間を２冪に分割するか、もしくは、与えられた区間を内包する２冪から区間外を除くか、どちらを選ぶ場合も考えられる。それをうまく整理できなかった。散々悩んだ末にまずは DFS 関数を２つ書いた。１つは区間を受け取ってクエリ回数を数える関数で、もうひとつはクエリを実際に実行する関数。積み上げるのがいいか取り除くのがいいかは、２冪の幅を大きめと小さめの２種類特定して、再帰呼び出しでシミュレートして比較選択した。この２パターンでいいということが全然見えなかった。「整理できなかった」とはそういうこと。その結果、ひと通りの実装は済んでもデバッグの時間がとれないまま時間切れになった。穴あきになっていた PAST の問題(魚釣り)の精進をしてから(ふてくされてたんだよ)、コードの整理とデバッグをした。再帰関数はクエリ配列を返すもの１つだけに統合された(#53902777)。最短のクエリ配列を選んで最後にまとめて実際のクエリに変換する。クエリ配列を使うものも使われないものも区別せず生成破棄を繰り返すのは無駄が多いけど、それでも許される制約なのだから AC のためにはこだわっていられない。■F 問題「MST Query」。解けてないよ。MST というのは辺のコストの昇順に UnionFind をするやり方しか知らない。それでクエリに答えられるか考えてみたけどできなかった。辺のコストが 10 通りの値しかとらないところがクサい。つまり、コストの更新機会が限られるのではないか。グラフは最初は木で、クエリのたびに辺が増えて入り組んでいくけど、実は常に木の形を維持していていいのではないか。そして木を維持するのにちょっとばかしコストをかけても、総体としてコストの和は実行可能な範囲におさまるのではないか。新しい辺を追加しても木の形を維持するというのは、２頂点間のコスト最大の辺を特定して切断するということ。そんなの逐次的に効率的にできないよ。UnionFind の経路圧縮的な手抜き手段がないと、部分木のすべての頂点について親子関係を更新することになってやってられないよ。■自分のすべての提出。成績証は確認しません。■■■UnionFind を 10 個使うんだという解法の核心を某所 publish.obsidian.md/naoya/ で読んだので、それでどうやって答えが出せるのかをお風呂で考えてきた。UnionFind ではコスト１のグラフ、コスト１から２のグラフ、コスト１から３のグラフというような 10 種類のグラフを管理する。あとはまあ、やります。提出 #53927502 (AC / 576 Byte / 1512 ms)。当日は、コスト１のグラフ、コスト２のグラフみたいに分けることは考えていた。「それでクエリに答えられるか考えてみたけどできなかった」。あとちょっとが足りないんだよなあ。やるだけも門前払いも退屈なので、これはちょうどいい難易度。■AC を出したことなので安心してネタバレを読みに行ったら、「ABC355 振り返り」、なんか UnionFind の使い方が違う。Ruby の中ではひときわ速い fumta さんの提出 #53927847 が同じ解法だと思うんだけど、えー、わかりません。自分の解法は、最初に N-1 本の辺のコストの合計を記憶しておいて、新しい辺が採用されたらそのコスト w を足し、それまでに採用されていたが不要になった辺のコストを w+1..10 の範囲で探して引くというもの。単純明快でしょ。しかも、コスト１の辺を使うグラフ、コスト１から２の辺を使うグラフ、……という 10 種類のグラフを維持管理する処理と、辺を追加したことで不要になった辺のコストを特定する処理が一体となっているところが美しいと思うんだ。これは解答というより問題の力だとは思うけども。■■■E 問題。kotatsugame さんの動画(【競技プログラミング】ABC355【実況】)でグラフとしての見かたを知ったので、新規に実装して提出した>#53993734 (AC / 1045 Byte / 402 ms)。変数の取り違えで RE を出し、off-by-one エラーで WA を出し、デバッグ版を提出して WA を出したあとでの AC だった。やっぱり難しいね、この問題。ミスのしやすさも問題の難しさのうちだとすればね。やっていることは辺が陽に与えられないだけの BFS。グリッド問題みたいなもんだ。■C 問題。行や列をスキャンする O(N^2) 解が 455 ms (#53855978) だったところ、カウンターを使う O(T) 解が 132 ms (#53993977) だった。制約がちょっと変則的で、1≤T≤min(N^2,200000) かつ 2≤N≤2000 なので、T の上限が 20 万なのに対して N^2 の上限が 400 万。N^2 解を許容するためにあえて制約の桁を減らしていることが窺える。C 問題だしね。まんまと甘えさせてもらいました。