.tr.to_i+.tr.to_i (@2021-06-28 .to_i 一発(相当)で計算できるこんな言語もあるらしい。「2001を2進数で解釈するというのは通常だと意味が通らないが、dcにおいては構わず2×2^3が使われる」)■今日はこの他に取りこぼしていた「045 - Simple Grouping（★6）」を Ruby で通しておいた。組み合わせの総当たりが bitDP でできるというのは初めて知った。Avoid War がまだ通せないとは 20210622 で書いたけど、そのときに覚えた部分集合の列挙をビット演算で行う方法(蟻本に載っていた。144 ページ)がさっそく使えた。１つのケースだけ 20 秒くらいかかって TLE になるので、その場合だけ別の方法で答えを出すなど>#23710778 (1087 ms / 同じ内容)。□わずかな時間を削るためにいろいろと猪口才なことをしている。配列の配列を作るときに長さ14で2^{15}個のインスタンスがいいか長さ2^{15}で14個のインスタンスがいいかとか。２点間距離をメモした D 配列がそのまま DP 配列(E)の初期値であるとか(だから本当は３ビット以上立っている数に限って列挙したい)、DP 配列のその他の初期値が最大値ではなく 0 でいいとか、それによって中間ループを K 回回さないで済んでるとか。ループの中で最初から最後まで使われている d 変数の初期化が実は１回だけですよとか。最内ループの C if A && B が多少冗長ではあるがコストの順に並んでいて総合的には得するだとか(少なくともローカルでは)。しかし、点を一列に並べて端っこから２番目の点を無き者にしてループの指数を１減らす試みは失敗した。x^2-1 の(用語不明)が x^3/3 だから、1 と -1 を……どんな式に代入するのか思い出せない。1^3/3-(-1)^3/3 だと思ったけどそれだと 2/3 なので、4/3 (図中)でも 1/3 (訂正ツイート)でもない。■ところで、錐体っていつ習う？ 覚えがない。■ X 軸を無視してるのが良くない気がする。つまり、斜線部っていうのは二次関数だけでなく X 軸と組み合わさってできあがってる範囲なわけだから……(で、どこをどう修正したら 1/3 になる？)。■謎は全て解けた！ x^2-1 の(用語不明)は x^3/3 でなく x^3/3-x だ。微分のつもりで定数項を捨ててはいけない。で、これに……？■ X 軸に沿って積分をする。\int_{-1}^1 dx が幅。高さにあたる値は y=0 と y=x^2-1 の差であり、y=0 の方が範囲内では上だからこう 0-(x^2-1)。面積は縦×横だから \int_{-1}^1 [0-(x^2-1)]dx。(用語不明)して 1 と -1 を代入して、-(1^3/3-1)--[(-1)^3/3-(-1)] = 2/3+2/3 = 4/3。だいぶ思い出したのではないか。1/3 との訂正ツイートは違う部分を訂正していたものと思う(よく見たら 1/3 は「体積」だってね)。最終更新: 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）の解き方がそうだったからなんだけど)。
