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

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

解説

まず，問題文の条件から，適切な予定表がどのようなものであるかを考える．各日，誰が鍵を持って帰ってもよいことから，どの連続する 2 日に対しても，誰か 1 人以上が両日に部活に出席することが必要であることがわかる．また，初日の責任者に関わらず，初日は鍵を持っている J 君が出席しないといけないこともわかる．この 2 つの条件を満たしていれば，毎日部活を行うことができる．

単純な解法として，それぞれの日に対して部活に出席する人の選び方をすべて試すという方法が考えられる．各日について，出席者の選び方は 8 通り考えられるため，選び方は 8^N 通り考えられる．責任者以外の 2 人が出席するかをすべて試す場合は，選び方は 4^N 通りになるが，これでも N が大きいデータに対しては短時間で答えを求めることができない．

注目すべきは，i 日目の出席者を決めたとき，i + 1 日目の出席者を決める際には，1 日目から i - 1 日目まで誰が出席するかは関係ないということである． 「i 日目の出席者の組み合わせが s であるときの，i 日目までの予定表の場合の数」を f(i, s) とする． すると，f(i + 1, s') は f(i, s) がわかっていれば次のようにして計算できる： s' が i+1 日目の責任者を含んでいないときは，f(i + 1, s') = 0 である． s' が i+1 日目の責任者を含んでいるときは，f(i + 1, s') は「s が s' と共通部分を持つようなすべての s についての f(i, s) の総和」である． また，f(1, s') は，s' が J 君及び 1 日目の責任者を含んでいるときは 1，そうでないときは 0 である． このように，サイズの小さい問題から順番に解いていくような手法は，動的計画法と呼ばれている．

この方法によって，計算すべき f(i, j) の値は 8 × N 個であり，f(i + 1, j') を計算するのに最大 8 通りの j の値を試すので，N に比例する時間で答えを求めることができる． 実装するにあたっては，s を 2 進法のビット列に対応させると比較的容易になる．例えば J 君，O 君，I 君にそれぞれ 1, 2, 4 を割り当て，s に対応する値は割り当てられた値のビットごとの論理和を取るとよい．このようにすると，s と s' が共通部分を持つかどうかは，s と s' に対応する値のビットごとの論理積をとり，0 でないことを確かめればよい．