399.1

最後の300番台。

250

使ってはいけない整数のリストが与えられて、ある整数Nに一番積がちかくなるような三つの正整数の組を答えよという問題。

使えない整数の範囲は1000以下で、Nも1000以下なので、1001の3乗くらいのループを回す。N以下しか見ていなかったりするとダメ。1000までもダメ。三つ目の値は割り算とかで計算しても良い。

500

三つの整数が与えられるので、各整数の内部でビットを並び替えて、a+b=cが成り立つようにするとき、最小のcを答えよという問題。無理なら-1を返す。

1+1というビット演算はそのあとどういう計算が来てもそれに起因する1が残って、1+0というビット演算はキャリーがあると必ず消える。cを小さくするためには0+0というビット演算を間にはさむ意味はないので...というようなことをやってみたらダメだったみたい。悪い例は浮かばない。

結構複雑なDPを回すのが正解の模様。今何桁目を見ているとか、キャリーがいくつあるとか、どれだけビットが使われているかとかで最小値を覚えておく。DPで解けそうだからDPで頑張る、という発想をしないとダメなんだろうなぁ。多分何か見落としてしまうからこそのDPなんだろうけれども。

1000

男女それぞれN人ずつがN組を作る。組になりたくない相手の関係が与えられるとき、同じ組を二度と作らないで、最大でいくつN組を作ることができるか、という問題。ただしk回だけ組みたくない相手との組にも妥協する。

多分二部グラフマッチング系の問題なんだと思う。組まない人の間にはコストのある枝を張って、最大流を計算するという感じかな？一番流れの少ない人に対して流れを作っていく、という処理をするんだろうと思うけれど、それを両側でやるのは面倒そう。こういうのを解けるようにならないとダメなんだろうなぁと思いつつ、放置しそう。