■A. Burenka Plays with Fractions
２手あれば絶対にできる
０手の判定は簡単(a*d==b*c)
１手の判定は0==(b*c)/(a*d)or0==(a*d/b*c)
0==a,0==cに注意
■B. Interesting Sum
FirstMax+SecondMax-FirstMin-SecondMin
■C. Corners
1の個数-(0,1,2)でできる
初手が重要。
■D1. Xor-Subsequence (easy version)
制約の意味を考える
a[i]<256の意味を考えると
256個ごとに区間で分けると同じ区間からは選べないことがわかる。
dpができる。
■D2. Xor-Subsequence (hard version)
A[i] xor j < A[j] xor iを満たすためには？
上n桁が一致してn+1桁目が0,1になれば良い
条件を分けて考える
前半
A[i]^iとA[j]^jの上n桁が一致すれば満たす
後半
jを決めたときに、iから遷移できるかは
特定の組み合わせのみとわかる
Binary Trieに少し拡張して乗せる
