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

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

解説

まず，整理した後のぬいぐるみの配置としてありうるものは，左から並べていく種類の順を決めれば， 左から各種類を詰めていくことで決めることができ，配置の仕方は全部で M! (= 1×2×3×……×M) 通りある． 配置を決めた後，棚から取り出すぬいぐるみの個数を最小にするには，ぬいぐるみを置く場所のうち，最初置かれていた種類と整理した後に置かれる種類が異なる場所のみを取り出せば良い． 並べ方を全通り試し，必要な個数をループで数えると計算量は O(M! × N) となり，MとNがともに小さい場合 (入力 1，2) のみ解くことができる．

配置を決めた後に取り出す必要のある個数を高速に求めるにはどうしたらいいだろうか．これは，累積和を使うことで計算できる．具体的には，まずそれぞれの種類に対して，その種類のぬいぐるみが存在する場所を 1 ， 存在しない場所を 0 とした配列を作る．その後，各要素に対し，配列の先頭の要素からその場所までに含まれる値の合計を計算することは，直前の計算結果にさらに値を足すことによって，合計で　O(N) で計算できる． この配列を利用すると，連続する区間 [l,r) に含まれる種類 k のぬいぐるみの総数を， sum[k][r]-sum[k][l] のようにして O(1) で求めることができる． この方法を使えば，M の小さいケース (入力 3) を解くことができる．

配置の決め方を全通り試していると M が大きいケースで短時間に答えを求めることができない．そこで，左から見て今までに配置した種類の集合をキーに動的計画法することを考える．(これはビット DP などと呼ばれている方法である) 具体的には， dp[S] := (配置に使った種類の集合が S の時のそこまでで取り出す必要があるぬいぐるみの個数の最小値) とする．集合が S の状態から，さらに 1 種類配置するとき， S に含まれる種類のぬいぐるみの総数だけ左から埋まっている．今まで配置した順にかかわらず，棚のどの位置に次の種類を配置するかがわかるので，次の種類を配置するのに必要な取り出す個数が 累積和の配列を利用すると O(1) で求められる．

この動的計画法を使うと，状態数が O(2^M) で遷移が O(M) かかるので、動的計画法の部分では計算量は O(2^M M) となる．これに累積和の計算量を加えても， 全てのケースに正解するのに十分高速であることがわかる．