483.1

相変わらず900が解けない日々。1000よりも常に難しい気もしている。

250

1より小さい実数の、小数点以下6桁までの精度で値が与えられる。このとき切り捨てを行うとして、字面上一番似ている分数を答えよ、という問題。

分母は高々1000なので、全部試すだけ。与えられた実数から分子を近い値にするくらいすると高速化できる。

500

N人の人がいて、全員を説得することを試みる。すべての人には影響力と、耐久力があり、ある人に働きかけるとその人を中心とした人に影響力に応じた影響が出る。影響の合計が耐久力以上になった人は説得されたことになる。このとき全員を説得するのに必要な最小の働きかける人数を答えよ、という問題。N人の人は一列に並んでいて、一人離れるごとに影響力は半減するとする。

影響はすぐに0になってしまい、この問題のケースでは影響が出るのは前後8人ずつなので、その状態を覚えておいてDPする。前8人と後ろ8人にどう働きかけたかで、その人が説得されるかどうかが分かるので、説得されたなら次の人へ進む。

900

ナップザック問題を貪欲に解くとき、ナップザックの数と詰め込むものの大きさが与えられるので、全部詰め込むことができるにはナップザックの大きさはどれだけ必要か答えよ、という問題。

当然ナップザック問題が貪欲に解けるわけがないので、二分探索すると落ちますよ、という問題。ただ、近似解としてはそこそこにいいので、その後適当に探索(時間が許す限り)をすると答えに辿りつけるとかどうとか...。