JOI 2010-2011 予選 問題６ 解説

この問題では，場合の数を効率よく数えることが求められている． M, N の値は小さいが，高得点を得るにはプログラムの実行時間や使用メモリの丁寧な見積もりが必要である． J, O, I が下の図のように並んだ部分を「良い JOI 」と呼ぶことにする． 解法１ 最も単純な解法として，考えられるすべての「良い旗」を作りその個数を数える，という方法がある． 文字が決まっていないすべての場所に対して J, O, I のどれにするかを考えたものが旗の候補であり， それぞれついて「良い旗」の条件をみたすものを数えればよい． この方法では 3( ? の個数 ) 通りの候補を調べることになり， 小さなデータ以外では時間がかかりすぎてしまう． 解法１’ 決まっている文字は入力の条件に従うが 「良い旗」ではない旗 (すなわち，J, O, I が適切に並んでいる箇所がどこにもない旗) を「悪い旗」とよぶ． 「良い

[xrekkusu]

"○と×を，○が隣り合わないように N-1 個並べる場合の数" - JOI 2010-2011 予選 問題６ 解説: