インタラクティブの無駄ペナやめよう
result:oooo--
rateing:1890->1897
■A. Reverse and Concatenate
与えられた文字列をp
それを反転させたものをqとして
作られるのは
p
pq,qp
pqqp,qppq
なので操作回数が1回以上なら2、0なら1
しかしp=qなら例外
■B. Fortune Telling
a+b=a^b(mod2)であり
x!=x+3(mod2)なので
構築ができるならどちらかということがわかる
■C. OKEA
k=1なら明らかに可能
そうでないときはmod2を可能にするために
全て偶数or全て奇数である必要がある。
なのでn%2で場合わけ
nが偶数のときは交差２の等差数列を作れば良い
■D. Finding Zero
a0,a1,a2
a0,a1,a3を順番に見ていく(n-2回)
これが最大に成るものは
a0,a1,minかa0,a1,maxを満たしている
n-2回の操作で取得した値が全て同じ場合は
a,b,0,a+b,a+b,,,,,
か
a,b,[a,b],[a,b],[a,b]のケース
そうでないときは
a,b,maxかa,b,minのケース
・前半ケース
a2,a3,a0
a2,a3,a1を考えこれらが、a0,a1,a2より大きければ答えはa2,a3になる
そうでないときは
a2,a3,a4
a2,a3,a5....を順々に見てきa0,a1,a2より大きいものがあれば、そこに0があり
そのようなものがなければ、a0,a1のどちらかになる。
・後半ケース
最初のn-2回で最大になったインデックスをidxをする
0,idx,iをすべて見ていく(n-2回)
これが最大になったインデックスをidx2とすると
minの存在可能性はidx,idx2,0(=idx3)のいずれかになる
idx=maxのときidx2idx3のどちらか
idx=minのとき答えはidx
なので、(idx,idx2,another),(idx,idx3,another)を考え大きくなったほうとidxを答えの候補とすればいい
■E. Fair Share
二部グラフっぽいよねということぐらいはわかる。
左に配列番号を、右に要素を置いて辺を貼る。
これをいくつかの一筆書きで全ての辺を使用すればいい。
左をから右をL、右から左をRとしてdfsを行う。
地味にdfsの遷移が難しい。
対応している逆辺のidをもたせておき、これを-1にしたら使用済みと判断する
辺を舐めるときは、すでに使用済みのものを全部舐め回すとtleするので
最低でもここまでは全て使用したというような情報を持っておく。
