最終更新: 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）の解き方がそうだったからなんだけど)。
display: none で隠す方法。これだと自分が使っているブラウザではキーボードを使ってグループ化されたラジオボタンの間でフォーカスを移動させることができなかった。ラベル要素をクリックすることでしか切り替えできなかった。これも「アクセシブルじゃないクリックイベント」のひとつ。■ラベル要素はクリックに反応してラジオボタンにフォーカスを移すけど、それ自身がフォーカスを受け取ってキー入力を処理することはない。しかしでは当のラジオボタンは……。規格は知らないけど、非表示(display:none)のラジオボタンは無効(disabled)ではないからチェック状態の設定・参照が問題なくできるけど、フォーカスを受け取らないから操作に支障が出る、という理解でいいだろうか。結局
opacity: 0 で隠した。これならキーボードで操作できる。透明で見えないけど存在している ⦿ のために生じる微妙な空間は無視できる程度だったのでそのまま。■だけど今時は(７から顕著なのを知っているが)、Microsoft の Windows でもキーボードアクセスが蔑ろじゃない？ 括弧で囲われたアクセラレータキーはどこ行った？ その一方で「Windows 10 の起動時に自動的に実行するアプリを追加する (support.microsoft.com)」方法に shell:startup と入力させる手順があるの、ほんとバカだと思う。最終更新: 2021-06-08T14:41+0900
解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。
ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。
話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。
実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。
一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。
これはマージしないでいいように１つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。
基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。
これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー？
確かなことはこのあたりの提出を読めばわかる。(提出の早い順)
メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。
3が1より小さいなら、3は10より大きい」。命題(P ⇒ Q の Q)があからさまに偽だからこの偽の命題を成り立たせる(P 以外の)隠れた条件は何か、という風に逆転した論理を自動的に考えてしまうのだと思う(生存戦略。ヒトは全知全能の神ではないが、無知の知ぐらいはある)。そうなるともう何もわからない……。■種明かしを読めば Ruby で空配列に対するクエリ
[].all? が(どんなブロックを与えても与えなくても) true を返すのと同じだと理解できる。■これには疑問>「最後の「3が偶数なら、4は奇数である」が正解多数だから1の"P が偽ならば、Q の真偽にかかわらず「P ならば Q」が真である"は理解してる人が多い」。 偶奇って正負、陰陽、表裏、左右と同じでペアのそれぞれにアイデンティティがあるわけではないので、「３が奇数なら４は偶数だし、３が偶数なら４は奇数」というように納得して正解の選択肢を選ぶことができる。しかしこれはさっき書いた逆転した論理。自分のように偶奇の性質によってたまたま正解が選べただけの人がいるのでは？■■■@2021-06-23 今日読んでいた本『『詭弁論理学』(野崎 昭弘 (著) / 中公新書)』の 171、172 ページにちょうど書いてあった。「
『もし Q ならば、Pである。』と『P でない。』とは、どちらも正しい(ことがありうる――Q でないことが結論される)ので、矛盾とはいわないのである。『もし Q ならば、P である。』と『もし Q ならば、P でない。』とも、Q が起こりえない状況においては、『Q でない』ことが確認されるだけで、矛盾ではない。」
git checkout -b myBranch 本家/master、git push -u myGitHubRepo myBranch、git rebase 本家/master [myBranch] というフローで作業をするために、「自分のではないリモートリポジトリへのプッシュをできなくする」「
新しく作成したブランチが自動的に設定する、分岐元との繋がりを断つ(--no-track を既定値にする)」という下準備をローカルリポジトリで行っていた。そもそも「
(クローンしたなら)リモート名 origin を削除する。余計な自動化も自分が管理しない名前もない方がまし」という考えによってリモート名 origin が存在しなかった。■だって origin ってリポジトリ名なの？ ブランチ名なの？ 本家なの？ フォークなの？ そういう曖昧なものの上で作業をしたくない。ましてそれ(origin)が他人(git)のお膳立てなら、助けではなく余分な複雑さを持ち込むようにしか思えない。定型のタイプの繰り返しに倦んできた頃に提案してくれたなら考えないこともない……かな？ それでもやっぱり自分は pull は使わないので(許容できるのは checkout や add までであって、自動で merge/rebase は乱暴だ)、origin もいらないんだよな(本家リポジトリにはその代わりにわかりやすい名前を付けます。「
ブランチ名とひと目で区別できるように、リモート名は @ を付けたり大文字にしたりしようかな」)。■自分にとって３つのリポジトリの関係は「本家―ローカル―フォーク」として捉えられている。でもひょっとしたら「本家―フォーク―ローカル」の想定もあるのかもな、と考えてみた次第。でも自分で GitHub にフォークリポジトリを持たなくても「本家―ローカル(フォーク)」の２者間でもフォークは成り立つので、中心に GitHub 上のフォークリポジトリを置くのは、GitHub の中の人の立場としてならともかく、個人としては順序が違うと思う。メンタルモデルはひとつで十分だ。そのとき GitHub 上のフォークリポジトリは３番目に位置するオプショナルな存在となる(だから意識しなければこれを忘れる>「
フォークする。プルリクエストを出すためには GitHub 上でフォークしたという事実が大事」 新規作成した空のリポジトリにプッシュしても PR は出せないのである)。■しかし GitHub のアップデートによって今後は、GitHub と origin を必須の前提として作業フローからリモートの区別・存在感を消すのがある種最適な選択になるのかもね。本家とフォークの２つのリモート名を使い分ける必要がなくなるのなら、単純化がなされるのなら、割り切りによる制約がむしろメリットと感じられる人もいるだろう。さもなければ無駄に複雑化して面倒なことをしているなと自分は思います。