390.1

自己ベスト更新。コンディションは良くないと思っていたけれど、結局コンディションは結果には影響しないんだなぁと...。負の相関があるかも知れないけど。

250

ある数NをKの倍数にするためには、何回繰り返せば良いか、という問題。

moduloで計算してlong程度の精度に収まるようにして、同じ数が出てきたらできない。後は0になったところが答え。K回繰り返して0にならなければできない、という判定でもmoduloの数が高々Kなので問題ない。

500

複数の壁に色を塗る。連続した壁に対して人を割り当てることができる。このときかかる最小の時間を求めよ、という問題。使わない人がいても構わない。複数の人で同じ壁を塗ることはできない。

DPすれば最適解が一度で求まるそうですが...。取り敢えずバイナリサーチで、その時間以内に塗る方法があるかどうかをDPして調べるという方針にしました。前者だとちょっと最適化をしないとダメだそうで、結構な数の人が落ちていました。

ちなみに、ある時間内で塗る方法があるかどうかというのは、人の部分集合に対して、どこまで塗れるかを覚えておくというDP。

1000

大きさ1と2の抵抗を任意の数使って、大きさa/bの抵抗を作るとき、いくつ抵抗を使うか答えよという問題。使える数は全部で16個までとする。

適当に分割しながら、メモしつつ計算すればいいのかなぁと思ったのだけれど、結果は合わないし終わらないし...。今回は結構時間残っていたんだけどなぁ...。