Codeforces 104

今年に入ってからBetaでなくなったようで。

A

0と1からなる同じ長さの文字列が二つある。スワップまたは書き換えの処理を最小回数行って、同じ文字列にせよ、という問題。

違っている数と、違い方を調べる。違い方は2通りしかないので、そのうち大きい方(小さい方はスワップで解決できる)を答えれば良い。

B

0と1からなる文字列のうち、0の個数・1の個数・01の個数・10の個数が指定された数のもので一番小さいものを答えよ、という問題。

01の個数と10の個数から、どの数字で始まってどの数字で終わるかが分かる。開始と終了のパターンは4通りで、01の個数と10の個数の可能なパターンは3通り。これに注意して後は最小なものを貪欲に出力すれば良い。

C

整数の配列が与えられるので、4と7のみからなる数は同じ数が出現しないように、大きさKの部分配列を作るとき、何通り可能か答えよ、という問題。

4と7のみからなる数字とそれ以外に分けて、それぞれがいくつずつかを考える。後は各セットからいくつずつ選ぶかをDPしていくだけ。最後だけたくさん選べるので、そこに注意。

D

整数配列が与えられるので、指定された数が両方に含まれないように重ならない連続領域を二つ取る方法は何通りあるか答えよ、という問題。指定された数字は高々1000回程度しか出現しない。

指定された数字で領域を切って、その領域内に二つの領域を確保するか、他方をその領域にして、残りをその指定された数で分割した領域のいずれかから取るか、とやるだけ。残りの領域の分割され具合とかをきちんとデータ構造に持たないとダメかも？

E

0と1からなる文字列が与えられる。その文字列の一部を反転させる操作を何回か行う。文字列中に出現する0*1*なる文字列の最長の長さの問い合わせがその過程で行われるので、適切に答えよ、という問題。

うまいこと適切なデータ構造に落とし込みましょう、といういつもの。