result:oooo--
rate:703->1117
レジってるつもりがレジれてなかったり
インタラクティブでfflush(stdout);
をすることを知らずに20分溶かすなどした。
■A. Forbidden Subsequence
tが"abc"でないときは単純にソートすればいい
tが"abc"でabcを部分文字列に持つときはbとcの塊を入れ替えればいい
■B. GCD Problem
c=1にしたい
n = 4m+0,2
(a,b,c) = (n-3,2,1)
n = 4m+1
(a,b,c) = ((n+1)/2,(n-3)/2,1)=(2m+1,2m-1,1)
n = 4m+3
(a,b,c) = ((n+3)/2,(n-5)/2,1)=(2m+3,2m-1,1)
■C. Paprika and Permutation
上から貪欲に決めていく
変更不要なものは変更する必要がないので変更はなし。
変更する必要なものは、上から除いたものを上から決めていく。
■D1. Too Many Impostors (easy version)
a,b,cとあってa!=bならcが0か1かで結果が決まるのでa!=bなものを見つければいい
a,b,c,dとあり(a,b,c)と(b,c,d)の結果が変わるならb!=cなのでそれを探す。
問題設定より絶対に存在する。
■D2. Too Many Impostors (hard version)
D1をn+6回で解けというもの。
長さ6のものを12回で特定し0と1の場所をD1の要領で探す。
(a,b,c) = 0なら
(a,b,c)=(0,0,0),(0,0,1),(0,1,0),(1,0,0)になる
これはすべてa->0,b->0とすると異なる結果になるので特定が出来る
結果n=3*mとして
m+(6-2)+6+(m-2)*2=3*m+6=n+6回で求まる。
■E. Christmas Chocolates
問題読む気にならない。
diff見てから決める
