548.1

リハビリ中...。

250

N本の木が並んでいて、それぞれの高さが与えられている。木の高さがソートされるように、それぞれの木について高さを変更することを考えるとき、必要な変更量の最小値を答えよ、という問題。

ある変更で十分ならば、それよりも大きい変更をしたときにも十分なので、バイナリサーチできる。それぞれの木について、変動分が与えられたときに、満たすべき範囲と、一つ前の木の高さ(越えなければいけない値)を受け取って自分の高さを決めていく。決定できるかできないかで分岐。

450

N面のさいころが二つある。一つのさいころには部分的に目が入れられており、もう一つのさいころには全部目が入っている。それぞれのさいころに重複の目はない。目の入っていないものに、重複がないように目を入れる、あるいは何もしないという操作をすることによって、二つのさいころを同時に振ったときに、一つ目のさいころが大きい目になる確率をできるだけ1/2に近付けたい。このときの確率(複数ある場合は最小値)を答えよ、という問題。

使える目の範囲を全部調べて、それを記入したときに大きい目になる確率を求めておく。何もしないという操作が許容されているので、必ず小さい目になることはできる。後は、あいているところに目を入れるときに、あいている個数と、大きい目になる確率ごとに何箇所に入れて良いかで、最終的な確率として達成できるものを全探索する。(適当にメモしてやらないとTLEする。)最後に1/2に一番近い最小の値を出力すれば良い。

1000

N都市の間にK本の道を引いて、全部の都市が連結になるようにしたい。ただしM都市に関しては次数が2でないといけない。このときの道の引き方は何通りか答えよ、という問題。

Mが2以下なので、Mについて状態を分けると、M都市の効果によって連結な都市がいくつかと、独立した都市に分割される。後はこれらを適宜併合していく。併合する際のルールとして、一個追加するときに、追加可能な道のうち何本使うか、とそれは何通りか、というのをかけてやる。というのを延々とやればできそう。