ABC 043の問題を解きました
昨日ABCの問題を解きました(バイトがあったので時間には間に合いませんでしたが…)
A、B、Cは省略。Cはnが小さいので全探索で行けました。D問題だけメモ。
アンバランスな文字列(過半数が同じ文字となる文字列)は、少なくとも1カ所で同じ文字が二個以上連続している、もしくは文字列の長さが奇数のとき、1、3、5、…2n-1 (n>0) 文字目が同じである、のどちらかとなります。したがって、長さが2もしくは3となる部分列だけ確認すればオッケー。最初文字列の長さが2である場合を無視したプログラムを書いていたのでWAになってしまいました。
30分で4完(1WA)でした。今回はそこまで難しくなかったようです。