358.1

終わった直後の問題についてはコメントが壮絶にいい加減。過去問を解くのが追い付くまでは解かないだろうし。

250 (level1)

あるページに行きたいけれど、ボタンを押して直接行くか、今のページに+1もしくは-1するかしかできない。初期状態は100ページ目。ただし特定のボタンは壊れていて使えない、という状況で、特定のページに行くのにかかる最小のボタン押し回数を求めよ、という問題。

行きたいページの上限が500000なので、1000000まで全部のページに行った後、+1と-1で移動するとどうなるかを全部試せばおしまい。

500 (level2)

おもりの重さが与えられるので、その中から一番少ない種類を使って、他の全部の重さを表現できるようにする最小の数を求めよという問題。重さを表現できるとは、天秤の片側に表現したいおもりを置いて、両側に適当に選んだおもりを任意の個数置いて釣り合うようにできる、ということ。

gcdを求めれば二つのおもりで表現できる最小の重さができる、と思ったのだけれど、ダメだった。

gcdは新しいおもりを追加するとどんどん小さくなるので、最小下降列を求めればいいのかなぁと思ったけれど、間違っているっぽい。求め方が悪いだけかも。

1000 (level3)

3つのパラメータを持つサメの集合があり、全部のパラメータで負けていないサメを食べることができるという状況下で、生き残る最小のサメの数を求めよ、という問題。ただしサメは2匹までしか食べられない。

greedyにおっきい方から2匹食べる、というルーチンだとダメ。何がダメかというとパラメータが3つあるので、うまくソートできない。そういう順序を考えた上で、うまいことソートできればそれでもいいのかも。

現実的には食べられる候補が発散しない程度にうまいことDPやればいいんだろうなぁ。少なくともgreedyでうまくいくならDPでうまくいかないわけがない。