脳log[20210616] 競プロ典型 90 問／068 - Paired Information（★5）

最終更新: 2021-06-21T21:06+0900

♪ [AtCoder]競プロ典型 90 問／068 - Paired Information（★5）

すごく難しいです。答えの出し方に確証が持てないまま、とりあえずグラフとして解答を書いた。クエリ０に応じて辺を追加する。クエリ１に応じてノードの値を確定しながら X から Y までグラフをたどる。しかし TLE。

 提出 #23506723 (TLE×10 / AC×3) ※まだコンテスト期間中でありアクセスできないのでこっち>提出 #23506723.rb27

次にクエリ０では Y=X+1 だという制約を思い出して、グラフを配列上に配置した。しかしこれでは多少効率が良くなれど TLE は解消しない。制約はノード数(N)、クエリ数(Q)ともに上限が 10 万であり、１つのクエリに答えるのに線形時間をかけることができない。

局所の変更を全体に(対数時間で)波及させるのに BIT がまず浮かぶ。何を記録しようか。階差の累積値かなと思った。つまり、連続する３要素 A,B,C があり、２度のクエリ０によって A+B=S, B+C=T であるとわかっているなら、C-A=T-S から１つおきの２要素の差が直接にわかる。これの累積を記録しておけば、クエリ１で X と Y が 2×k はなれていても直接計算できる。

 提出 #23510943 (AC / 669 Byte / 413 ms / 31888 KB) ※まだアクセスできないのでこっち>提出 #23510943.rb27

結局 BIT は使わなかった。クエリへの答え方は階差の累積という点で同じだけど、クエリの先読みをすれば事前に累積値が記録しておける。更新がないなら値の取得に対数時間がかかる BIT よりただの配列の方が良い。Ambiguous と答えるタイミングは Union-Find で管理した。

 「《上級者向け（★7）》 X[i] + 1 = Y[i] の制約を外した場合（ワナにとても引っ掛かりやすいです）」

階差を使う解法は完全に「Y=X+1 (T=0 の場合)」という制約に依存しているので、とっかかりを失って困ってしまった。グラフなら困らないが TLE。階差を封じられてどうすればよいか。

 「A_1 と A_2、……、A_{N-1} と A_N の関係性がすべて分かっていた場合、A_1 の値を +1 すると、下図の通り +1 される要素と -1 される要素があります」

解説が公開された。プラスかマイナスか、そんな単純な関係やったんか。それにしてもそこからさらに(厳しくない方の)制約をクリアさせられることがもうつらい。

Y=X+1 (T=0 のとき) という条件が外れた厳しい方の制約だけど、X から Y へ至る異なるパスがクエリ０によって与えられたときにどうすればいいかわからないでいる。定数時間で答えるためにどのような情報の持ち方をしておけばいいのか(グラフは TLE)。でもプラスかマイナスかという単純な関係なのならば、すべてのパスに関わるノードをまとめて詰め込んでおいて、つじつまが合うのだろうか。

連結なノード間であるノードを基準(たとえばゼロ)にして相対的な値を割り振っておく。ノード間の距離(の偶奇)も記録しておく。迂回路があっても分岐点・合流点のノードが持つ相対値はパスによらず共通だし、パスによって異なる非共通ノードも、ノード数の偶奇はたぶん同じになる。まだよくわからないのは、連結成分ごとに基準となるノードが必要だけど、連結成分同士が連結するたびに基準と相対値のふり直しをして許されるのかというところ。小さい方の連結成分を選ぶようにすればいいのだろうけど。

全部 Union-Find に乗せたいけどうまくいかない。Unite は当然として、Find で集合の代表を書き換えるタイミングでもごにょごにょすると、集合の合体があったとしても偶奇と相対値を適切に(新しい代表を基準にして)更新できると思うんだけど、符号で死ぬほどバグらせる。一見正しい答えに見えても、バグ×バグ=正常だったりする。

 https://github.com/monnu123/atcoder_files/blob/master/kyopro90-68.cpp (monnu さん / C++ / 166 ms)

自分がやりたいのはたぶんこういうの。やっぱりできるんだね。不可能をやろうとしてるのでないとわかったのは朗報。

ところで、Ruby のようなスクリプト言語と C++ の実行時間が接近しているときは、入出力がネックになって C++ の実行時間が遅くなっている印象がある。C ランタイムとの連携を切ったり、std::endl が引き起こす flush を "\n" で回避したり、いろいろ対処法がある模様。

 https://github.com/NachiaVivias/kyopro-tenkei-90-submit-nachia/blob/main/shared-solutions/068-Paired-Information/068-01.cpp (Nachia さん / C++ / 51 ms)

こっちの見た目すっきりな方はすっきりしすぎてて自分がやりたいことと同じなのかどうかもわからない。

ノード数が 2N あるなあ。前半 N 個と後半 N 個の位置づけとは。

偶数世界と奇数世界？ これはノード番号 X が偶数か奇数かという話ではなく二部グラフの話なのであって、あるノード X を赤色で塗った場合と白色で塗った場合を同時並行で扱っているのではないか、という……あてずっぽうです。

 提出 #23560415 (AC / 778 Byte / 334 ms / 16544 KB) ※まだアクセスできないのでこっち>提出 #23560415.rb27

やった！ うんざりするほどバグらせてついに完成した(UnionFind 全乗せ版)。頭が整理されたところでバグまみれを捨ててイチから書き直したのが良かったと思う(それからもバグらせたんだけど)。

10
11

	D[a] *= D[g]
	V[a] += D[a]*D[g]*V[g]

↑ここは無駄なことをしてる。修正版はこう↓

10
11

	V[a] += D[a]*V[g]
	D[a] *= D[g]

Union-Find でグループの代表とサイズを管理するのはこれまでのおなじみだけど、同時に代表からの相対値を記録するのは考えたこともやったこともなかった。「重み付き UnionFind」というものがあるらしいが、いったい何に使うものなのか。

ノード数が 2N のすっきり解法は遠くから拝むだけにしておきます。

 https://gist.github.com/masa-aa/4be96f053457dc60625a3552288fb1e4 (masa_aa さん / PyPy3 / 304 ms)

これも重み付き UnionFind。ノード番号の偶奇を利用すれば別途偶奇の管理をする必要がないらしい。クエリへの応答部分でだけ偶奇を気にすればいいというのがよくわからないが、たぶんこれを考えた先に Nachia さんのサイズ 2N のグラフがあると思う。

偶奇を一体でぐちゃぐちゃ扱う(自分)→偶奇に前提をもうけて整理されたグラフを作る(masa_aa さん)→偶奇と奇偶を並行させて偶奇の別を気にしない(Nachia さん)、という違いなのではないか、という印象を持っている。

あ find メソッドで再帰呼び出しをしていない。スタックオーバーフローのおそれがないのはいい。

これだけの学びがあるのは企画の趣旨に照らして(そうでなくても)、すばらしい良問だったのでは？