SRM369 Div2 500

とぷこだ 過去問

問題

AまたはBの文字をいくつか並べた文字列を考える。
もし、

  • AはcountA個を超えない
  • BはcountB個を超えない
  • 連続するAの部分文字列の長さはmaxAを超えない
  • 連続するBの部分文字列の長さはmaxBを超えない

を満たす文字列は美しい。それぞれのパラメータが与えられたとき、美しい文字列の最大の長さを返す。

考え方

実際に具体的な文字列を作るのは困難。
文字はどちらでも関係ないので、countA>=countBとする。
もし、maxAが0のときはBしか使えないので、min(maxB,countB)。
もし、maxBが0のときはAしか使えないので、min(maxA,countA)。
そうでなければ、***B***B***B*...*B***B***のように、BをcountB個並べるとAを入れられる場所は*のところで、countB+1箇所ある。countAはcountB以上あるので、Aはその間にmaxA個ずついれることができる。したがって、Aは最大でも{maxA*(countB+1)}個以下でなければならない。
したがって、{min( countA, maxA*(countB+1) )+countB}となる。(桁あふれに注意)