■A - Alloy
書いてるとおりに場合分け。
SliverのタイプミスでWA
■B - Weak Password
書いている通りにやるだけ。
■C - Min Difference
尺取法、だけど面倒なのでlower_bound
一番賢い方法はaかbかの情報をもたせてsortし
隣接のabが異なるとこの最小を出力。
■D - Querying Multiset
操作3を見る限り、priority_queueが必要。
面倒なのは操作2
全体にaddするものは別に持っておけば良い。
■E - Safety Journey
制約を眺めると、使えない道のほうが圧倒的に少ないので
いったんすべての道が使えるものとして遷移させ(dp[i+1][j]=Σdp[i][j])
だめな部分を引く。
■F - Greedy Takahashi
コンテスト中は一読して、飛ばしました。
イベントソート+dsu
イベント管理をする上で面倒なのは、
バスの乗り降りと、それぞれのクエリの高橋くんの行動時間がぶつかる場合。
時間を適当に、
乗車x->3x+2
下車x->3x+1
クエリx->3xとでもすれば良い。intで管理するとoverflowに注意
あとは時間順に処理しつつ、dsuで丁寧にリーダーを管理しつつ、マージを丁寧にやる。
■G - Power Pair
原始根。
x^(p-1) = 1 mod p (0<x<p)
なので、xの最小サイクルはp-1の約数になる。
あとは約数列挙して適当に。
■H - Nim Counting
xor畳み込み。
xor畳み込みが既知なら山の数が固定なら、繰り返し二乗法で解けるのはわかる。
問題は、山の数が固定でないこと。
これは工夫することで、n個以下の山で、xorがiになる通り数のdpを持てばいい。
具体的には
dp0[i][j] = i個丁度の山で、xorがjになる通り数。
dp1[i][j] = i個以下の山で、xorがjになる通り数
とでもすれば
dp0[2*i][j] = dp0[i][j] * dp0[i][j];
dp1[2*i][j] = dp0[i][j] * dp1[i][j] + dp1[i][j];
とすれば良い。
後半の式の意味は、山の数がiより大きいとi以下で分けて考えてる。
xorに限らず、何が畳み込めて何が畳み込めないのかと使い方は把握しといたほうが良さそう。
把握さえしとけばコピペでAC出来るだろうし。
oooooxoxの6完でperf2300超え
黄色まであと70。
arc125までの3回のabcで決めたい。
とりあえず8問abcの戦略としては500easyまで解いて
順位表を確認し、解けそうな問題に突っ込むが最適？
実際、ooooooxxxでもperf2000は出るわけだし。
