| 第８回日本情報オリンピック 予選６ |
|
|
2008年12月23日
情報オリンピック日本委員会
|
この問題はビンゴカード上の数字として表現されているが，実は n2 個の数列 {a1, a2, …, an×n} として表現することができる．これ以降，この数列に関して考えることにする．
ここで数列にかけられている制限は M を超えない自然数であり，昇順の順列(小さいものから大きいものに順に並べられた数列)でかつ同じ数字は二度でないということと，その全ての合計が S であるということである．
解法１
ai の値と a1 から ai までの合計値との組み合わせからその種類数を引き出すことができる配列を持ち，それを元に ai+1 の値と a1 から ai+1 までの合計値からその種類数を引き出すことができる配列を求める．これを i が 1 から n×n-1 まで繰り返し行う．ただし，この解法は一回の繰り返しに最大 M×M×S の回数だけ計算する必要があるため，計算時間が長くなり途中までしか答えられないだろう．
解法２
解法２では差分の数列 bi=ai-ai-1 ( ただし b1=a 1) なる数列を使う．数列の合計値が M を超えないことはすぐにわかるはずである．次にもう一つの条件，順列 a の合計値が S であることに注目する． b1 の値が 1 増えると合計値には n×n だけ影響が出るように， bi を 1 増やすと合計値が n×n-i+1 だけ増えることが少し考えるとわかるはずである．ここで b1 からbi までの合計値とその時点での a の合計値の組み合わせで解法１と同様に繰り返しを行う．一見このままでは解法１と同様の計算時間がかかるように思えるが，ある i での a の合計値の増え方は n×n-1 と一定であり，関数 fi(b の合計値 , a の合計値 ) を考えると fi(x, y)=fi(x-1, y-(n×n-i+1))+fi-1(x-1, y-(n×n-i+1)) と書け，計算結果をそのまま利用できるので一回の繰り返しに最大 M×S の回数の計算ですみ，計算が素早く終わる．ただ，この方法は式を見てもすぐはわからないと思うので以下の表に a と b の関係を表で図示したので参考にしてほしい．
| a1 | a2 | a3 | a4 | a5 | … | an×n | 合計値 | 使う回数 |
| 1 | 1 | 1 | 1 | 1 | … | 1 | n×n | b1 |
| 0 | 1 | 1 | 1 | 1 | … | 1 | n×n-1 | b2 |
| 0 | 0 | 1 | 1 | 1 | … | 1 | n×n-2 | b3 |
| 0 | 0 | 0 | 1 | 1 | … | 1 | n×n-3 | b4 |
| 0 | 0 | 0 | 0 | 1 | … | 1 | n×n-4 | b5 |
| ： | ： | ： | ： | ： | ： | ： | ： | ： |
| 0 | 0 | 0 | 0 | 0 | … | 1 | 1 | bn×n-1 |
上記より ai が b1 から bi までの合計になるということがわかっていただけただろうか． この表を元に 1 から n×n までの数字をそれぞれ少なくとも 1 回ずつ使いかつ合計 M 回以下使いその合計値を S 以下にしたいと考えると，より実装も容易になるだろう．