2009年春合宿 ビンゴ
この問題、非常に難しく感じた上に、解説の需要がありそうなので書きます。
日本語が下手なので、twitterで質問してください。
僕のACコード
Submission #1746495 - 第８回日本情報オリンピック 予選（オンライン） | AtCoder
多分どの解答も同じソースコードです。
解説
ポイント1
ビンゴの表は一列の数列に表せる！
これはほとんどの人が分かったと思います。左の列より右の列のほうが大きいかつ同じ列で昇順になっているので、それはそうですね。
ポイント2
これはDP!w
これもまた暫く考えていると予想はついてくるのではないでしょうか。ついてきますね。
ポイント3
とりあえずDPの構想を練ってみる！
この解説の続きを見る前に自分でDPを組み立ててみましょう。これ無理じゃん！ｗって気づいたらこの解説を見てください（もうDPの構想を練った人は続きを読もう）
DPの構想（仮）
必要な情報を考えてみます。
場所（何個目の整数か）//max50
今まで使った中で最大の値（要するに一個前の値)//max2000
今までの合計//3000
残念ながら、これだと50*2000*3000=3*10^8個の配列（メモリ）が必要になります。もちろん通りません。
ここでforDPでしかできない裏ワザ的な何かを使います。
使うと思った値を、使わずに済ませる→ループの順番を工夫して、その値を使わなくても自明な状態にする
ここで使わずに済ませる、自明にできる値は、予想がつくとは思いますが、今まで使った中での最大の値です。
最大の値が果たす役目は2つあります。
1.一個後の値を超えなければいけない。
2.制約で決められた値を超してはならない←これがなければ再帰でできます。
この役目2つを果たすためには、使う値を1からmまで順番に組み立てればいいです。そうすれば、3を組み立てたあとにそれより小さい1が来ること(これは例です)はなくなります。
最初のfor文で1からmまでループさせよう！
これで解決です。こうすれば、最大の値を考慮する必要があります。
もうこの先は、普通のDPです。頑張ってください！
