C - コマンド入力
時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB問題文
高橋君は友達と格闘ゲームで対戦をすることにしました。格闘ゲームは A, B, X, Y の 4 種類のボタンを連続で入力するコマンドにより技を繰り出し戦うゲームです。
しかし、普段格闘ゲームで遊ばない高橋君にとってコマンドの入力は難しく、友達に勝てそうにありません。
そこで余っている L と R のボタンに連続した 2 つのボタン入力を
ショートカットとして割り当てることで、コマンドの入力を短縮したいと思います。
例えば、コマンドが ABXY だと 4 回ボタンを入力する必要がありますが、
L に AB、R に XY を割り当てることで LR の 2 回のボタン入力に短縮できます。
L と R を用いて入力をなるべく短くした時に必要なボタンの入力回数を求めなさい。
入力
入力は以下の形式で標準入力から与えられる。N1 行目にコマンドに必要なボタンの入力回数を表す N(1≦N≦1000)が与えられる。
c1c2…cN
2 行目にコマンドの内容を表す N 文字の文字列が与えられる。
i 文字目の文字である ci は、A, B, X, Y のいずれかで与えられる。
出力
ショートカットを用いてコマンド入力に必要なボタンの入力回数を最小化したときの、ボタン入力回数を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。
出典
C: コマンド入力 - AtCoder Regular Contest #002 | AtCoder回答
AtCoder/arc002_3.cpp at master · wada811/AtCoder総当りでクリアってのが美しくないかなー。
アルゴリズム的なのを期待したけど解読できる回答はみんな総当りでなんかなー。
とりあえず次は総当たりでもなんでも時間内にC問題までクリアしたいところ。