/ 最近 .rdf 追記 設定 本棚

脳log[2021-06-20~]



2021年06月20日 (日) Ruby で AtCoder をやってるとよく見かける名前と同じ人が Ruby に速度改善パッチを投げていた(ということに気がついた)。え、すごい。これで Ruby で勝てる(そういう話か?)。


2021年06月18日 (金) 「左の問題を中2に出したら3分後に右の解答が返ってきて絶句した https://t.co/hFaGZQbc3j」 / Twitter」■あかん、定積分わからへん。えっ、それだけの情報で面積求まるの?っていうのが最初の感想。範囲が -1 から 1 までってわかるのに気がついて、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月17日 (木)

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

[AtCoder]競プロ典型 90 問035 - Preserve Connectivity(★7)

解説はこちら>解説1解説2解説3

 LCA とダブリング

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

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

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

そこでダブリングです。

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

間違えた(TLE)。

A = [ps=P.dup]
(D.max-1).bit_length.times{ # 1世代上はすでに P としてあるので、1回分繰り返しが無駄かも。
	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 配列に事前に親、親の親(2世代上)、4世代上、8世代上、とメモしておいて、Ans 関数(Ancestors の略ったら略)で「a の dd 世代上は?」という質問に対数時間で答えられるようにした。Ans 関数がこのようなインタフェースになっているのは、LCA を経由した2頂点間の辺の数を求めたい呼び出しもとで「同じ深さにある2頂点 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 にならないこともある。

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

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]]
}

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


2021年06月16日 (水)

最終更新: 2021-06-21T21:06+0900

[AtCoder]競プロ典型 90 問068 - Paired Information(★5)

すごく難しいです。答えの出し方に確証が持てないまま、とりあえずグラフとして解答を書いた。クエリ0に応じて辺を追加する。クエリ1に応じてノードの値を確定しながら X から Y までグラフをたどる。しかし TLE。

 提出 #23506723 (TLE×10 / AC×3) ※まだコンテスト期間中でありアクセスできないのでこっち>提出 #23506723.rb27

次にクエリ0では Y=X+1 だという制約を思い出して、グラフを配列上に配置した。しかしこれでは多少効率が良くなれど TLE は解消しない。制約はノード数(N)、クエリ数(Q)ともに上限が 10 万であり、1つのクエリに答えるのに線形時間をかけることができない。

局所の変更を全体に(対数時間で)波及させるのに BIT がまず浮かぶ。何を記録しようか。階差の累積値かなと思った。つまり、連続する3要素 A,B,C があり、2度のクエリ0によって A+B=S, B+C=T であるとわかっているなら、C-A=T-S から1つおきの2要素の差が直接にわかる。これの累積を記録しておけば、クエリ1で 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 へ至る異なるパスがクエリ0によって与えられたときにどうすればいいかわからないでいる。定数時間で答えるためにどのような情報の持ち方をしておけばいいのか(グラフは 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 全乗せ版)。頭が整理されたところでバグまみれを捨ててイチから書き直したのが良かったと思う(それからもバグらせたんだけど)。

	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 のすっきり解法は遠くから拝むだけにしておきます。

 https://gist.github.com/masa-aa/4be96f053457dc60625a3552288fb1e4 (masa_aa さん / PyPy3 / 304 ms)

これも重み付き UnionFind。ノード番号の偶奇を利用すれば別途偶奇の管理をする必要がないらしい。クエリへの応答部分でだけ偶奇を気にすればいいというのがよくわからないが、たぶんこれを考えた先に Nachia さんのサイズ 2N のグラフがあると思う。

偶奇を一体でぐちゃぐちゃ扱う(自分)→偶奇に前提をもうけて整理されたグラフを作る(masa_aa さん)→偶奇と奇偶を並行させて偶奇の別を気にしない(Nachia さん)、という違いなのではないか、という印象を持っている。

あ find メソッドで再帰呼び出しをしていない。スタックオーバーフローのおそれがないのはいい。

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


2021年06月12日 (土) 競プロ典型 90 問 065 - RGB Balls 2(★7)」■サンプル3で7億回ループする提出を投げた。実行時間はお察し(桁が2つ多い)。部分点 3+2。ここからは問題をとらえ直す別のフレームが必要な感じ(=全然わかんないって言ってる)。■■■解説2of3「しかし、この考察だけだと満点が取れません。次にどうすれば良いのでしょうか。」自分「はい、どうすればいいですか?」解説3of3「キーワード:畳み込みを知っていますか?」 名前は知っている。FFT 怖い(未知のものへの恐怖)。『これなら分かる応用数学教室』という本を持ってるだけは持ってるんだけど、16年間積んでいる。よっちゃんいかの人がおすすめしていたときに買った。

最終更新: 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 問題にもフィボナッチ数が現れていたらしい)。あと、計算途中で1を足すという行為が、新しい系列のフィボナッチ数列を開始すること、それらずれたフィボナッチ数列を串刺しにした和が数列として現れるということもあまりピンとこない。そうなの? そんなこと漸化式を見てわかる? 足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。

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

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

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

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

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

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

 提出 #23379741 (AC)

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

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

それもダメ? [[実数の二分探索・三分探索はループ回数を決め打ちしようね - えびちゃんの日記|https://rsk0315.hatenablog.com/entry/2020/04/29/155009]]。探索範囲が過大(過小)な値に寄っていったときに、浮動小数点数の密度が足りなくなって無限ループする? 無限ループしていないことをもって OK としていい?


2021年06月10日 (木) 競プロ典型 90 問 062 - Paint All(★6)■これは知識が問われないという点で好き。体感は★4つ。直近の ABC-D (解けないくらい難しい)より易しい感じ。問題の設定が人工的ですごく頭に入りづらいのが苦労するけど、「白いボールが1つでもないと黒く塗れないのに、全部を黒く塗るには……」というところに気がつければ十分。あとは経時的に見て「塗れる→塗れないの2つの状態しかない」とか。


2021年06月07日 (月)

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

[AtCoder]競プロ典型 90 問059 - Many Graph Queries(★7)

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

この問題はとっかかりがなくて最初から解説を読んだ>解説1解説2解説3

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

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

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

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

制約 1≤Xi<Yi≤N

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

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

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

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]]
}

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

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

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

 解説と違う点

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

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

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

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

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

基本は提出1と同じ。30 ビット 60 ビットでテキトーに区切っていた最大で 10 万ビットになりうるビットフラグを、1つの 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]]
}

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

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

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

これは提出1、2と違って想定解法と同じ方針。ただしクエリ 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 で満点がありだったのだなあ。道具のせいにしてあきらめなくて良かった。

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

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

こちらを参考にして。

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

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

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

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


2021年06月04日 (金)

最終更新: 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. 取り出したスイッチを押したり押さなかったりする(最も左のビットが立っているスイッチはこれ1つだけなので確実にどちらかを選べる)
  4. 繰り返し

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


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

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

 549 ms

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

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行目)が富豪的過ぎるから? 前処理の部分でまだちょっと変なやり方をしてる?

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)

★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 では解説が役に立たない。★6~7相当のより高速な解法があるというから、そちらを解説してもらわねば。


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×190≤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 となるか。たぶん1つに定まらないのではないかと思う。ここで詰まった。


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 170F 問題 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 の2つのケースでキューが複製要素で膨れ上がってしまう。それ以外のケースでは AC なのに。

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

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

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

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

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

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


2021年05月31日 (月) クマのプーさん病理テスト」やった。結果はルー(77%)だって。知らないなあ。よく見ると、誰にも当てはまらないのが当たりなのか(はずれキャラしかいない)。もちろんはずれで何の悪いこともない。マイペースで几帳面だと解釈して何の問題もない。■質問の中には回答者自身よりも環境に答えが左右されるものがあった。それはどうなのか。自分は周囲の人間に恵まれてきたのでそれを反映した答えになるよ。あと現状の認識ではなく未来への願望を問う質問もあった。べつにどうにかしたいと思っていないので、当てはまらないという回答になるよ。


2021年05月29日 (土) [AtCoder] 今週 ABC ないの?ってツイートを見かけて、えっ直前になって消えたの?って atcoder.jp を確認したけど消えていなかった。明日ある。そのうち ABC が2回ある週が来るね。■ちなみに今日は ARC があった。ARC の AB 埋めをすべきときなんだよなあ(B 問題が解きたいです)。


2021年05月28日 (金) 好き。「【MV】GIRI-GIRI borderless world / LizNoir 作詞・作曲・編曲:Q-MHz【IDOLY PRIDE】 - YouTube」 特にこっち。「【IDOLY PRIDE】第11話 LizNoir「GIRI-GIRI borderless world」 - YouTube


2021年05月27日 (木) 全部で 10 程度しかチェックしていないのに何か所かでリツイートされていたパズル。「「Twitterでたまたま見つけた、日替わりのカレンダーパズル。 天才が作った臭がプンプンする。 なかなかに難しかったが今日の分をクリア。 https://t.co/j9blzcV2tV」 / Twitter」■興ざめなのは承知の上で、箱入り娘も解いたことだし(20210121)、このパズルもコンピュータに任せて解いてみた>a-puzzle-a-day.rb27。ひとつの日付に対して何通りも答えがあるみたい>num_of_answers.txt。特に難しそうなのは10月6日(7通り)と4月6日(8通り)。しかし、解くのはともかく、作る方は何を考えれば可能になるというのか。■「Makuake|「最近記憶力が落ちたかも…」そんな人に贈る毎朝1回のパズル習慣で楽しく脳に刺激を|マクアケ - アタラシイものや体験の応援購入サービス」 ここによると1つの日付につき答えが最低で7、多いと 200 以上あると書いてある。7と 216 だとしたらスクリプトは間違ってなかったっぽい。でも答えの合計は 25061 であり 12 万通りもなかった。表裏同型とか回転対称を区別してカウントすると、ってことでいいだろうか。まあ、マーケティング的な動機による? でも表裏同型が3ピースで、表裏を別とすると 25061×8=200488 通りになるから、キリよく「答えは 20 万通り以上」になるはずで、数え間違えてる? あり得ない日付(2月30日とか)を除外しても答えの合計は 24405 であり 195240 だから疑念は解消しない。月月、日日などカレンダーとしてはありえないけどとにかくピースが枠に収まる組み合わせかとも考えたけど、59787 通りであり半分以下。謎は解けない。バグか?■解のない日付が生じる別バージョンが紹介されていたのでそのボードもスクリプトに足しておいた(1 をコマンドラインオプションにして実行する)。その場合の解の個数>num_of_another_answers.txt。答えが0なのは3月14日、7月1日、7月3日、11月7日の計4日だと出た。■空き部分を埋める1マスのピースが2つあると考える。この2つを区別し、なおかつカレンダーとしてはありえないどの位置にきても構わないとする。そうすると先に挙げた 59787 の2倍、およそ 12 万通り(119574 通り)が解となる。そういう解釈でいいだろうか。(考えていたのは数字の意味ではなくて全探索に頼らない効率的な探索。少なくとも日付ごとに全探索する現状よりは、ピースを2つ加えて一度だけ全探索をする方が早いのでは?)


2021年05月26日 (水) アクセシブルじゃないクリックイベントを発見する」←これはキーボードで操作できない onclick ハンドラの話だけど、最近ラジオボタンに関するブラウザ(Firefox ESR 52.9)の微妙な反応の違いに気がついたよ。■「ラジオボタン スタイル」で検索すると <input> を隠して <label> で装飾する方法がいくつものサイトで紹介されてるけど、隠し方次第で問題が出る。出た。紹介されていたのはどれも <input type="radio"> を display: none で隠す方法。これだと自分が使っているブラウザではキーボードを使ってグループ化されたラジオボタンの間でフォーカスを移動させることができなかった。ラベル要素をクリックすることでしか切り替えできなかった。これも「アクセシブルじゃないクリックイベント」のひとつ。■ラベル要素はクリックに反応してラジオボタンにフォーカスを移すけど、それ自身がフォーカスを受け取ってキー入力を処理することはない。しかしでは当のラジオボタンは……。規格は知らないけど、非表示(display:none)のラジオボタンは無効(disabled)ではないからチェック状態の設定・参照が問題なくできるけど、フォーカスを受け取らないから操作に支障が出る、という理解でいいだろうか。結局 opacity: 0 で隠した。これならキーボードで操作できる。透明で見えないけど存在している ⦿ のために生じる微妙な空間は無視できる程度だったのでそのまま。■だけど今時は(7から顕著なのを知っているが)、Microsoft の Windows でもキーボードアクセスが蔑ろじゃない? 括弧で囲われたアクセラレータキーはどこ行った? その一方で「Windows 10 の起動時に自動的に実行するアプリを追加する (support.microsoft.com)」方法に shell:startup と入力させる手順があるの、ほんとバカだと思う。