ARC133
3完早解きバトル
result:ooo---
rateing:1933->1962
■A - Erase by Value
初めて、a[i]>a[i+1]となるa[i]を抜く
なければa[n-1]を抜く
■B - Dividing Subsequence
ARC126 B - Cross-free Matching
ARC133 B - Dividing Subsequence
実質一緒。
オーダーが厳しそうですが、ユークリッドの互除法と同じなので間に合う
■C - Row Column Sums
縦と横を別に考え、和が最大に成るケースのうち小さい方を採用する。
ngケースはΣAとΣBがmod kで異なる時
■D - Range XOR
f(x):=0 xor 1 xor.......x-1と定めると
f(x)は0,0,1,3,0,4,1,7となり
4つ周期で0,n-1,1,nとなることがわかる。
ここで問題文を読み替えると
L<=l<=r<=Rにてf(r+1) xor f(l)となり
r->r+1とし変形すると
L<=l<r<=R+1にてf(r) xor f(l)となる
g(x,y,z)でz = f(0<=i<=x) xor f(0<=j<=y)となるのの個数とすると
求めるのは
g(r,r,v)-g(l-1,r,v)*2+g(l-1,l-1,v)
ただし、0==zの時、l==rは調整が必要
関数gの中身は、上記のmod4で場合わけを16ケース頑張るとO(1)パートとメモ化再起に落ちる
■E - Cyclic Medians
解ける見た目をしてない。
