Endagorion回は質が高い(+相性がいい(のに微妙な順位に・・・))
A
そんなに自明じゃない
答えXを決め打つと、二冪をちょうどX個使ってn-pXを作る問題になる。
Xを小さい順に試し、
p>=0で、n-pXが負になるとダメ
popcount(n-pX) <= X <= n-pXならOK
2 以上の二冪 b は $ b/2+b/2 と 2 つの数の和に分解できるので n-pX 個までは自由に増やせる
B
素因数分解して、肩をmod kすると、相方が一意に定まる
C
曲がると、今の進行方向にあった岩は以降に影響を与えなくなる
曲がるまでを1セットにして適当にDP(累積和っぽい感じで高速化をする)
D
逆の操作(vの子a,bを選び、aをbの子にする)を繰り返して一直線にする
一直線=「最も深い頂点の深さがn」
1回の操作で深さのmaxは高々1しか変えられないand必ずそういう操作があるので、操作回数はN-深さのmax
構成は、次数が 2 以上かつ片方が深さmaxの頂点を含むような頂点を見つけてつなぎ替えるを繰り返す
根から順にやれば楽
思いつき方
木を括弧列で表して、(が +1 で)が -1 な折れ線を書く
すると操作がヤング図形の下段か左列を 1 つ削る操作になった
つまり原点に最も近い点までのマンハッタン距離が最小手数
原点に最も近い点=深さ最大の頂点に対応する場所、となり分かった
正確には子の順番を並び替える操作もできるが最小手数は変化しない
E
$ Σa_i/k^{x_i} = 1が成り立つような x を求める
これが無ければ自明にダメで、ある場合の構成を示す
code:E.rb
S = {}
for j = max(x)...0:
while S が k で割り切れない数を含む:
a,b = S から k で割り切れない数を 2 つ取り出す # ← (ア)
a,b を出力
S に a+b を追加
S の要素を全て k で割る
(ア) の部分で k で割り切れない数がちょうど 1 個であるケースがあると困るのだが、
S の和が k の倍数であるはず(行間は自分で埋めて)なことを考えると起こり得ないことが示せる
最後に、x の求め方は、
dp[i][j] = 集合 i を使って $ Σa_i/k^{x_i} = jに出来るかどうか
j のmaxは$ Σa_i = 2000
遷移は、「1個追加」と「j /= k」($ x_iを全部インクリメントすることに対応)をBFS
復元のためにprevみたいなのを持つDPをすると、MLEするのでbitsetとかで取って、遷移は毎回試しながら復元しよう
TLEするので高速化しましょう
i の昇順にやればBFSせずにできる
さらに、Nかかってる遷移のところをビット演算でやれば/64できて爆速
ちなみに max(x) は k = 2 で a = {1,127,127,....} のケースとかで 105 くらいになり得る
F
問題文はシンプル。あまり考えてないけど難しそう。
行き過ぎてから戻ったほうがいいケースとかあるし。