精進禄

競プロメモ

AGC019-B
B - Reverse and Compare
端が違う文字なら他の位置を反転した文字列とかぶることはない。
アルファベットごとに出現個数を持っておいて、左から探索。O(n)

AGC020-B
B - Ice Rink Game
にぶたんしてO(klogk)くらいかなーと思ってたらなんか線形で解けた。

APC001-C
C - Vacant Seat
どこかでMFMFMF...の規則が入れ替わらないとおかしいので、にぶたんできる
まず0を出力した時の答えが
男のとき:a[男]=0, a[女]=1
女のとき:a[女]=0, a[男]=1
と符号化する。
l = 1, r = nを初期値として区間[l, r)をもつ。
mid=(l+r)/1を出力したときに受け取った結果をresとおくと、
P(mid) = (a[res] == mid % 2)として
if(P(mid)) {
l = mid;
} else {
r = mid;
}
区間を狭めて行くことで答えにたどり着く。