389.1

難易度が低め。
なのに1000解けず...。

250

a/bの計算を2のべき乗のみの割り算で近似する。

近似式が与えられるので、その通りに実装しましょう。という問題。

500

ギターの弦の音と、実現したいコードが与えられる。コードは複数の音からなり、少なくとも一つの弦からその音を作成し、すべての弦を使う。弦の音を好きなように変えて実現するとき、操作する弦のうち、動かした大きさの最大値と最小値の差-1をコストとする。どれも動かさない場合はコスト0とする。このとき最小のコストでコードを実現せよ、という問題。

弦の数が6本しかないので、全通りためしてみる。12音がループしていることに注意する必要があるけれど、大抵のコーナーケースはサンプルに書いてある。

1000

10x10の盤面に1x1または2x2の正方形をあいている場所に書き、最後のマスを埋めた方が勝ちというゲームで、途中盤面からどちらのプレイヤーが勝つか答えよという問題。2x2のマスは一番上の行から行方向に重ならないようにしか置けない。列方向での重なりは良い。

状態は横方向9箇所と縦方向5か所の45か所のいずれに2x2が置けるか。これらのどこかに置き、残りのマスの数の偶奇をうまく考慮しつつ、grundy numberを求めるらしい。

DPすると終わらない...。効率良くやれればうまくいくのかなぁと思いつつ、保留。