第18回日本情報オリンピック　予選６

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

解説

小課題 1
選手の人数の合計を M = A_1 + ... + A_N とおく．
単純な解法として，選手の並べ方を M! 通りすべて試すという方法が考えられる．再帰関数あるいは C++ の `std::next_permutation` を用いるとよい．時間計算量は O(M!) あるいは O(M! M) などになる．
同じ国の選手を一旦区別せずに，国の番号の並べ方を考えることもできる．この場合，調べるのは M! / (A_1! ... A_N!) 通りとなり，最後に場合の数に A_1! ... A_N! をかければよい．

小課題 2
左から順番に並べる動的計画法による解法を考える．
「並べる選手の集合」と「右端の選手の国」の組に対して，条件を満たす並べ方が何通りあるか求めていく．同じ国の選手を一旦区別しない方針によって，選手の集合は各国の人数で表され，(A_1 + 1) ... (A_N + 1) 通りとなり，O(A_1 + 1) ... (A_N + 1) × N^2) 時間で解くことができる．
この小課題では A_i ≦ 3 であるから，各国の人数を 2N ビットの整数に格納することで，ビット演算を用いた効率的な実装が可能である．

小課題 3
国の番号が小さい順に並べ方を決めていく動的計画法による解法を考える．
途中の並べ方においては，条件を満たす並べ方でなくてもよい：例えば，国 3 まで並べたときに国 2 の選手どうしが隣り合っていても，あとで間に国 4 の選手を挿入することで条件を満たすかもしれない．このように，「まだ条件を満たさない箇所がどのくらいあるか」を状態として動的計画法を行う．具体的には，国 i - 1 までを並べたとき，

• 国番号 i - 2 以下どうしで，同じ国あるいは隣国で隣り合っている場所の個数
• 国 i - 1 と国番号 i - 3 以下が隣り合っている場所の個数 (条件を満たさない場所ではないが，国 i の選手の挿入によって条件を満たさなくなる可能性があることに注意)
• 国 i - 1 と国 i - 2 が隣り合っている場所の個数
• 国 i - 1 どうしで隣り合っている場所の個数

を保持する．ここに国 i の選手たちを加えるには，

• 上記 4 種類のそれぞれについて，「国 i の連続」を何箇所に挿入するか
• 上記 4 種類以外について，「国 i の連続」を何箇所に挿入するか

を決めると，状態を更新でき，場合の数も計算することができる (実際の式は複雑になるので，解答例を参照のこと)．この解法の時間計算量は O(N (max A_i)^9)) となる．
上の解法では国ごとに並びに追加していったが，1 人ごとに追加していく考え方でも，同様に N と max A_i についての多項式時間で解くことができる (状態がやや複雑になるが，場合の数の計算は簡単になる)．