659.1

あってなきがごとしな問題はどうなんだろう？

250

二種類のものを並べるときに、一方のものが直近のK個の中にK/2個以下になるようにしたい。(もう一方はどうでもいい。)一方のものの配置が一部固定されているので、最大の個数を答えよ、という問題。

もし一方のものを置いたら、それはK個分くらい影響が出るし、それより後ろに置いたら、もっと影響が出るので、置けるときには先に置いてしまうというような感じで、貪欲に割り当てていけばよい。

500

なんかちょっとゆがんだN*Kの空間があって、1x2のタイルか2x1のタイルか1x1のタイルを敷き詰めたい。何通り可能か答えよ、という問題。

ゆがみ方を適切に調整すると、2^K通りの状態を覚えておきつつN*K回割り当てていく感じになる。頭悪いと2^(K*2)になって詰む、というだけの問題。

1100

なんか存在してたらしい。