■A - ABC Identity
解けませんでした。
６つに分けろといっているからABC,ACB,BAC,BCA,CAB,CBAの形に分ければいい気がする。
だが、貪欲でやると前と後ろはいいが真ん中をどう取るべきかという話になる。
おもむろに3NのブロックをN,N,Nに分けて考えてみる
ABCを作るとして、Aの並びは最初のブロックからBは真ん中のブロックからCは最後のブロックからを上記の6セット繰り返すことで
最終的に残る要素がなくなればいい。
この正当性の証明は解説を参照。
これ500人もちゃんと証明してACしてるならすごいと思う。
■B - ABC Supremacy
実験を色々してみる。
ABCAはAABCに出来る
すなわち、ABC,BCA,CABがあればそれを好きな場所に動かせるので無視していい。
結果的に取り除いた文字列が、一致すればいい。
あとはstackでやるよくあるパターン。
■D - ABC Ultimatum
何故か解けた。
ABCABCBCAみたいなものは、
ABC,ABC,BCAを作るのではなく
ABCABCとBCAを切り出すと考えてみる
こうすると、例えばCはBで終わっている(Cを待っている)文字列があればそこに
なければ先頭要素として採用することになる。
すると
dp[i][j][k][l][m][n]:=A始まりがi個,B始まりがj個,C始まりがk個,Aを待っているのがl個,Bを待っているのがm個,Cを待っているのがn個
というdpが立つ。
遷移は上に書いたとおり行えば簡単で
最終的にi==l,j==m,k==nとなるものが答えになるもの。
遷移の途中でl+m+n>Nとなるものは枝刈りしてmapで管理する。
微妙に自信がないがサンプル３が通るので投げると通る。
