JOI logo
  第7回日本情報オリンピック 予選

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

問題
   おせんべい

解説

この問いでは, 最初に横の何行かを同時にひっくり返し, 次に縦の何列かを同時にひっくり返すようにと, 手順が指定されている. しかし, もし手順が指定されていないとしても i 行 j 列の煎餅の状態は, 初期状態と第 i 行をひっくり返した回数と第 j 列をひっくり返した回数だけで定まり, ひっくり返す順序は影響しない. 実際, 初期状態を S (表の場合は 1, 裏の場合は 0), 第 i 行をひっくり返した回数を r, 第 j 列をひっくり返した回数を c とすると, (S + r + c) が偶数ならば煎餅は表で, 奇数なら裏である.

解法1:
煎餅を焼く機械の縦を R 行, 横を C 列とする. ひっくり返し方は単純に数えると 2R × 2C 通りある. これらのひっくり返し方を全て調べれば出荷できる煎餅の枚数の最大値を求めることができる. この方法では, 1つ目の採点用テストデータに対して正解できる. 2つ目の採点用テストデータは8行50列であるので, 調べるひっくり返し方は 28 × 250 > 1017 となり, 短時間で正解を得ることは難しい.
解法2:
行のひっくり返し方を1つに固定すると, ある列をひっくり返すかどうかは他の列に影響を及ばさない, つまり, 列ごとに出荷できる煎餅の枚数を最大化すれば, 全体の出荷できる煎餅の枚数を最大化したことになる. 各列において出荷できる煎餅の枚数を最大化するには, その列の表(と裏)の数を数え, 表が多ければひっくり返し, 裏が多ければそのままにすればよい. 全ての行のひっくり返し方に対して, この方法で出荷できる煎餅の最大枚数を求める. 行のひっくり返し方は高々 210 = 1024 通りしかないので, 適切に実装すると, 全ての採点用テストデータに対して正解できる.
解法2の実装方針例:
行のひっくり返し方は 0 と 1 からなる長さ R の文字列で表すことができる. ここでは, この文字列の第 i 番目のビットが 1 なら i 行目をひっくり返すことを表し, 0 なら i 行目はひっくり返さないことを表すことにする. 各列の初期状態も, 行のひっくり返し方と同様に, 0 と 1 からなる長さ R の文字列で表すことができる.
行のひっくり返し方を上記の方式で表すと R ビットの非負整数 i になったとする. このひっくり返し方に対して, j 列目の出荷できる煎餅の最大枚数は, j 列目の初期状態を表す R ビットの非負整数を Sj とすると, i と Sj をビット単位で排他的論理和 (eXclusive OR) を取り得られるビット列中の 1 の数 と 0 の数の最大値 Mi,j となる. 1 から C までの j に対して, Mi,j の総和 Mi を求めると, Mi が行のひっくり返し方 i に対する出荷できる煎餅の最大数となる.
よって, 0 から 2R-1 までの各整数 i に対して, Mi を計算し, これらの最大値が求める数となる.