最終更新: 2021-06-17T19:54+0900
「実装したことはないけどダブリング(要は繰り返し二乗法でしょ？)で効率的に親を辿る？」と書いたのがつい先月のことだけど、とうとうダブリングを実装する機会が訪れた。
この問題がどうして、選ばれた複数の頂点を決まった順番で環状に並べて隣接する頂点ペアの LCA が辺の本数になって割る２が答え、になるのかは解説３を読む。今は LCA にだけ注目する。
LCA の取り扱いは「巨大企業」や「筆塗り」で経験があるけど、線形より効率的な LCA の検索が案外面倒くさい。「最小共通祖先 [いかたこのたこつぼ]」にいくつか手法がリストアップされているけど、自分が知っている手段はセグメント木だけであり、セグメント木は書くのが面倒くさい。
そこでダブリングです。
間違えた(TLE)。
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 が初めて祖先を共有する深さは？」という問いを立てて、二分探索でその深さを確定させようとしたから。次のように。
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 にならないこともある。
A 配列は正しくはこう使う。共有されている yuruhiya さんの解答 を見ても LCA#lca メソッドが同じ感じだったので、大嘘はついてないと思う。(Dst は Distance の略。D は Depth の略)
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
すごく難しいです。答えの出し方に確証が持てないまま、とりあえずグラフとして解答を書いた。クエリ０に応じて辺を追加する。クエリ１に応じてノードの値を確定しながら X から Y までグラフをたどる。しかし TLE。
次にクエリ０では 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 はなれていても直接計算できる。
結局 BIT は使わなかった。クエリへの答え方は階差の累積という点で同じだけど、クエリの先読みをすれば事前に累積値が記録しておける。更新がないなら値の取得に対数時間がかかる BIT よりただの配列の方が良い。Ambiguous と答えるタイミングは Union-Find で管理した。
階差を使う解法は完全に「Y=X+1 (T=0 の場合)」という制約に依存しているので、とっかかりを失って困ってしまった。グラフなら困らないが TLE。階差を封じられてどうすればよいか。
解説が公開された。プラスかマイナスか、そんな単純な関係やったんか。それにしてもそこからさらに(厳しくない方の)制約をクリアさせられることがもうつらい。
Y=X+1 (T=0 のとき) という条件が外れた厳しい方の制約だけど、X から Y へ至る異なるパスがクエリ０によって与えられたときにどうすればいいかわからないでいる。定数時間で答えるためにどのような情報の持ち方をしておけばいいのか(グラフは TLE)。でもプラスかマイナスかという単純な関係なのならば、すべてのパスに関わるノードをまとめて詰め込んでおいて、つじつまが合うのだろうか。
連結なノード間であるノードを基準(たとえばゼロ)にして相対的な値を割り振っておく。ノード間の距離(の偶奇)も記録しておく。迂回路があっても分岐点・合流点のノードが持つ相対値はパスによらず共通だし、パスによって異なる非共通ノードも、ノード数の偶奇はたぶん同じになる。まだよくわからないのは、連結成分ごとに基準となるノードが必要だけど、連結成分同士が連結するたびに基準と相対値のふり直しをして許されるのかというところ。小さい方の連結成分を選ぶようにすればいいのだろうけど。
全部 Union-Find に乗せたいけどうまくいかない。Unite は当然として、Find で集合の代表を書き換えるタイミングでもごにょごにょすると、集合の合体があったとしても偶奇と相対値を適切に(新しい代表を基準にして)更新できると思うんだけど、符号で死ぬほどバグらせる。一見正しい答えに見えても、バグ×バグ=正常だったりする。
自分がやりたいのはたぶんこういうの。やっぱりできるんだね。不可能をやろうとしてるのでないとわかったのは朗報。
ところで、Ruby のようなスクリプト言語と C++ の実行時間が接近しているときは、入出力がネックになって C++ の実行時間が遅くなっている印象がある。C ランタイムとの連携を切ったり、std::endl が引き起こす flush を "\n" で回避したり、いろいろ対処法がある模様。
こっちの見た目すっきりな方はすっきりしすぎてて自分がやりたいことと同じなのかどうかもわからない。
ノード数が 2N あるなあ。前半 N 個と後半 N 個の位置づけとは。
偶数世界と奇数世界？ これはノード番号 X が偶数か奇数かという話ではなく二部グラフの話なのであって、あるノード X を赤色で塗った場合と白色で塗った場合を同時並行で扱っているのではないか、という……あてずっぽうです。
やった！ うんざりするほどバグらせてついに完成した(UnionFind 全乗せ版)。頭が整理されたところでバグまみれを捨ててイチから書き直したのが良かったと思う(それからもバグらせたんだけど)。
D[a] *= D[g] V[a] += D[a]*D[g]*V[g]
↑ここは無駄なことをしてる。修正版はこう↓
V[a] += D[a]*V[g] D[a] *= D[g]
Union-Find でグループの代表とサイズを管理するのはこれまでのおなじみだけど、同時に代表からの相対値を記録するのは考えたこともやったこともなかった。「重み付き UnionFind」というものがあるらしいが、いったい何に使うものなのか。
ノード数が 2N のすっきり解法は遠くから拝むだけにしておきます。
これも重み付き UnionFind。ノード番号の偶奇を利用すれば別途偶奇の管理をする必要がないらしい。クエリへの応答部分でだけ偶奇を気にすればいいというのがよくわからないが、たぶんこれを考えた先に Nachia さんのサイズ 2N のグラフがあると思う。
偶奇を一体でぐちゃぐちゃ扱う(自分)→偶奇に前提をもうけて整理されたグラフを作る(masa_aa さん)→偶奇と奇偶を並行させて偶奇の別を気にしない(Nachia さん)、という違いなのではないか、という印象を持っている。
あ find メソッドで再帰呼び出しをしていない。スタックオーバーフローのおそれがないのはいい。
これだけの学びがあるのは企画の趣旨に照らして(そうでなくても)、すばらしい良問だったのでは？
最終更新: 2021-07-12T20:54+0900
A 数列を後ろから見ていく方針は早くに決まったのだけど、初項を [1,0] ではなく [1,1] にしていたミスでいつまでも答えが合わなかった。あと余りを取り忘れて 1 TLE。
もう 54 分経っている。
A 数列をソートすれば賢く答えが求められそうだけど、何も考えずに探索しても良さそう。この前の ABC204-E Rush Hour 2 と違って最初から実数解が求められているあたり、罠もなく素直なのでは？
デバッグ出力を消し忘れて 1 WA。bsearch メソッドで極小値を求めようとして 1 WA。三分探索(名前だけは知っていたが初めて書いた。「三分探索を救いたい - Qiita」)を 100 回試行しようとして 1 TLE。ざっくり半分の 50 回にして AC。本当は探索範囲の幅が許容誤差以下になったかどうかを終了条件にすべきだったそれもダメ？。
AC までおおよそ 30 分だから B 問題は A 問題より簡単。
盲滅法な探索では時間が足りない。考えても時間の無駄なので興味本位で解説を読んだ>「C - Calculator 解説 by maroonrk_admin」
フィボナッチ数？ 「競プロ典型 90 問」でも見かけたが、この数列がどうして頻繁にあちこちに登場するのかわからない。限りなくありふれたジェネレータなのか(知らなかったけど A 問題にもフィボナッチ数が現れていたらしい)。あと、計算途中で１を足すという行為が、新しい系列のフィボナッチ数列を開始すること、それらずれたフィボナッチ数列を串刺しにした和が数列として現れるということもあまりピンとこない。そうなの？ そんなこと漸化式を見てわかる？ 足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。
とりあえず実験をした。x,y=1,1 を初項として操作３と４を繰り返すとどのように値が増加するか。大体 80 数回で N の上限を超える。今度は x,y=0,0 でスタートして 80 数回の１か所でだけ +1 をすると、80 数回の操作３、４の結果がどういう値になるのかを調べた。これは並べるとフィボナッチ数列になった。
つまり、次の提出における A 数列というのは、フィボナッチ数列を貼り付けたものではなく、+1 するタイミングによって操作３と４を繰り返したのちのちにどれだけの影響を及ぼすかというのを予め調べた実験結果なのである。
「貪欲をすればよい
」と解説に書いてあったので貪欲をした。フィボナッチ数列の増加のしかたを見れば組み合わせでどんな数字でも作れそうな雰囲気はある(基数の冪乗を大きい方から取っていくのと同じように)。
「この時，i と i+1 両方で操作することはありません． なぜなら，
」は読み飛ばした。解説の細かい部分にこだわってもわかりません。
WA の原因は問題を読み誤っていたこと。x か y のどちらかが N になればいいと思っていたが、そうではない。
x と y を取り替えればいいのだから、仮の操作列を作ってから必要に応じて操作１と２、操作３と４を交換するようにした。最初からきれいな解答を作ろうという努力はあきらめている。
ARC-C が自分のいるところからどれだけ高くにあるかは垣間見られたのでは？ 時間内に B 問題まで解けただけで上出来なのに、レイティングは下がるんですよ。緑に対してあまりにひどい仕打ち。A、B がどちらも茶 diff だといっても、ARC に参加する層にとっての茶 diff だという意味で、ABC の茶 diff 問題とはくらべられないと思うんだ。へなちょこながら ARC に参加する意気にレイティングで報いてほしい(嘘です)。
それもダメ？ [[実数の二分探索・三分探索はループ回数を決め打ちしようね - えびちゃんの日記|https://rsk0315.hatenablog.com/entry/2020/04/29/155009]]。探索範囲が過大(過小)な値に寄っていったときに、浮動小数点数の密度が足りなくなって無限ループする？ 無限ループしていないことをもって OK としていい？
最終更新: 2021-09-14T17:27+0900
AtCoder タグを付けてるけど非公式コンテストです。
この問題はとっかかりがなくて最初から解説を読んだ>解説１、解説２、解説３。
この問題で扱われるグラフは DAG (有向非巡回グラフ) といわれるもので、サイクル(閉路) を含まない有向グラフです。
えっっっ？ どこに閉路を含まないって書いてあった？ 問題文を３回読み直して気がついた。
辺 i は頂点 Xi から Yi に向かいます。
制約 1≤Xi<Yi≤N
制約が持つ情報量が多すぎて見逃していた。難しい。そして閉路が含まれてるなら含まれてるで、解説３に書かれている強連結成分(SCC)分解を手段として持っておくべきであると。
まだコンテスト期間中だけどソースコード共有の動きがあるくらいなので隠す必要はないかなと>「解説が公開されたら、ソースコードを共有していきましょう」。
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 が大きい場合、想定解法の方が遅くなる。
基本は提出１と同じ。30 ビット 60 ビットでテキトーに区切っていた最大で 10 万ビットになりうるビットフラグを、１つの Bignum にまとめた。
多倍長が許されるのは数百桁までかなと思ってたんだけど、(最大で)10万桁でもすっごく速かった。しかしメモリ制限 1024 MB を超えて 1.24 GB 使ったところで MLE。
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 頂点程度に過ぎない。桁数部分での寄与は小さい。
これは提出１、２と違って想定解法と同じ方針。ただしクエリ 64 並列ではなく 10 万並列でやっている。
DP がしたいのに Bignum を頂点の数だけ保持すると MLE になるのをどうすれば良いか。TLE を避けたいなら Bignum を使うしかないがどうすれば良いか。頂点番号の小さい順にどんどん処理を進めて、使用済みの情報は辺もクエリも遷移してきたという DP 要素もどんどん捨てていった。一時的には C 配列に処理待ちの Bignum が蓄えられるけど、どこかから遷移して来るまではそれも 0 (Fixnum) だ。
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 で満点がありだったのだなあ。道具のせいにしてあきらめなくて良かった。
メモリもタイムもさらに良くなった。提出３がベースだけど、クエリごとに１ビットを使うのではなく、スタート地点 A が共通するクエリが同じビットを共有する。
こちらを参考にして。
昨日はうしさんのライブラリを参考にして解いたため、(A_i,B_i)というクエリを処理するときにはdp[A_i]|=1<<iとしていた。そうではなくdp[u]|=1<<uとし、すべてのペアについて問題を解くことにすれば、頂点番号uに対しては1..uに対応するbitしか保存しなくてよいため、必要なメモリが\frac{N^2}2くらいになるらしい。
頂点番号が小さい順に処理をするという提出３の流れと、頂点番号が小さいものから０に近いビットを割り当てるというのがマッチして、ビットの同時使用量が節約できる。
整理したからそのまま同じではないけど、だいたいこんな雰囲気>typical90_59_nosub5.rb27
@2021-09-14 結局最後のも提出した>提出 #25841973 (1149 ms)
最終更新: 2021-06-05T05:03+0900
解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg
この問題はとても良かった。確実に力になった。問題を解く選択肢が増えた。キーワードは「行列の掃き出し法を知ろう」だって。
最初は独力でパネルを順番に見ていく DFS を書いた。それしか知らない。だけどどうしても入力に左右されるし、あるパネルに影響する複数のスイッチの組み合わせを総当たりするので遅くなる。
入力を前処理して扱いやすくするとは考えてもみなかった。
でまあ今後は、こういうことができると知ったはいいけど、これが適用できる対象の性質を見抜けるかどうか、というところに課題が移ったとみていいのではないかな。簡単ではないね。
具体的な実装にも迷いがある。スイッチ数(N)、パネル数(M)の上限が 300 なのに対して 550 ms の時間をかけている。メインループだけど、
ステップ１の処理が N で、ステップ２の処理が N×M。もっとシュッと片付くうまい書き方があっても良さそうでは？
hai!@magrofly「典型057 Ruby https://t.co/Dri1yBSvuK」 / Twitter
「基底を求める」のはよくわからないけど、「解く」過程では順番に適用していくだけでいいようだ。さっきの手順に当てはめると、基底を求めるのがステップ２に相当して、解く部分がステップ３。ステップ１の検索が不要であると。
最初の提出。無駄にソート、検索している(９行目)。
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)
ツイートを参考に改良したが、あまり良くはならない。N,M<=300 だから？ 対称差を求める部分(15行目)が富豪的過ぎるから？ 前処理の部分でまだちょっと変なやり方をしてる？
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
★２つだからってこういう素直なスクリプトを投げた。
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
競プロ典型 90 問の 043 - Maze Challenge with Lack of Sleep（★4）が普通に解けたので、Pond Skater (青diff1968)も解けるような気がした(既視感>20200826p01。根拠は必要ない)。
All AC になるまで死ぬほどバグらせた。これが時間内に解ける未来が見えない。訪問済みフラグが二値ではない。ループの継続条件とキューへの追加条件が同じではない。ループのあいだ無条件にキューに追加していると rand_20_01.txt と rand_20_03.txt の２つのケースでキューが複製要素で膨れ上がってしまう。それ以外のケースでは AC なのに。
無駄に難しくしてる？ そうであってほしい。
比較すると短いし速いし省メモリだと思う。テストケースハック(※テストケースは公開されている)らしき提出を除けば。
訪問済みフラグを水平方向と垂直方向に分けたのが間違いだったろうか。途中からフラグ(二値)ではなくなったし、紆余曲折を経て扱いが同列だし、単にコストとして再定義して書き直せるのでは？
Vh と Vv だったものを C に統合した。さらに短くさらに速くさらに省メモリになった。最初にコストでなく２つのフラグを使って書き始めたのが間違いの始まりだったのだなあ(Maze Challenge with Lack of Sleep（★4）の解き方がそうだったからなんだけど)。
最終更新: 2021-06-08T14:41+0900
解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。
ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。
話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。
実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。
一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。
これはマージしないでいいように１つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。
基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。
これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー？
確かなことはこのあたりの提出を読めばわかる。(提出の早い順)
メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。
最終更新: 2021-04-30T21:11+0900
「10分間３問早解き」回だったわけなので４問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。
AC のきっかけはこのツイート。
chokudai(高橋 直大)ナス@chokudai
D問題、非連結ですって言うだけでDiff400くらい落ちそう
chokudai(高橋 直大)ナス@chokudai
非連結ですって言っても落ちないわ（サンプルにあるし）
連結で出題しないと400落ちなさそう。
「連結で出題しないと落ちない
」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。
サンプル４つのうち２つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある？
テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。
しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。
だけど次のように番号の付け方を変えただけで問題が問題でなくなる。
たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。
ソートするにせよ先読みするにせよ、２番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。
DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p02、20201107p01.05。
最終更新: 2021-06-08T15:01+0900
昨日あった ABC。D 問題は覆面算。たまたま何か月か前に「FDCAJH × IBCFEH = FBAECIIJEGIH」というのを解く機会があったのだけど、時間制限がないせいで雑に総当たりをして済ませてしまっていた。
本番中は TLE で終わってしまった。E 問題を 15 分で片付けて戻ってきたけど、ついに通せなかった。
制限時間が大盤振る舞いの５秒なんだよね。
桁を１つ２つ減らすだけで時間がだいぶ違うだろうという予測はできたけど、減らし方がわからなかった。なんといっても目の前に文字で書かれた式があるわけではなく、色々なケースが入力されるわけなので。
TODO: Array#all? の中のテストは l<=r より l==r||l+1==r の方が厳しくて良い。
TODO: 和の先頭の桁が１だとすぐにわかる場合がある。
TODO: 列挙してから弾くより列挙しない方がいい。(確定桁が１つあったとして、未確定桁(=文字種-1)の順列の数だけ弾くのは手間だから)
TODO: ループの中の処理がシンプルになるように入念に事前準備をした方がいい。
現在 Ruby での AC 提出は 20。実行時間が 109 ms から 4845 ms までと幅広い。中央値は３秒台です。
たとえば(４桁 ms では最も速い)約 1.6 秒のこの提出>#21688714
先頭桁が０のケースを弾くと同時に、末尾の桁が一致するかどうかだけ特別にチェックしている。一致しないケースでは文字式の全体を数値化する無駄がスキップできる。このひと手間が効果的なのだと思う。
それと、全くの想定外だったのだけど、文字が 11 種類以上使われている式が入力されるケースがあったのだろうか(上の 1.6 秒の提出がチェックして UNSOLVABLE を出力している)。AtCoder の問題は入力や条件がきれいに整理されていて枝葉の手間が省けるように作られているだろう、という甘えがあるのは否めない。
３つある３桁 ms の提出が何をやっているのかは、さっぱりわかりません。
４つの TODO を意識して書いたけど、妥協した部分もある。
とはいえ、これを深さ優先探索で妥協なく書き換えただけで２桁 ms になる？ そう、Ruby で現在最速の提出は 71 ms になっている。
根本的なところで、列挙してから弾くか、可能性のある組み合わせだけを列挙するかという違いがあるのかな。そっち方面で書こうとしたときは、ある桁を見たときに未確定文字が０なのか、１個あるのか２個か３個か、未確定文字があるのはどの項か、繰り上がりはあるのか、ということを考えるのが面倒くさくなって(=脳のキャパシティをオーバーして)、書けなかったんだよね。
書けなかったのをがんばって書いた。時間は申し分ないけども１つの WA。たぶん答えがないケースだと思うんだけど……。
WA の原因は非ゼロチェックが１つ抜けていたこと。それと、想定外だと書いた「文字が 11 種類以上使われているケース」はサンプル４がそうだった。コピペするだけで全然読んでいない。
雑に総当たりしていたのを反省して(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
緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない。
だから青色。難しかったん。１年くらい前に ABC004 を埋めようとしたときは力が及ばず C 問題までしか提出に至っていなかった。
今回も一発 AC とはいかなかった。原因はすぐに推測できて、緑色が原点から離れない想定が誤っていたのだと思った。
たとえば赤か青の片方が極端に多いとき、外側に広がっていくよりも中心にある緑色の全体を移動させてでも中心に向けて移動する方が低コストになる分岐点がある。
しかしそれを想定するとコードにするのがさらに難しくなりそうで困った。
ちなみにこの提出の方針は……。赤と青をそれぞれ -100 と 100 を中心にして原点の左右で平らに並べる。原点は超えない。数が多ければ外側により大きく広がる。そのあとで緑色を原点を中心として配置していく。左右のコストを比較して赤と青を押しのけながら。
提出に至らなかった１年前の方針は、RGB の数から重心を求めて云々という感じ。ひょっとすると緑の配置拠点を原点に限らず適切に移動することで、WA だった方針のまま AC に持って行けた可能性が？
「J - 長い長い文字列」(提出 #19035422) とか、「K - 転倒数」(提出 #18029328)とか、脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい。今回は両方出てきた。(クラスのメソッドの並びが不揃いなのが気になる。左を先に書くで統一しておきたかった)
イメージとしてはビー玉をざらざらと流し込んでから、抵抗の強弱を感じ取りつつ右に左に均す感じ。最大で900個程度の広がりしか考えなくていいからなんとかなっている。
Ruby の他の提出を見るとゴルフをしていなくても 300 バイト台の短い提出がいくつもあるし、内容も、候補を並べて最小値を選ぶ、二分探索で解(極小値)を探すなど、特に大層な道具は必要としていない。それは、頭の中で十分に理解して整理できているから書けるんだよなあ。
できないからソースコード上でメソッドと複数のインスタンスに分割して整理しています。結果としてひと味違った解法になったと思う。
たぶん抗力の計算が間違ってるんだよね。
押した力を上限として０以上それ以下の力しか発生しないはずだけど、なんだか負の抗力によって隣の障害物に引っぱられていきそうになってる。それだと引っぱってる方はともかく引っぱられる方は、必ずしも安定した、低いエネルギー状態にあるとはいえなくなる。
これが問題にならない理由もわかるけど、それはクラスの外部、インスタンスの利用方法にあるのであって、クラスの、メソッドの定義としては間違っている。
最終更新: 2021-06-08T15:27+0900
ABC の４問目で 400 点問題。しかし青diffではある。
時間制限を 10 秒にしてくれたらたぶん通る。しかし実際の制限は２秒であり、３秒ですらない。慈悲はないのか。
Ruby の提出一覧を見ると AC していても軒並み１秒越えであり、処理量がしんどい問題なのは間違いないのだけど、その中にあって１秒を切っている提出もある。ということは、己の考えが足りないのである。ぐぬぬ。
入力を正負ゼロに分けて、正負ゼロの積がそれぞれいくつ作られるかをまず求めた。
負の積が K 個かそれより多いならば、正の数と負の数のペアを考える。ゼロは特に考えることがない。K 番目が正の積の中に含まれているなら、負の数同士のペアと正の数同士のペアを考える。
これで考えるべき組み合わせが多少は減ったつもりになるが、入力次第では何の足しにもならない。本質的に計算量を削減する方法がわからなかった。
それでどうしているか。
K 番目の数を -10^{18} から 10^{18} の範囲で二分探索している。
ペアを、ある数とそれに掛け合わせるソート数列として持っている。K 番目の数の候補となる数が与えられたとき、その数以下の積がいくつ作られるかは、これまたソート数列を二分探索することでわかる。
ペアの数が馬鹿にならない。N (≦2×10^5) のオーダーで存在する。だから「ある数」と「ソート数列」に注目して、ペアをソートされた状態で持っている。そうすると K 番目の数の候補となる数が与えられたとき、かすりもしないペアを予め除外して考えることができる。かすらないとは２通りあって、すべての積がある数以下となるか、すべての積がある数より大きくなるか。全か無か。ここで累積和と、三度目になる二分探索を使っている。
とまあ、こんな感じ。(３つだが三重ではない)二重の二分探索のあいだに、範囲を絞っているとはいえちまちまと順番に数え上げる線形時間の処理が挟まっているのがいただけない。一番重たいケースで 10 秒はがんばった方だと思うよ。知的方面でのがんばりではないけども。
ソート列とソート列の組み合わせでペアを作っているのに、そのときに一方のソート列をばらばらにしてしまっているのが悪いのか？ (短い方を選んでバラすようにはしている)
この回 は「C 問題が解けなくて大爆死した回の ABC」。その後 C 問題を解いて、F 問題も解いたけど、「F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？」と書いたように、F の後でも D と E が解けていなかった。不思議なもので、D 問題は緑埋めをしていた先月に普通に解いていた(提出 #21267825)。緑がほぼ埋まってきて次なるターゲットは水色下位に移ってきている。E 問題 Logs である。解けない緑より解ける水色なのである。
えー、解けました。解けなかったときは何を考えて行き詰まっていたか。
今日の日記のタイトルは「D 問題 Pairs」です。関連は？
これまで二分探索といえばソート済み配列から特定の閾値をまたぐ値を選び出すのに使用してきたのだけど、実はそれだけではなかった。何もない空中から特定の値(解)を見つけ出すのにも利用できるのだった。順序さえ与えられるなら、解が -10^{18} から 10^{18} の範囲に存在すると判っているなら、たったひとつの意味のある値(解)を二分探索してもいいのである。
という気付きが Pairs を解く過程で(まだ解けてないけど)得られていたので、今度はごく素直に、解を決め打ってから最適な切断をすると切断回数の合計が何回になるかという逆算的な解法を発想することができた。そういうことができるとわかっていた。
二分探索を使った解法でかつて最も衝撃を受けたのは Vacant Seat というインタラクティブ問題に対する提出 #2057817 と #2064531 だった。bsearch メソッドから呼び出されるブロックの中でクエリを行っている。いやね、自分も提出 #7970588 の中で二分探索を使って答えを出してるんだけど、そのことと、対象となる具体的なソート列がないまま空中で二分探索を行う、順序はクエリで動的に決定するということの間に、どれだけの隔たりがあることか。
脳みそが不自由だと存在しない制約で思考が枷をはめられてしまうのだなあ。最も基本的なツールといえる二分探索も、まだまだ使いこなせていないのだった。
ところで 350 ms は Ruby で２番目に速い提出なのだけど、どんぐりの背比べである２番目とそれ以降から頭ひとつ抜けて速いのがこの 提出 #15632506 (sushibon さん / 219 ms)。二分探索は行っていない(ソートはしている)。
二分探索というのは人間が考えることを放棄して機械に試行錯誤させる解法なのだけど、人間が頭を使えば無駄なく速く答えを求めることができるのですね。まあ、何をどう考えればいいのかわかりませんけども。
これも空中二分探索。解を決め打ってから考える。もはやおなじみである。
Ruby では唯一３桁 ms に入った(他は４桁)。log１つ分の差だと思う。Nlog^2 と Nlog。単にソートする方のやり方を思いつかなかっただけなんだけど。
同じ青diffでもこちらのほうが Pairs よりわずかに難しいことになっている。
しかしこれは簡単な Pairs ということでいいんではないか？ だって同じように二重の二分探索の真ん中で線形時間の足し合わせを行っていて、TLE にならないんだもん。
概ね 300 ms から 500 ms の間におさまっているから、自分の 1489 ms は最も遅い部類に入る。Pairs を解くヒントが(Pairs の提出一覧はもちろん)ここにもあるのでは？(だったら読むわけにはいかない)
ループの構成は変わらないまま脳筋的努力を重ねた結果、倍近く速くなった。しかし 300 ms にも 500 ms にも及ばない。やっぱり計算量のオーダーを減らす手がどこかにあるのだろう。それがわかれば Pairs が AC できるぞっ。
やったど。246 ms は Ruby では僅差で一番速い。
どこでオーダーが改善できるか。解法の根幹をなす大外の二分探索の log は欠かせない。入力をなめる N もなくせない。なら内部の二分探索を削るしかないのはわかってたんだけど、「log を削らなければいけません」「はい、削りました」ができるなら脳みそはいらないわけで……。
ヒントはこの問題の前に解いた射撃王にあった。log ひとつの差ってちょっとした違いなんですよ。ちょっと見る角度を変えるだけ……でなんとかなるなら脳みそは(略)
実際のところ、二分探索の代わりに shift/pop を繰り返すようにしただけ。
261 ms の提出を読んだ。A 数列の値から添字を得る逆引きインデックスを事前に作成するのがキモであるようだった。A の値の範囲は 10000 以下なので、それが配列のサイズとなったところで大した大きさではない。
言われてみれば、そうだね、という感じ(だけど思いつかなかった)。313 ms の提出も 328 ms の提出も 329 ms の提出も、同じ下拵えをしていた。
やったど！ たまたまぶつかった別の問題ばっかり３問片付けてきたけど、とうとう本丸の Pairs をクリアしたぞ！ (提出日時を見ればわかるけど、今日は５月の下旬なのだ。日記とは？)
これもやっぱり Handshake と同じように二分探索の代わりに shift/pop を繰り返すようにした。Pairs は Handshake と違って A 数列の値の上限が 10^9 なので、逆引きインデックスを用意しておく方法は使えなかったのではないかと思う。
ところで、ぎりぎり３桁 ms には入ったけど、759 ms には負けました。配列の操作でなく添字の操作をしているところが効いてるのかな？
最終更新: 2021-03-24T16:47+0900
解いたあとで他の人の Ruby での解答を見たらバリエーションがいくつか見られた。
これが一番多かったと思う。公式解説に書かれている通りの手順。
これは Ruby で最速の qib さんの提出 #20369253 (191 ms) の解法。
公式解説にはこう書かれている。
マス i と j の距離を d(i,j) として，マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる．結論としてマス 1 とマス N の 2 点から幅優先探索や深さ優先探索などを行うことで O(N) でこの問題を解くことが可能である．
解法１はたしかに解説通りの手順ではあるが、解答にあたり具体的な距離まで知りたいわけではなく、距離の大小関係だけ知れれば十分なのだ。
解法２の手順は(スタート地点からの距離を測定する)幅優先探索に則っているのだが、一見すると１手につき１マスしか塗れないゲームのルールに反しているように見えるのが難しい。同じことは解法１にも言えて、「マス i の色は d(1,i) ≦ d(N,i) ならば黒，そうでなければ白となる
」が納得できるかどうかに尽きるのだけど、解法２の手順がなまじゲームに似ているせいで考えてしまう。
フェネックとすぬけくんの行動原理として想定したのは公式解説のものと同じ。見立てだけが異なる。どういう見立てだったか。
フェネック(すぬけくんでもいいが便宜上フェネックを選ぶ)のスタート地点を木の根と定めて、すぬけくんのスタート地点の深さを知る。すぬけくんは移動可能範囲を広げるために根に向かって移動する。フェネックはすぬけくんの移動可能範囲を狭めるためにすぬけくんに向かって移動する。出会うのは中間の深さ。すぬけくんは根に向かって移動できなくなった地点を根としてその子孫ノードだけを塗ることができる(だから一直線に根(フェネックのスタート地点)を目指していた)。
結局のところこの問題は一本の辺を見つけ出す問題だった。頂点集合をフェネック側、すぬけくん側に分ける辺がどれかを見つける問題だった。
その手順として幅優先探索(解法１)とその応用(解法２)と深さ優先探索(解法３)とダイクストラ法(未紹介)と、いろいろな方法があって、実行速度の差があった。同じ線形時間でも１回なめるだけで済ませられるのか、２回か、３回か。
今日@2021-03-23 たまたま取り組んだこの問題が同じ方針で解けそうだった。
２地点から深さ優先探索で陣取りをしていって、中央付近でにらみ合って、それからどれだけ相手陣へ侵攻(自陣へ後退)できるかを数えれば答えになりそうだった。
きっちりと隙を見せない after_contest に撃ち落とされましたとさ。
競技プログラミングをするフレンズ @kyopro_friends
サーバル「ABC148F『Playing tag on tree』にafter_contestを追加したよ！ 不等式に等号を入れるか入れないかを間違ってるコードが落ちるようになったはずだから確認してみてね」https://t.co/jcHP4lHFhg
不等号などなかった。先攻後攻を入れ替えたのと、自陣へ逃げ込もうとしてうっかり中立地帯へ迷い込まないように道を塞いだ。
当初方針のまま after_contest に対応したが、どうにも不自然に頑張ったようなコードになってしまった。この問題に関しては、想定解法通りに２通りの距離表を見比べて答えを選び出すのが良かっただろう。
ところで ABC148 はオンタイムで参加していた。A-D まで灰 diff で、E 問題に至ってもギリギリ緑という低難度回。F 問題でやっと水 diff 中位だったらしい。当時１時間を残していながら解けなかったのがこの F 問題。何を考えて解けなかったか。
木の上で追いかけっこをする２人がすれ違うことができない、ということが認識できていなかった。だから偶奇が適切な部分木を選んで逃げ込むことで追跡が躱せるような気がしていた。それじゃあこの但し書きが嘘になるのにね。「なお、ゲームは必ず終了することが証明できます。
」 そんなん考えたら青 diff 上位の「DFS Game」より難しくなるってのにね。
最終更新: 2021-03-15T22:56+0900
本日の ABC。１時間かけて ABCD の４完で、残り40分考えて E 問題が解けずに終わった。ゲーム問題苦手。勝ち筋とか必勝法とか、さっぱり見えない。「自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。」
本番中に E 問題が行き詰まっている最中に F 問題をタイトルだけチラ見していた。Coprime の単語が見えた瞬間にあきらめた。別の問題だけど先々月に「Coprime はまた解けなかった。」 完全に苦手意識を持っている。素数とか見たくない。
割と大きめのサンプル３が通ったのでいけると思ったが TLE だった。
考えたことを順番に。
このとき(緑diff精進３問)解いた問題の１つが「ABC 115 D - Christmas」なんだけど、素直に問題の通りに書いた最初の版が明らかに TLE を免れなくて、ださいけど if を使って２回の再帰呼び出しを１回に節約するパスを追加することで AC になっていた。
倍倍ゲームになりうる再帰構造には特別な警戒が必要だということと、それが反転したときに改善効果が劇的だということを学んでいた。今回も最後の lambda F に２行追加して AC。
たぶんグループの作り方が間違っていた。二次ペア三次ペアと芋づる式に相互グループを作るのでなく、それぞれの数ごとに一次ペアのグループを作って、そのサイズでクラス分けをすれば、計算で答えが求まったのではないか。計算の材料にする数字が誤っていたから求まらなかったのではないか。いやでもそのクラスには公倍数の情報が抜けてるのか……。
組み合わせた結果をフィルタリングするよりも、フィルタリングした結果を組み合わせるべきだったのではないか。SQL がそうでしょう？ JOIN する前に WHERE で絞るべきなんだ。WHERE に似ていても HAVING では遅いんだ。
全探索がダメでもある種の探索が許されていたあたり、今日の制約には優しさが感じられるなあ。
これに関連した @kyopro_friends さんのツイートを考えていた。
競技プログラミングをするフレンズ @kyopro_friends
アライグマ「F問題は、COLOCON2018C『すぬけそだて――ごはん――』の難しい版なのだ！ gcd(x,y)=gcd(x-y,y)≦|x-y|だから、72以下の素数の倍数が重複しないようにすればよくて、どの素数の倍数をもう使ったかでbitDPすればいいのだ！」
「
」ってつまり……gcd(x,y)=gcd(x-y,y)≦|x-y|
というような発見があった。ものがよく見えていないと「新発見」が多い。ユークリッドの互除法まで見つけてしまった。開拓者か研究者に向いているのではないか。
最終更新: 2021-03-23T20:00+0900
解説を読んで ABC をコンプリートしようシリーズの１回目。ABC192 で残っているのは F 問題。いわゆるポーションって portion とはスペルが違ったのね。
２回目があるかはわからない。１回目にして解説を読んでから２日間苦しんだ。DP だったんだけど、人類が扱うには次元が高すぎるのではないかな？ 自分には無理。
ソースコードの冒頭にも引用したけど、解説の要諦が次の一文。
dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod C で k に等しいようなものの最大値
自分は最初これを次のように解釈した。
dp[i][j][k] = i 番目までから j 個選んだときの和であって、mod j で k に等しいようなものの最大値
微妙な違いがわかりますか？ mod C と mod j の違い。うっかりミスではなく、理解できる範疇を超えていたから、これってこういう意味だよね、と一段次元が低い誤った理解しか生まれなかった。
引き回すデータ配列の構成を教えてもらってさえ遷移が書けるまで一日かかったんだけど、いざ完成したらこの微妙な勘違いのせいで時々答えが合わなかった。時々。答え合わせに使ったのは次のナイーブな解答スクリプト。N が 30 を超えると実行時間が現実的でないので生成する入力の N は小さめに。テストケースはまだ利用できない。
N,X,*A = $<.read.split.map(&:to_i)
p (1..N).filter_map{|c|
k = X%c
m = A.combination(c).map(&:sum).sort.reverse_each.find{|m| m%c == k }
(X-m)/c if m
}.min
要するに、これを時間制限に収まるように書き直しましょう、という問題だった。それが難しい。
結局一度完成したと思ったスクリプトを囲うようにもうひとつループを重ねた。法が変わると余りは再利用できない。最初から目的地(C)を定めて j を変化させなければいけない。dp 配列の添字 k の上限は j でなく C である。無理だよ、明日にはもう自分でこの文が理解できないよ。
DP であることでナイーブな解答より有利になる点は次の２つ？
j+1 個の組み合わせを生成するのに j 個の組み合わせ結果が利用できる。
その際にキーとなるのが添字 i (「i 番目までから j 個選んだときの和であって
」)。j 個の組み合わせ結果を i (1～N-j)によって分類しておくことで、j+1 個の組み合わせを作るのに利用できる。
たぶんこれって DP のひとつの典型なんだと思うけど、配列の型を示されてさえこの種の遷移(何を残して何を再利用するか)を見つけるのに１日かかった。
見つけた遷移は具体的には、「j を C まで増やしながら、ある j について i 番目の要素(A[i])を i の大きい順に考える。A[i] を採用しないときに dp[j][i] に対応する C 要素の配列は dp[j][i+1] のものと同じ。A[i] を採用するときは dp[j-1][i+1] に記録された C 個の値と組み合わせる」 i と j が解説とは入れ替わってら。
dp[j][i] の値を作るのに dp[j][i+1] (最内ループの直前の値)と dp[j-1][i+1] (中間ループの直前の値の１要素)を再利用している。
勘違いして見えていなかったのは、j=C であり j を 1..N の範囲で変化させる過程で各 j(C) に対応した答えが見つかる……のではなく、C=1..N について j を 1..C の範囲で変化させなければいけないということ。
提出 #20486969 (TLE×11)
主にイテレータを使って書き直したので遅くなるのはわかる。
Array#min の代わりに Array#[] でダイレクトに最小値を取得するようにしたので、special_xx.txt 以外のケースでは改善している。
提出 #20486969 (TLE×11)
同じように Array#min を使うのをやめたのと、イテレータを使わず全て while で書いた。special_xx.txt 以外のケースで上よりさらに少し改善しているが、TLE は TLE。
Ruby って整数演算が足す引く剰余大小比較まで、どれも同じくらい遅い雰囲気。演算コストに差がないなら演算子の数を減らす方がいい？
でもどこに 800 ms も遅くなる要因があった？ もう予測できない。
平均すると最初の提出より１割弱タイムが改善しているけど、意味のある差ではない。
ベースはイテレータメインの提出 #20486969 (TLE×11)。
AC と TLE の分かれ目は４重ループの最深部にあった。
初期値を正の無限大ではなく nil にした。
正の無限大は正常値として扱えるので記述が統一できるのだけど、むしろ異常値として nil や -1 や無限大を設定・検知して、ループをスキップするのが良かった。
ところで、想定上限を整数で表現しようとすると 67 か 68 ビットが必要になる気がして採用できなかった。Float::INFINITY と Bignum の、どちらがいいともいえない。打ち切り条件が ×C ではなく ÷C である理由でもある。
k = m%c や k-=c if c<=k よりも、「実行されないコードが最速」なのだった。負の添字を使った配列参照は組み込まれた機能でありコストは支払い済みなので、使い倒さなければ損になる。いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか。数列 A の偏りと C の組み合わせを調べれば、k が取り得る値が C 種類より少なくなるのを見抜けるのではないか。結局のところ、TLE の原因はおそらく X%C と A%C(の和) がまったくマッチしないせいで４重ループを最初から最後までフル回転させられるせいだと思うから。
「いくつかの C について最小公倍数で余りをとれば、より外側のループで DP 配列が再利用できるのではないか」を実装してみた。話を単純にするために C が偶数の時に j=C/2; i=0 の DP 配列を C=C/2 の DP 配列として再利用した。
たとえば N が上限の 100 のとき、51..100 は普通に DP をする。1..50 は再利用配列を使用して DP をしない。限界は次の２点。
| ケース | X | X (素因数) | A に含まれる 9999999 の数 | 答えが見つかる C |
|---|---|---|---|---|
| special_01.txt | 52142908377193267 | 103×4703×107642319563 | 0 | 1 |
| special_02.txt | 48620189947792921 | 131×2719×18713×7294453 | 1 | 2 |
| special_03.txt | 702276810747319237 | 702276810747319237 | 2 | 3 |
| special_04.txt | 651020109319638361 | 162011×231599×17350549 | 3 | 4 |
| special_05.txt | 611688502818504841 | 82936769××7375359689 | 4 | 5 |
| special_06.txt | 85741517196073082 | 2×11257×32587×116867599 | 5 | 6 |
| special_07.txt | 794433313787770441 | 101×74910361×105001181 | 6 | 7 |
| special_08.txt | 515779426304609041 | 101×5106726993114941 | 7 | 8 |
| special_09.txt | 896297933758956951 | 3×22769×13121611749293 | 8 | 9 |
| special_10.txt | 90842952249996662 | 2×24335153×1866496427 | 9 | 10 |
N はすべて 100。数列 A の要素はほとんどが 10000000 で、０から９個が 9999999 という構成。
special_xx.txt が入力する数列 A の中に値の種類は１から２個しかなかった。C 個選んだ和の余りがとる値は、限られた 9999999 がいくつ含まれるかでしか違いが出なかった。つまり１から10種類。それでも C が 1..N の範囲で変化するうちに余りの数字(k)自体は変化していくし、X%C も変化するんだけど、どうやったらぎりぎり最後までマッチングしないような X が選べるんですか？