問題一覧 > 通常問題

No.38 赤青白ブロック

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 160
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
2 ProblemId : 31 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:52

問題文

赤と青と白のブロックが各10個ずつある。
ブロックは左から右に一列に並べられている。
並べるときには次のような決まりがある。

赤いブロックよりちょうどKr個左に赤いブロックがあってはならない。
赤いブロックよりちょうどKr個右に赤いブロックがあってはならない。
青いブロックよりちょうどKb個左に青いブロックがあってはならない。
青いブロックよりちょうどKb個右に青いブロックがあってはならない。
白いブロックについては特に制限は無い。

最初にKr、Kbの数値とブロックの並びが与えられる。
赤のブロックをR、青のブロックをB、白のブロックをWとする。
最初の状態は上記に示した条件を満たしていないかもしれない。
よって、操作として次のような操作が許される。

・赤か青のブロックをいくつか抜いて列の間を詰める。

例えば、「RWBRWWB」であれば、
左端のRだけ抜いて「WBRWWB」という列を作ることができる。
左から4つめのRと右端のBを抜いて「RWBWW」という列も作れる。
RとBはいくつでも選んで抜くことができる。
ただし、Wのブロックを抜くことはできない。
このような操作を行うことで条件を満たす最長の列を残したい。
どのようにRとBのブロックを抜くかは自由である。
残すことが可能な最長の列の長さはどれだけか?

入力

Kr Kb
S

1<=Kr,Kb<=29
SはRが10個、Bが10個、Wが10個からなる文字列

出力

Ans

残ったブロックの最大個数Ans個を表示せよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
1 10
RRRRRRRRRRWWWWWWWWWWBBBBBBBBBB
出力
21

Rの1個となりがRであってはならないのでRを9個抜く。
Bの10個となりにBがあることは無いのでBは抜かなくてよい。
最終的には RWWWWWWWWWWBBBBBBBBBB が残る。

サンプル2
入力
1 2
WRWWBBRRRWWBBRRRRWWWBBBRRWWBBB
出力
22

サンプル3
入力
7 11
BWBWRWRRWBRRWRRWWBBBRRWBBRWBBW
出力
27

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。