609.1

ひどいセットだった。

250

指定された文字列のうち>が連続する個数と<が連続する個数が等しい部分文字列のうち最長なものの長さを答えよ、というのが面倒な英語で書かれていた問題。

やるだけ。

500

K種類のボールがたくさんあるので、K個以下のまとまりに分割したい。まとまりは、全部同じ色か、全部違う色のどちらか。最小いくつのまとまりに分けることができるか答えよ、という問題。

取り敢えずKで割った余り以外はK個同じ色のまとまりに分割して、後は適当に探索やるだけ。

全部違う色のまとまりは高々K-1個しかできないという方針は頭いいなぁ。(K個違うの色のまとまり作るなら、K個同じ色のまとまり作っても同じ。)

1000

木が与えられる。交差しないように二次元平面上に書いたとき、連続する葉をグループ化して、K個のグループにすることを考える。根から等確率に子への移動を繰り返したときに、各グループに到達する確率が均等になるような木の描画は可能か答えよ、という問題。

普通にDPやっても通らないんだろうなぁ、と思いつつ、探索書こうとしていた自分がいた。