TopCoder SRM597

250

文字列 A に対して，「1 文字選んで先頭に持ってくる」操作を行うことができる．A を別の文字列 B に変えるために必要な操作の回数は？

A の部分文字列で，B の後ろのほうに一致しているものの最長の長さを求める．

600

凸多角形が与えられるので，その内部（辺上は含むが頂点は含まない）に頂点が整数座標であるような別の凸多角形を取れるか判定せよ．という問題になる．

内部の点が一直線上にあるかどうかを判定する（と思う）．落ちた

900

2*M のマス目を，赤，緑，青のいずれかで塗る．同じ色が隣り合ってはいけない．また，どの 2*2 の部分についても，赤，緑，青のそれぞれが 1 マス以上なければならない．赤，緑，青のマス数が与えられるので，塗り方の場合の数を求めよ．

2 列組で考えると，「赤緑」「赤青」「緑青」のどれか（逆も含む）である．一番上の行でこれらを置く向きを決めると，それ以下は全部自動的に決まる．2*2 の部分についての条件より，同じものが隣り合ってはいけない．それぞれの必要個数は簡単に求められる．
つまり，A, B, C を決められた個数，同じものが隣り合わないように並べる場合の数 * 2 を求める問題になる．
あとは，場合の数をがんばって求める．

結果

mid を適当に眺めていたらおかしいのがあったので落として +50
mid 落ちた＞＜
oxo +50 788.04 (4 位)

rating: 3126 -> 3172