脳log[AtCoder: 2021-06-17～]

最終更新: 2021-06-17T19:54+0900

♪ [AtCoder]競プロ典型 90 問／035 - Preserve Connectivity（★7）

解説はこちら>解説１、解説２、解説３

 LCA とダブリング

「実装したことはないけどダブリング(要は繰り返し二乗法でしょ？)で効率的に親を辿る？」と書いたのがつい先月のことだけど、とうとうダブリングを実装する機会が訪れた。

この問題がどうして、選ばれた複数の頂点を決まった順番で環状に並べて隣接する頂点ペアの LCA が辺の本数になって割る２が答え、になるのかは解説３を読む。今は LCA にだけ注目する。

LCA の取り扱いは「巨大企業」や「筆塗り」で経験があるけど、線形より効率的な LCA の検索が案外面倒くさい。「最小共通祖先 [いかたこのたこつぼ]」にいくつか手法がリストアップされているけど、自分が知っている手段はセグメント木だけであり、セグメント木は書くのが面倒くさい。

そこでダブリングです。

 提出 #23482710 (TLE×26 / 810 Byte / 2207 ms / 42608 KB) ※まだコンテスト期間中であり見られないはず。

間違えた(TLE)。

21
22
23
24
25
26
27
28
29
30
31
32
33
34

A = [ps=P.dup]
(D.max-1).bit_length.times{ # １世代上はすでに P としてあるので、１回分繰り返しが無駄かも。
	A << ps = N1.times.map{|a| ps[ps[a]] }
}

Ans = lambda{|a,dd|
	i = 0
	while 0<dd
		a = A[i][a] if 0<dd&1
		dd >>= 1
		i += 1
	end
	next a
}

A 配列に事前に親、親の親(２世代上)、４世代上、８世代上、とメモしておいて、Ans 関数(Ancestors の略ったら略)で「a の dd 世代上は？」という質問に対数時間で答えられるようにした。Ans 関数がこのようなインタフェースになっているのは、LCA を経由した２頂点間の辺の数を求めたい呼び出しもとで「同じ深さにある２頂点 a,b が初めて祖先を共有する深さは？」という問いを立てて、二分探索でその深さを確定させようとしたから。次のように。

35
36
37
38
39
40
41

Dst = lambda{|(a,b)|
	da,db = D[a],D[b]
	dc = (1..[da,db].min).bsearch{|dc|
		Ans[a,da-dc] != Ans[b,db-dc]
	}
	next dc ? da-dc+db-dc+2 : (da-db).abs
}

競プロにおいては対数は定数と言われるけれど、かなり大きな定数ではあり、必要がないところで log をくっつけると TLE に苦しめられたりする>「Pairs」。同じ日記に書いてあるけど、「射撃王」や「Handshake」のように余分な log があっても TLE にならないこともある。

 提出 #23482781 (AC / 873 Byte / 1082 ms / 42672 KB) ※まだコンテスト期間中であり見られないはず。

A 配列は正しくはこう使う。共有されている yuruhiya さんの解答 を見ても LCA#lca メソッドが同じ感じだったので、大嘘はついてないと思う。(Dst は Distance の略。D は Depth の略)

35
36
37
38
39
40
41
42
43

Dst = lambda{|(a,b)|
	da,db = D[a],D[b]
	a = Ans[a,da-db] if db<da
	b = Ans[b,db-da] if da<db
	A.reverse_each{|ans|
		a,b = ans[a],ans[b] if ans[a]!=ans[b]
	} if a!=b
	next a==b ? (da-db).abs : da+db-2*D[P[a]]
}

実は解説２にはこれを説明する具体的手順が書いてある(あとで詳しく読んだ)。だけどありとあらゆる落とし穴にはまりたがる自分にとって、「こうすればいいんですよ」とか「こうしてはいけませんよ」いうアドバイスは役に立たないんですな。「要は繰り返し二乗法でしょ」というだけの理解で実装してみて、「あれは良かったここはダメだった」と納得するまでは身にならない。仮にアドバイスのおかげで最初からうまくやれたとしても、それは今回だけのことであり、将来必ず自分の性向に導かれて穴にはまる。早いうちに地図を作っておくべきだ。そうすれば多少は、ね。

最終更新: 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 メソッドで再帰呼び出しをしていない。スタックオーバーフローのおそれがないのはいい。

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

最終更新: 2021-07-12T20:54+0900

♪ [AtCoder]東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)／A,B,C

 A 問題 Many Formulae

A 数列を後ろから見ていく方針は早くに決まったのだけど、初項を [1,0] ではなく [1,1] にしていたミスでいつまでも答えが合わなかった。あと余りを取り忘れて 1 TLE。

 提出 #23369338 (AC / 147 Byte / 106 ms / 24936 KB)

もう 54 分経っている。

 B 問題 Insurance

A 数列をソートすれば賢く答えが求められそうだけど、何も考えずに探索しても良さそう。この前の ABC204-E Rush Hour 2 と違って最初から実数解が求められているあたり、罠もなく素直なのでは？

デバッグ出力を消し忘れて 1 WA。bsearch メソッドで極小値を求めようとして 1 WA。三分探索(名前だけは知っていたが初めて書いた。「三分探索を救いたい - Qiita」)を 100 回試行しようとして 1 TLE。ざっくり半分の 50 回にして AC。本当は探索範囲の幅が許容誤差以下になったかどうかを終了条件にすべきだったそれもダメ？。

AC までおおよそ 30 分だから B 問題は A 問題より簡単。

 C 問題 Calculator

盲滅法な探索では時間が足りない。考えても時間の無駄なので興味本位で解説を読んだ>「C - Calculator 解説 by maroonrk_admin」

フィボナッチ数？ 「競プロ典型 90 問」でも見かけたが、この数列がどうして頻繁にあちこちに登場するのかわからない。限りなくありふれたジェネレータなのか(知らなかったけど A 問題にもフィボナッチ数が現れていたらしい)。あと、計算途中で１を足すという行為が、新しい系列のフィボナッチ数列を開始すること、それらずれたフィボナッチ数列を串刺しにした和が数列として現れるということもあまりピンとこない。そうなの？ そんなこと漸化式を見てわかる？ 足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。

とりあえず実験をした。x,y=1,1 を初項として操作３と４を繰り返すとどのように値が増加するか。大体 80 数回で N の上限を超える。今度は x,y=0,0 でスタートして 80 数回の１か所でだけ +1 をすると、80 数回の操作３、４の結果がどういう値になるのかを調べた。これは並べるとフィボナッチ数列になった。

つまり、次の提出における A 数列というのは、フィボナッチ数列を貼り付けたものではなく、+1 するタイミングによって操作３と４を繰り返したのちのちにどれだけの影響を及ぼすかというのを予め調べた実験結果なのである。

 提出 #23379308 (半分くらい WA)

「貪欲をすればよい」と解説に書いてあったので貪欲をした。フィボナッチ数列の増加のしかたを見れば組み合わせでどんな数字でも作れそうな雰囲気はある(基数の冪乗を大きい方から取っていくのと同じように)。

「この時，i と i+1 両方で操作することはありません． なぜなら，」は読み飛ばした。解説の細かい部分にこだわってもわかりません。

WA の原因は問題を読み誤っていたこと。x か y のどちらかが N になればいいと思っていたが、そうではない。

 提出 #23379741 (AC)

x と y を取り替えればいいのだから、仮の操作列を作ってから必要に応じて操作１と２、操作３と４を交換するようにした。最初からきれいな解答を作ろうという努力はあきらめている。

ARC-C が自分のいるところからどれだけ高くにあるかは垣間見られたのでは？ 時間内に B 問題まで解けただけで上出来なのに、レイティングは下がるんですよ。緑に対してあまりにひどい仕打ち。A、B がどちらも茶 diff だといっても、ARC に参加する層にとっての茶 diff だという意味で、ABC の茶 diff 問題とはくらべられないと思うんだ。へなちょこながら ARC に参加する意気にレイティングで報いてほしい(嘘です)。

最終更新: 2021-09-14T17:27+0900

♪ [AtCoder]競プロ典型 90 問／059 - Many Graph Queries（★7）

AtCoder タグを付けてるけど非公式コンテストです。

この問題はとっかかりがなくて最初から解説を読んだ>解説１、解説２、解説３。

 キーワード「DAG を使いこなそう」

この問題で扱われるグラフは DAG (有向非巡回グラフ) といわれるもので、サイクル(閉路) を含まない有向グラフです。

えっっっ？ どこに閉路を含まないって書いてあった？ 問題文を３回読み直して気がついた。

辺 i は頂点 Xi から Yi に向かいます。

制約 1≤Xi<Yi≤N

制約が持つ情報量が多すぎて見逃していた。難しい。そして閉路が含まれてるなら含まれてるで、解説３に書かれている強連結成分(SCC)分解を手段として持っておくべきであると。

 提出１ (TLE×6 / 3325 ms / 461844 KB) 得点 2/7

まだコンテスト期間中だけどソースコード共有の動きがあるくらいなので隠す必要はないかなと>「解説が公開されたら、ソースコードを共有していきましょう」。

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23

N,M,Q = gets.split.map(&:to_i)
B = 60 # Bignum に切り替わらないビット数を。
Z = (N-1)/B+2
V = Array.new(N+1){|a| [0]*(Z-a/B) }
E = Array.new(N+1){[]}; M.times{
	x,y = gets.split
	E[x.to_i]<<y.to_i
}

N.downto(1){|a|
	va = V[a]
	va[-1] |= 1<<a%B
	E[a].each{|b|
		V[b].each_with_index{|v,i|
			va[i] |= v
		} if va[a/B-b/B-1][b%B]<1
	}
}

puts$<.map{|ln|
	a,b = ln.split.map(&:to_i)
	next %w[No Yes][V[a][a/B-b/B-1][b%B]]
}

２枚目の解説画像で満点解答のために「ビット演算で 64 倍高速化」と書かれていることから、Ruby で満点解答が望めないのは明らか。Ruby を使うことによる定数倍のハンデが最初から 100 より大きいので……。手元では V = の初期化部分だけで２、３秒かかってるもんね。部分点２で満足している。

AtCoder はスクリプト言語に優しいので、定数倍高速化がキーになるのは非公式コンテストならではかな。解説が大いに参考になる。

昨日の ABC204-D - Cooking の解法はどこか(解説１)で見たような形だなあと思いながら書いていた(この日記を書いてるのは月曜だけど、典型90-059の出題は土曜日だったので、日曜の ABC の前に取りかかっていた)。

 解説と違う点

キーワードからこうだろうと最初に思いついた方法で実装したら解説とちょっと違う。違って良くない。

最初にすべての頂点について到達可能な点を(テキトーにビット演算を使って)調べてからクエリに定数時間で答える、というのがさっき貼り付けたスクリプトだけど、解説ではクエリを 64 並列で調べるようにしていた。クエリが起点にある。

調べたら、重いケースでは頂点数(N=100000)、クエリ数(Q=100000)に対して、実際に到達可能性が参照される頂点の種類が 84000 ちょっとになるものがほとんどだった(例外が 99999)。約 16000 の頂点に関しては到達可能地点を調べたのが無駄だった。まあ、無駄を省こうとするとスタックオーバーフローを避けてごてごてと記述と条件判断が増えるわりに、２割も違わない(それも入力依存)という見かたはできる。

必ずしも良くないばかりでもなくて、頂点数 N に比して辺数 M が大きい場合、想定解法の方が遅くなる。

 提出２ (MLE×1 / 1154 ms / 1244032 KB)

基本は提出１と同じ。30 ビット 60 ビットでテキトーに区切っていた最大で 10 万ビットになりうるビットフラグを、１つの Bignum にまとめた。

多倍長が許されるのは数百桁までかなと思ってたんだけど、(最大で)10万桁でもすっごく速かった。しかしメモリ制限 1024 MB を超えて 1.24 GB 使ったところで MLE。

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16

N,M,Q = gets.split.map(&:to_i)
E = Array.new(N){[]}; M.times{
	x,y = gets.split
	E[N-x.to_i]<<N-y.to_i
}
V = [nil]*N
N.times{|a|
	va,bs,b = 1<<a,E[a]
	va |= V[b] if va[b]<1 while b = bs.pop
	V[a] = va
}

$<.each{|ln|
	a,b = ln.split.map(&:to_i)
	puts %w[No Yes][V[N-a][N-b]]
}

頂点番号とビット位置の対応を逆向きにしたのが工夫(提出１でも Z-a/B という形でやっていた)。たとえば N-1 番目の頂点が N 番目に移動するというのを 0b11 で表現すれば Bignum はいらない。これを素直に 1<<N-1|1<<N で表していたら、ほぼ全ての頂点で N 桁の Bignum が必要になってもおかしくない(頂点１以下全ての頂点が頂点 N に遷移する場合)。しかしあえなく MLE。工夫なしだと 1.29 GB だったから 50 MB だけ減りましたよ。

たぶん Bignum のネックは桁数に比例する部分ではなく、100 桁であれ１万桁であれ必ず必要になる基礎的な部分でのコストなのだろう。その面では 64 ビット版が不利だ。Bignum か非 Bignum かで見れば、上の段落で改善するのは 10 万頂点のうちの 62 頂点程度に過ぎない。桁数部分での寄与は小さい。

 提出３ (AC / 2009 ms / 500612 KB) 得点 7/7

これは提出１、２と違って想定解法と同じ方針。ただしクエリ 64 並列ではなく 10 万並列でやっている。

DP がしたいのに Bignum を頂点の数だけ保持すると MLE になるのをどうすれば良いか。TLE を避けたいなら Bignum を使うしかないがどうすれば良いか。頂点番号の小さい順にどんどん処理を進めて、使用済みの情報は辺もクエリも遷移してきたという DP 要素もどんどん捨てていった。一時的には C 配列に処理待ちの Bignum が蓄えられるけど、どこかから遷移して来るまではそれも 0 (Fixnum) だ。

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22

N,M,Q = gets.split.map(&:to_i)
E = M.times.map{ gets.split.map(&:to_i) }.sort_by(&:first)
A = Array.new(N){[]}
B = Array.new(N){[]}
Q.times{|q|
	a,b = gets.split
	A[-a.to_i]<<q
	B[-b.to_i]<<q
}

r = 0
C = [0]*N
N.times{
	as,bs,c,q = A.pop,B.pop,C.pop
	c |= 1<<q while q = as.pop
	r |= c[q]<<q while q = bs.pop
	C[N-E.shift[1]] |= c while e = E[0] and e[0]+A.size==N
}

Q.times{|q|
	puts %w[No Yes][r[q]]
}

Ruby で満点がありだったのだなあ。道具のせいにしてあきらめなくて良かった。

 提出４ (AC / 1376 ms / 383080 KB)

メモリもタイムもさらに良くなった。提出３がベースだけど、クエリごとに１ビットを使うのではなく、スタート地点 A が共通するクエリが同じビットを共有する。

こちらを参考にして。

昨日はうしさんのライブラリを参考にして解いたため、(A_i,B_i)というクエリを処理するときにはdp[A_i]|=1<<iとしていた。そうではなくdp[u]|=1<<uとし、すべてのペアについて問題を解くことにすれば、頂点番号uに対しては1..uに対応するbitしか保存しなくてよいため、必要なメモリが\frac{N^2}2くらいになるらしい。

週記（2021/05/31-2021/06/06） - kotatsugameの日記

頂点番号が小さい順に処理をするという提出３の流れと、頂点番号が小さいものから０に近いビットを割り当てるというのがマッチして、ビットの同時使用量が節約できる。

整理したからそのまま同じではないけど、だいたいこんな雰囲気>typical90_59_nosub5.rb27

@2021-09-14 結局最後のも提出した>提出 #25841973 (1149 ms)

最終更新: 2021-06-05T05:03+0900

♪ [AtCoder] 競プロ典型 90 問／057 - Flip Flap（★6）

解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg

この問題はとても良かった。確実に力になった。問題を解く選択肢が増えた。キーワードは「行列の掃き出し法を知ろう」だって。

最初は独力でパネルを順番に見ていく DFS を書いた。それしか知らない。だけどどうしても入力に左右されるし、あるパネルに影響する複数のスイッチの組み合わせを総当たりするので遅くなる。

入力を前処理して扱いやすくするとは考えてもみなかった。

でまあ今後は、こういうことができると知ったはいいけど、これが適用できる対象の性質を見抜けるかどうか、というところに課題が移ったとみていいのではないかな。簡単ではないね。

具体的な実装にも迷いがある。スイッチ数(N)、パネル数(M)の上限が 300 なのに対して 550 ms の時間をかけている。メインループだけど、

1. スイッチ群から最も左のビットが立っているスイッチを選んで取り出す
2. 残されたスイッチ群を処理して最も左のビットが取り出したスイッチのものより右にくるようにする
3. 取り出したスイッチを押したり押さなかったりする(最も左のビットが立っているスイッチはこれ１つだけなので確実にどちらかを選べる)
4. 繰り返し

ステップ１の処理が N で、ステップ２の処理が N×M。もっとシュッと片付くうまい書き方があっても良さそうでは？

hai!@magrofly「典型057 Ruby https://t.co/Dri1yBSvuK」 / Twitter

「基底を求める」のはよくわからないけど、「解く」過程では順番に適用していくだけでいいようだ。さっきの手順に当てはめると、基底を求めるのがステップ２に相当して、解く部分がステップ３。ステップ１の検索が不要であると。

 549 ms

最初の提出。無駄にソート、検索している(９行目)。

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19

N,M = gets.split.map(&:to_i)
A = N.times.map{
	gets
	next gets.split.map{_1.to_i-1}
}
S = gets.split.map(&:to_i)

n,T = 0,[0]*M
while as = A.sort_by!(&:first).shift
	i = as[0]
	A.map!{|bs|
		i < bs[0] ? bs : ((as|bs)-(as&bs)).sort
	}.reject!{|bs|
		bs.empty? && n+=1
	}
	as.each{|i| T[i] = 1-T[i] } if S[i]!=T[i]
end

p(S==T ? 2.pow(n,998244353) : 0)

 524 ms

ツイートを参考に改良したが、あまり良くはならない。N,M<=300 だから？ 対称差を求める部分(15行目)が富豪的過ぎるから？ 前処理の部分でまだちょっと変なやり方をしてる？

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

N,M = gets.split.map(&:to_i)
A = N.times.map{
	gets
	next gets.split.map{_1.to_i-1}
}
S = gets.split.map(&:to_i)

N.times{|i|
	next if A[i].empty?
	(i+1...N).each{|j|
		next if A[j].empty?
		if A[j][0] < A[i][0]
			A[i],A[j] = A[j],A[i]
		elsif A[j][0] == A[i][0]
			A[j] = ((A[i]|A[j])-(A[i]&A[j])).sort
		end
	}
}
A.reject!(&:empty?)
O = N-A.size

T,as = [0]*M,nil
as.each{|i| T[i] = 1-T[i] } if S[as[0]]!=T[as[0]] while as = A.shift

p(S==T ? 2.pow(O,998244353) : 0)

最終更新: 2021-06-24T16:08+0900

♪ [AtCoder] 競プロ典型 90 問／055 - Select 5（★2）

★２つだからってこういう素直なスクリプトを投げた。

N,P,Q,*A = $<.read.split.map(&:to_i)
p A.combination(5).count{|a5| Q == a5.inject{_1*_2%P} }

結果は TLE×21/AC×4。なんだよ全然ダメじゃんかよ。解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/055.jpg。Ruby では解説が役に立たない。★６～７相当のより高速な解法があるというから、そちらを解説してもらわねば。

ABC192-F Potion (20210224p01) を思い出しながら悪あがきをした。

N,P,Q,*A = $<.read.split.map(&:to_i)
q = Hash.new 0
S = A.map{|a| q[a%P]+=1; q.dup }
(N-1).downto(N-4){|k|
	S.pop # S.size==k
	q = Hash.new 0
	S.map!.with_index(N-k){|q0,i|
		a = A[i]
		q0.each{ q[_1*a%P]+=_2 }
		next q.dup
	}
}
p q[Q]

これで TLE×6/AC×19。0≤Q<P≤10^9 という制約がえぐすぎるんよな。大きすぎるし、素数じゃないし。いったいどういう手が打てるのか。

N が 100 以下というところで何かできないかと考えた。3..100 のある i より左から A×A のペアを作って記録し、また 1..98 のある i より右から A×A のペアを作って記録し、3..98 の 96 通りのある A_i に関して i の左右から条件を満たすペアを引っぱって来られないかと考えた。P で割った余りは 10^9 通りになりうるけど、A×A%P が取り得る値は 10000 通りより少ないから、左側のペア×A_i を総当たりしても高々 1000000 通りであり、これは許される。あとは右側のペアが定数時間で選べれば良い。ここでモジュラ逆数が使えるような、使いたいような気がするんだけど、法が素数でないから「a が m と互いに素でなければならず、さもなくば逆元 x は存在しない。」と Wikipedia に書かれていて困っている。A×A×A%P の値が決まっているとき、A×A%P の値が何であれば A×A×A×A×A%P==Q となるか。たぶん１つに定まらないのではないかと思う。ここで詰まった。

Ruby を使う良さってこういうところだよね。ぬるい解法が許されないところ(許されるとそれ以上考えないので)。「Ruby ならではのお楽しみポイント」「この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。」 そこは問題の本質ではないからかかずらいたくないという考えもあるだろうけど、自分が一番楽しめるのはここ。

Ruby で 365 ms の解答が共有されているなあ。見たい、見たくない、見たくない。

典型 90-005 の解説から>「mod の値が 998244353 のような特殊な値ではないので一工夫必要ですが、それでもたとえば 3 種類くらいmod を用意して中国剰余定理で復元する方法などで上手くいきます」。中国剰余定理は Wikipedia やブログを読む機会が何度かあったけど、まだ早い、と理解をあきらめている状態。

「線形篩を用いた合成数を法とする逆元の列挙」

最終更新: 2021-06-08T14:11+0900

♪ [AtCoder]AtCoder Beginner Contest 170／F 問題 Pond Skater

競プロ典型 90 問の 043 - Maze Challenge with Lack of Sleep（★4）が普通に解けたので、Pond Skater (青diff1968)も解けるような気がした(既視感>20200826p01。根拠は必要ない)。

 提出 #23175112 (AC / 777 Byte / 492 ms / 46772 KB)

All AC になるまで死ぬほどバグらせた。これが時間内に解ける未来が見えない。訪問済みフラグが二値ではない。ループの継続条件とキューへの追加条件が同じではない。ループのあいだ無条件にキューに追加していると rand_20_01.txt と rand_20_03.txt の２つのケースでキューが複製要素で膨れ上がってしまう。それ以外のケースでは AC なのに。

無駄に難しくしてる？ そうであってほしい。

 Ruby でのすべての提出 (AC のみ / 実行時間昇順)

比較すると短いし速いし省メモリだと思う。テストケースハック(※テストケースは公開されている)らしき提出を除けば。

訪問済みフラグを水平方向と垂直方向に分けたのが間違いだったろうか。途中からフラグ(二値)ではなくなったし、紆余曲折を経て扱いが同列だし、単にコストとして再定義して書き直せるのでは？

 提出 #23175271 (AC / 590 Byte / 374 ms / 39016 KB)

Vh と Vv だったものを C に統合した。さらに短くさらに速くさらに省メモリになった。最初にコストでなく２つのフラグを使って書き始めたのが間違いの始まりだったのだなあ(Maze Challenge with Lack of Sleep（★4）の解き方がそうだったからなんだけど)。

最終更新: 2021-06-08T14:41+0900

♪ [AtCoder] エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）／E 問題 Count Descendants

解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。

ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。

話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。

 クエリ(U,D)に答える方法１

1. ある深さ D にあるノードのうち祖先に U を持つものを選ぼうか。
2. 実装したことはないけどダブリング(要は繰り返し二乗法でしょ？)で効率的に親を辿る？
3. (ほぼ)全ノードがフラットに並んでたらダブリング関係なくクエリ(N)×ある深さのノード数(N)で死ぬ。

 クエリ(U,D)に答える方法２

1. あるノード U の子孫ノードを深さごとに数えておこうか。
2. 深さを調べる深さ優先探索のついでにそれはできるけど、子ノードが記録した配列をマージするのが大変。ほぼノードの数だけマージ操作が必要。マージテク？

3. 実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。

   一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。

 提出 #22827097 (TLE×27 / AC×3)

これはマージしないでいいように１つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。

 提出 #22832306 (AC / 708 ms / 285,364 KB)

基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。

 クエリ(U,D)に答える方法３

これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー？

1. 深さ優先探索で深さを調べると同時に、あるノードに降りてきたタイミングと上っていくタイミングを記録しておく。
2. クエリがきたらノード U の両タイミングの間に処理をしたノード(=子孫ノード)のうち、ある深さ D にあるノードの数を答える。
3. タイミング配列をなめて深さを確かめる線形時間の処理は許されない。どうする？
4. (３つの提出を読んだのに思い出せない) どうする？
5. タイミング配列を深さごとに分けておくのかな。
6. クエリが指定する深さのタイミング配列を取り出して、そこからクエリが指定するノードの子孫にあたる範囲を二分探索で切り出すと、答えがわかる……かな？ 実装して AC をもらってないので不確か。

確かなことはこのあたりの提出を読めばわかる。(提出の早い順)

• 提出 #22837949 (tinsep19 さん / AC / 1016 ms / 94,688 KB)
• 提出 #22839832 (konayuki さん / AC / 910 ms / 296,740 KB)
• 提出 #22841409 (qib さん / AC / 806 ms / 58,764 KB)

メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。

最終更新: 2021-04-30T21:11+0900

♪ [AtCoder] AtCoder Beginner Contest 199（Sponsored by Panasonic）／D 問題 RGB Coloring 2

「10分間３問早解き」回だったわけなので４問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。

 提出 #22101036 (AC / 343 ms)

AC のきっかけはこのツイート。

chokudai(高橋 直大)ナス@chokudai

D問題、非連結ですって言うだけでDiff400くらい落ちそう

Twitter

chokudai(高橋 直大)ナス@chokudai

非連結ですって言っても落ちないわ（サンプルにあるし）

連結で出題しないと400落ちなさそう。

Twitter

「連結で出題しないと落ちない」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。

サンプル４つのうち２つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある？

 AC 前の提出 #22100473 (TLE×2 / １つは after_contest)

テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。

しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。

• widetree_all2one.txt

だけど次のように番号の付け方を変えただけで問題が問題でなくなる。

• widetree_one2all.txt

たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。

ソートするにせよ先読みするにせよ、２番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。

 提出 #22109995 (AC / 238 ms)

DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p02、20201107p01.05。

最終更新: 2021-06-08T15:01+0900

♪ [AtCoder] AtCoder Beginner Contest 198／D 問題 Send More Money

昨日あった ABC。D 問題は覆面算。たまたま何か月か前に「FDCAJH × IBCFEH = FBAECIIJEGIH」というのを解く機会があったのだけど、時間制限がないせいで雑に総当たりをして済ませてしまっていた。

 提出 #21665467 (TLE×6 / AC×34)

本番中は TLE で終わってしまった。E 問題を 15 分で片付けて戻ってきたけど、ついに通せなかった。

 提出 #21721083 (AC / 3703 ms)

制限時間が大盤振る舞いの５秒なんだよね。

桁を１つ２つ減らすだけで時間がだいぶ違うだろうという予測はできたけど、減らし方がわからなかった。なんといっても目の前に文字で書かれた式があるわけではなく、色々なケースが入力されるわけなので。

TODO: Array#all? の中のテストは l<=r より l==r||l+1==r の方が厳しくて良い。

TODO: 和の先頭の桁が１だとすぐにわかる場合がある。

TODO: 列挙してから弾くより列挙しない方がいい。(確定桁が１つあったとして、未確定桁(=文字種-1)の順列の数だけ弾くのは手間だから)

TODO: ループの中の処理がシンプルになるように入念に事前準備をした方がいい。

 Ruby によるすべての提出

現在 Ruby での AC 提出は 20。実行時間が 109 ms から 4845 ms までと幅広い。中央値は３秒台です。

たとえば(４桁 ms では最も速い)約 1.6 秒のこの提出>#21688714

先頭桁が０のケースを弾くと同時に、末尾の桁が一致するかどうかだけ特別にチェックしている。一致しないケースでは文字式の全体を数値化する無駄がスキップできる。このひと手間が効果的なのだと思う。

それと、全くの想定外だったのだけど、文字が 11 種類以上使われている式が入力されるケースがあったのだろうか(上の 1.6 秒の提出がチェックして UNSOLVABLE を出力している)。AtCoder の問題は入力や条件がきれいに整理されていて枝葉の手間が省けるように作られているだろう、という甘えがあるのは否めない。

３つある３桁 ms の提出が何をやっているのかは、さっぱりわかりません。

 提出 #21741214 (AC / 921 ms)

４つの TODO を意識して書いたけど、妥協した部分もある。

• 妥協１：確定した１を他の非ゼロと混ぜて列挙した。
• 妥協２：列挙を正と非負の２つに分けたがどちらにも permutation メソッドを使いたかったがために、配列の引き算やら配列の２段参照がループの中にある。

とはいえ、これを深さ優先探索で妥協なく書き換えただけで２桁 ms になる？ そう、Ruby で現在最速の提出は 71 ms になっている。

根本的なところで、列挙してから弾くか、可能性のある組み合わせだけを列挙するかという違いがあるのかな。そっち方面で書こうとしたときは、ある桁を見たときに未確定文字が０なのか、１個あるのか２個か３個か、未確定文字があるのはどの項か、繰り上がりはあるのか、ということを考えるのが面倒くさくなって(=脳のキャパシティをオーバーして)、書けなかったんだよね。

 提出 #21743144 (WA×1 / 90 ms)

書けなかったのをがんばって書いた。時間は申し分ないけども１つの WA。たぶん答えがないケースだと思うんだけど……。

 提出 #21743445 (AC / 66 ms)

WA の原因は非ゼロチェックが１つ抜けていたこと。それと、想定外だと書いた「文字が 11 種類以上使われているケース」はサンプル４がそうだった。コピペするだけで全然読んでいない。

 「FDCAJH × IBCFEH = FBAECIIJEGIH」

雑に総当たりしていたのを反省して(TLE は嫌だ！)、数か月ぶりに書き直した。提出 #21743445 をベースにして、掛け算に対応させた。prd の計算が難しかったのですよ。ありえたかもしれないもうひとつの筆算のかたち。すっごく縦長になるけども。

A = 'FDCAJH'.bytes.to_a # to_a is for Ruby 1.8/1.9
B = 'IBCFEH'.bytes.to_a
P = 'FBAECIIJEGIH'.bytes.to_a

C2D = [nil]*91
D2C = [nil]*10
NZ = [-1]*91; NZ[A[0]] = NZ[B[0]] = NZ[P[0]] = 0
F = lambda{|i,carry,aa,bb,zz|
	next carry<1 if i<-P.size

	a = (c = A[i]) ? C2D[c] : 0
	b = (c = B[i]) ? C2D[c] : 0 if a
	next D2C.each_with_index.any?{|e,d|
		next if e || d==NZ[c]
		C2D[c],D2C[d] = d,c
		next F[i,carry,aa,bb,zz] || C2D[c] = D2C[d] = nil
	} unless b

	prd = a*bb+b*aa+a*b*zz+carry

	if p = C2D[c=P[i]]
		next p==prd%10 && F[i-1,prd/10,a*zz+aa,b*zz+bb,zz*10]
	else
		p = prd%10
		next if D2C[p] || p==NZ[c]
		C2D[c],D2C[p] = p,c
		next F[i-1,prd/10,a*zz+aa,b*zz+bb,zz*10] || C2D[c] = D2C[p] = nil
	end
}
raise unless F[-1,0,0,0,1]

puts [A,B,P].map{|a|'%*d'%[P.size,a.inject(0){|b,c| b*10+C2D[c] }]}

最終更新: 2021-06-02T21:11+0900

♪ [AtCoder] AtCoder Beginner Contest 004／D 問題 マーブル

緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない。

だから青色。難しかったん。１年くらい前に ABC004 を埋めようとしたときは力が及ばず C 問題までしか提出に至っていなかった。

 提出 #21534453 (WA×2 / AC×83)