ARCの難易度バランスを最考してほしい
result:ooox--
rateing:1864->1866
■A - Floor, Ceil - Decomposition
基本的に分割したほうがいいのは
x*xと2xの大小関係と
x*(x+1)と2x+1の大小関係から明らか
具体的には1,2,3は分割するべきではないが、それ以外は分割したほうがいい。
ここまでわかればメモ化再帰
■B - Sum of Three Terms
a0=x,a1=y,a2=zとでも置くと、
a3以降がx+α,y+α,z+αの形でおける。
それぞれをが負にならないようにx,y,zに下駄を履かし
x+y+z=s0に成るように下駄をはかす。
下駄を履かせられないならNG
■C - XOR to All
手元で実験をする。
２回操作する意味がないことがわかる。
あとは計算量を少なくすることを考えればいいので
bitごとの情報を前処理しておけばO(n*log(maxA=(30)))
■D - Add to Square
直感的な嘘解放を投げるも通るはずはなく。
簡単にするために1 ==(i+j)%2の場合は-1倍しておく
左上の(h-1)*(w-1)を0にする。
その上で更に最小化を目指すと
0,x
y,zとあるとxとyの符号が一致していると(0 < x < y )
0-x,x-x
y-x,z-xとなるので小さくなる。これを繰り返すと通るが
正当性がよくわからない。
公式解説を読んだ
最小絶対値和は明らかなので
000x
000y
000z
abc
からそれを構築する方法を考える
もしaとxが共に正なら(a<=xとする)
a00x-a
000y
000z
0bc
とできるこれを繰り返す(共に負でも同様にできる)
サンプルでやってみると
0,0,0=2
0,0,0=-5
-3,3,-3から初めて
0,1,0=0
-3,0,-2=0
0,1-1となる
さらに1,-1の部分を
0,2,-1
-3,0,-2
とでもして反転を戻す。
