最終更新: 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)