233.1

きっとこの頃の問題セットは簡単だから解けるに違いない、と思ってやるとうまくいくルーチンができていたり...。

250

棒を二点で切るときに、ある長さよりも長い断片が残る確率はどれくらいか答えよという問題。切れる場所は有限個指定される。

全通り試してみるだけ。

500

4文字の文字列の任意の文字を前後に変換することにより、目的の文字列を作るためにな何回変換が必要か答えよ、という問題。ただし途中で作成してはいけない文字列が指定されている。

使えない文字列を事前にメモしておいて、BFSするだけ。

1000

円形のディスクを指定された大きさに切り分けるときの最小コストを求めよという問題。一回切るコストは切る前の大きさ。

ソートして、i番目からj番目までのものに切った時のコストを計算するというDPをするだけでうまくいく。なぜうまくいくのかは自明ではないし、良く分かってはいない。

想定解は、ハフマン木を作るのと同じ方法でやるみたい。