第９回日本情報オリンピック　予選４

2009年12月17日
情報オリンピック日本委員会

解説

この問題を解くためには，

• n 枚のカードから k 枚を選ぶ選び方を全て列挙する
• 選んだカードを横一列に並べて整数を作る
• 作った整数が全部で何個あるかを数える

という３つのステップを正確に実装し，組み合わせる必要がある． 配列，ループ，再帰といったプログラミングの基礎事項を理解し，実装できることが求められる．

カードの選び方を列挙する方法であるが， もし k の値が固定されている場合は， 単純に k 重の for ループを書けばよい． この問題では入力データによって k の値が異なるので， 少し工夫が必要だろう．また，再帰を使って書くこともできる．

選んだカードから整数を作るためには， まず，カードに書かれた整数を文字列として記憶しておいて， 文字列として結合する（C 言語であれば strcat などの関数を利用することもできる）． そして，最後に文字列から整数に変換すればよい． この問題の場合，カードに書かれた数字が 1 以上 99 以下なので， 次のように実装してもよい． まず，カードに書かれた数を整数として記憶する． 例えば，2 つの整数 a と b を並べて新しい整数を作るためには， 1 ≦ b ≦ 9 なら a*10+b を計算し， 10 ≦ b ≦ 99 なら a*100+b を計算すればよい． 並べる整数の数が多い場合も同様である．

最後に，作った整数の個数を数える方法だが，まず，十分に大きな配列を用意する． 整数を 1 つ作る度に，配列内の整数と比較し，新しい整数であれば配列の最後尾に追加することを繰り返す． 全ての整数を作り終わった後に，配列の長さを出力すればよい． カードの枚数 n が 10 以下，選ぶ枚数 k が 4 以下だから， 最大でも ₁₀C₄ = (10*9*8*7)/(4*3*2*1) = 210 個の整数しか作られない． したがって，長さが 210 以上の配列を用意すればよい．

情報オリンピックでは，この問題のように， 複数のアルゴリズムを適切に設計し組み合わせる問題も出題される． プログラムがなかなか思い通りの動作をせず，手間取った人も多いのではないだろうか． 最初から一気に作ろうとするのではなく， 一つ一つのアルゴリズムを正確に実装することが大切である． この問題であれば， まず，カードの選び方を列挙するだけのプログラムを作る． 十分に修正（デバッグ）した後，カードを並べて整数を作るプログラムを作る． 最後に，作った整数を数えるプログラムを作ればよい．