反転 (ライツアウト) 蟻本読書会

ひとりで勝手にはじめた蟻本読書会しゃくとり法最大区間・最小区間数え上げ蟻本読書会の続きです。

ライツアウトは、5×5の形に並んだライトをある法則にしたがってすべて消灯 (lights out) させることを目的としたパズルです。これに似た問題が競技プログラミングではよく出題されます。

選択した場所とその周辺の電球のONとOFFが入れ替わる問題の場合、同じ場所を 2 回選択したら元の状態に戻る、操作の順序を入れ替えたとしても結果は変わらないという特徴があります。これは同じ場所を 2 回選択することはありえない、選択回数としてありうるのは 1 か 0 かの 2 つだけです。

電球が直線上に並んでいる場合は端から考える貪欲法で解を求めることができます。

Contents

1 端から順に決まる貪欲法
- 1.1 C – Boxes and Candies
2 差分更新で計算量を減らす
- 2.1 Face The Right Way (POJ No.3276)
3 2回やったら元に戻る性質を利用する
- 3.1 H – 植林
4 反転 (ライツアウト)
- 4.1 Fliptile (POJ No.3279)

端から順に決まる貪欲法

C – Boxes and Candies

N 個の箱が横一列に並んでいます。最初、左から i 番目の箱には a i 個のキャンディが入っています。

キャンディが 1 個以上入っている箱をひとつ選び、その箱のキャンディを 1 個食べることで、どの隣り合う 2 つの箱を見ても、それらの箱に入っているキャンディの個数の総和が x 以下にしたいと考えています。

そのために必要な操作回数の最小値を求めてください。

入力されるデータ
N x
a 1 a 2 … a N

（ただし、2 ≦ N ≦ 10^5
0 ≦ a_i ≦ 10^9
0 ≦ x ≦ 10^9 ）

i を順番に見ていって、a[i] + a[i+1] ＞ x なら a[i] + a[i+1] = x となるまで a[i] と a[i+1] を減らさなければなりませんが、このとき a[i+1] から先に減らすのが最適です（i がインクリメントされたときに a[i+1] が再度 a[i] として評価対象になるため）。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N, x;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            x = vs[1];
        }
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        long ans = 0;
        for(int i = 0; i < N - 1; i++)
        {
            if (A[i] + A[i + 1] > x)
            {
                // 食べなければならない個数
                int a = A[i] + A[i + 1] - x;

                // 先に A[i + 1] から食べる
                if (a <= A[i + 1])
                {
                    A[i + 1] -= a;
                }
                else
                {
                    A[i] -= a - A[i + 1];
                    A[i + 1] = 0;
                }
                ans += a;
            }
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N, x;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

N = vs[0];

x = vs[1];

}

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

long ans = 0;

for(int i = 0; i < N - 1; i++)

{

if (A[i] + A[i + 1] > x)

{

// 食べなければならない個数

int a = A[i] + A[i + 1] - x;

// 先に A[i + 1] から食べる

if (a <= A[i + 1])

{

A[i + 1] -= a;

}

else

{

A[i] -= a - A[i + 1];

A[i + 1] = 0;

}

ans += a;

}

Console.WriteLine(ans);

}

差分更新で計算量を減らす

Face The Right Way (POJ No.3276)

「N頭の牛が並んでおり、それぞれ前/後どちらかを向いている。連続したK頭の方向転換ができる機械を何回か用いて、全頭の向きを前に揃えたい。最小の機械の使用回数と、そのときの最小のKを求めよ。」

前問では区間の長さは 2 で固定でしたが、今回はその区間の長さも考えよという問題です。

i番目の牛が後ろ向きの場合、「i番目の牛を先頭とする連続するK頭の牛の向きを変える」という操作を i=0 のときから順に繰り返し、これができるときの K の最大値を求めればよいのですが、これだと計算量がO(N^3)になり制限時間以内には終わりません。

そこで牛の区間[i, i+K-1]にて反転したかどうかを配列 isTurn[i] として定義します。牛 i が反転しているかどうかは、区間[i-K+1, i-1]でisTurn[i]の総和を取り、これが奇数なら最初の向きに対して反転していると判断できます。

using System;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        int[] directs = new int[N];

        for (int i = 0; i < N; i++)
        {
            if(Console.ReadLine() == "F")
                directs[i] = 0;
            else
                directs[i] = 1;
        }

        // すべてのKについて試す。
        int K = 1, turnCount = N;
        for (int i = 1; i <= N; i++)
        {
            int m = GetTurnCount(directs, i);
            if (m >= 0 && turnCount > m)
            {
                turnCount = m;
                K = i;
            }
        }
        Console.WriteLine($"{K} {turnCount}");
    }

    static int GetTurnCount(int[] directs, int reverseLength)
    {
        int n = directs.Length;
        int[] isTurn = new int[n]; //区間[i, i+K-1]の牛を反転させたかどうか？
        int turnCount = 0;
        int sum = 0;  //  区間[i-K+1, i-1]でisTurn[i]の総和
        for (int i = 0; i + reverseLength <= n; i++)
        {
            // 先頭の牛が後ろを向いている場合
            //(今までの操作回数が偶数ならば、はじめと同じ向き。奇数ならば、はじめと反対の向きなので)
            if ((directs[i] + sum) % 2 != 0)
            {
                turnCount++;
                isTurn[i] = 1;
            }

            // i が変化したら 区間[i - K + 1, i - 1]でisTurn[i]の総和も更新する
            sum += isTurn[i];
            if (i - reverseLength + 1 >= 0)
                sum -= isTurn[i - reverseLength + 1];
        }

        // 操作終了後、後ろ向きの牛が残っていないか調べる
        for (int i = n - reverseLength + 1; i < n; i++)
        {
            //牛向きがいたら不可能として-1を返す
            if ((directs[i] + sum) % 2 != 0)
                return -1;

            if (i - reverseLength + 1 >= 0)
                sum -= isTurn[i - reverseLength + 1];
        }
        return turnCount;
    }
}

using System;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] directs = new int[N];

for (int i = 0; i < N; i++)

{

if(Console.ReadLine() == "F")

directs[i] = 0;

else

directs[i] = 1;

}

// すべてのKについて試す。

int K = 1, turnCount = N;

for (int i = 1; i <= N; i++)

{

int m = GetTurnCount(directs, i);

if (m >= 0 && turnCount > m)

{

turnCount = m;

K = i;

}

Console.WriteLine($"{K} {turnCount}");

}

static int GetTurnCount(int[] directs, int reverseLength)

{

int n = directs.Length;

int[] isTurn = new int[n]; //区間[i, i+K-1]の牛を反転させたかどうか？

int turnCount = 0;

int sum = 0; // 区間[i-K+1, i-1]でisTurn[i]の総和

for (int i = 0; i + reverseLength <= n; i++)

{

// 先頭の牛が後ろを向いている場合

//(今までの操作回数が偶数ならば、はじめと同じ向き。奇数ならば、はじめと反対の向きなので)

if ((directs[i] + sum) % 2 != 0)

{

turnCount++;

isTurn[i] = 1;

}

// i が変化したら区間[i - K + 1, i - 1]でisTurn[i]の総和も更新する

sum += isTurn[i];

if (i - reverseLength + 1 >= 0)

sum -= isTurn[i - reverseLength + 1];

}

// 操作終了後、後ろ向きの牛が残っていないか調べる

for (int i = n - reverseLength + 1; i < n; i++)

{

//牛向きがいたら不可能として-1を返す

if ((directs[i] + sum) % 2 != 0)

return -1;

if (i - reverseLength + 1 >= 0)

sum -= isTurn[i - reverseLength + 1];

}

return turnCount;

}

2回やったら元に戻る性質を利用する

H – 植林

林は H × W 個のセルを持つ長方形領域とみなすことができる。各セルは木が 1 本生えているか 1 本も生えていないかのどちらかである。

セル (i, j) に使い魔を召喚すると i 行目か或いは j 列目にある H + W – 1 個のセルに対し、木が生えていなければ木が植えられ、木が生えていれば木が消されるという操作が行われる。

召喚には多くの魔力を必要とするので、できるだけ少ない召喚回数で林を木で覆いつくしたい。どのセルに使い魔を召喚すれば最小の召喚回数で林を木で覆いつくすことができるだろうか？

入力されるデータ
H W
a[1, 1] a[1, 2] … a[1, W]
a[2, 1] a[2, 2] … a[2, W]
…
a[H, 1] a[H, 2] … a[H, W]

（ただし、H，W は偶数。
2 ≦ H，W ≦ 1000
a[i, j] は 0 または 1 ）

出力するデータ
b[1, 1] b[1, 2] … b[1, W]
b[2, 1] b[2, 2] … b[2, W]
…
b[H, 1] b[H, 2] … b[H, W]
（ただし b[i, j] は 0 または 1。召喚する場合は 1、しない場合は 0 ）

H と W が偶数という制約により、i 行すべてと j 列すべてに召喚するとセル(i, j)の状態だけを反転させることができます。セル(i, j)以外の i 行のセルは W 回、j 列のセルは H 回（W と H はともに偶数）反転するので変化はしません。また i 行にはなく j 列にもないセルはちょうど 2 回反転するのでこれも変化はしません。セル(i, j)だけが奇数回反転するので状態が変化するのです。

そこでセル(i, j) に木がない場合は i 行すべてと j 列すべてを反転させます。偶数回反転させると元に戻るので、各セルを反転させた回数を記録し、奇数回反転させたセルだけ 1 を出力し、そうでないセルは 0 を出力します。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int H, W;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            H = vs[0];
            W = vs[1];
        }

        int[,] map = new int[H, W];
        for (int row = 0; row < H; row++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            for (int col = 0; col < W; col++)
                map[row, col] = vs[col];
        }

        int[,] counts = new int[H, W];
        for (int row = 0; row < H; row++)
        {
            for (int col = 0; col < W; col++)
            {
                // セル(i, j) に木がない場合は i 行すべてと j 列すべてを反転させる
                if (map[row, col] == 0)
                    SetCounts(counts, H, W, row, col);
            }
        }

        for (int row = 0; row < H; row++)
        {
            int[] arr = new int[W];
            for (int col = 0; col < W; col++)
                arr[col] = counts[row, col] % 2 == 0 ? 0 : 1;
            Console.WriteLine(string.Join(" ", arr));
        }
    }

    // i 行すべてと j 列すべての反転回数を加算する
    static void SetCounts(int[,] counts, int H, int W, int row, int col)
    {
        for (int r = 0; r < H; r++)
            counts[r, col]++;
        for (int c = 0; c < W; c++)
            counts[row, c]++;
        counts[row, col]--; // 交点を 2 回加算したので減算
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int H, W;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

H = vs[0];

W = vs[1];

}

int[,] map = new int[H, W];

for (int row = 0; row < H; row++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

for (int col = 0; col < W; col++)

map[row, col] = vs[col];

}

int[,] counts = new int[H, W];

for (int row = 0; row < H; row++)

{

for (int col = 0; col < W; col++)

{

// セル(i, j) に木がない場合は i 行すべてと j 列すべてを反転させる

if (map[row, col] == 0)

SetCounts(counts, H, W, row, col);

}

for (int row = 0; row < H; row++)

{

int[] arr = new int[W];

for (int col = 0; col < W; col++)

arr[col] = counts[row, col] % 2 == 0 ? 0 : 1;

Console.WriteLine(string.Join(" ", arr));

}

// i 行すべてと j 列すべての反転回数を加算する

static void SetCounts(int[,] counts, int H, int W, int row, int col)

{

for (int r = 0; r < H; r++)

counts[r, col]++;

for (int c = 0; c < W; c++)

counts[row, c]++;

counts[row, col]--; // 交点を 2 回加算したので減算

}

反転 (ライツアウト)

Fliptile (POJ No.3279)

M × N グリッド (1 ≦ M ≦ 15; 1 ≦ N ≦ 15) があり、そこには片面が黒、もう片面が白の正方形タイルが置かれています。

特定のタイルを選択するとそれに隣接するタイルも同時に裏返ります。

すべて裏にするために必要な反転回数の最小値と、その最小値を達成するために反転する場所を出力してください。複数ある場合は文字列としてみたときに辞書順最小のものを、タスクが不可能な場合は「IMPOSSIBLE」を出力してください。

入力されるデータ
M N
A[1, 1] A[1, 2] … A[1, N]
A[2, 1] A[2, 2] … A[2, N]
…
A[M, 1] A[M, 2] … A[M, N]

（ただし、1 ≦ M ≦ 15, 1 ≦ N ≦ 15
A[i, j] は 0 または 1 ）

貪欲法で端から順に決めることができればよいのですが、この場合はそうはなっていません。しかし 1 行目全体が決定すると 2 行目以下は貪欲法で適切な動作が決まります。1 行目の動作は辞書順で全通り試します。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int H, W;
    static int[,] Map = { };

    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        H = hw[0];
        W = hw[1];

        Map = new int[H, W];
        for (int row = 0; row < H; row++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            for (int col = 0; col < W; col++)
                Map[row, col] = vs[col];
        }

        int res = int.MaxValue;
        int[,] opt = new int[H, W]; // 最適解保存用

        // 1 行目の動作は辞書順で全通り試し
        // 2 行目以降の動作は Calc メソッドで処理をする
        for (int i = 0; i < 1 << W; i++)
        {
            int[,] flip = new int[H, W]; // このマスを中心に反転させたか？
            for (int j = 0; j < W; j++)
                flip[0, W - j - 1] = (i >> j) & 1;

            int num = Calc(flip);

            // Calc が -1 を返したときは解なし。
            // 0 以上の値を返したときは最小値のときはこれを更新する
            if (num >= 0 && res > num)
            {
                res = num;
                opt = (int[,])flip.Clone();
            }
        }

        if (res < int.MaxValue)
        {
            Console.WriteLine(res);
            for (int row = 0; row < H; row++)
            {
                int[] arr = new int[W];
                for (int col = 0; col < W; col++)
                    arr[col] = opt[row, col];
                Console.WriteLine(string.Join(" ", arr));
            }
        }
        else
            Console.WriteLine("IMPOSSIBLE");
    }

    static int Calc(int[,] flip)
    {
        for (int row = 1; row < H; row++)
        {
            for (int col = 0; col < W; col++)
            {
                // (i - 1, j)が黒色ならこのマスを反転させるしかない
                if (Get(row - 1, col, flip) != 0)
                    flip[row, col] = 1;
            }
        }

        // 最後の行が全部白かチェック
        for (int col = 0; col < W; col++)
        {
            // チェック不合格 → 解なし
            if (Get(H - 1, col, flip) != 0)
                return -1;
        }

        // チェックを通過したので反転回数をカウントして返す
        int res = 0;
        for (int row = 0; row < H; row++)
        {
            for (int col = 0; col < W; col++)
                res += flip[row, col];
        }
        return res;
    }

    // マス(row,col)の状態を取得する
    static int Get(int row, int col, int[,] flip)
    {
        int[] dx = { -1, 0, 0, 0, 1 };
        int[] dy = { 0, -1, 0, 1, 0 };

        // もとの状態とそのマスおよびこれと隣接するマスの差分から(row,col)の状態を取得する
        // もとの状態と差分の合計から表か裏かがわかる
        int value = Map[row, col];
        for (int i = 0; i < 5; i++)
        {
            int r = row + dx[i];
            int c = col + dy[i];
            if (0 <= r && r < H && 0 <= c && c < W)
                value += flip[r, c];
        }
        return value % 2;
    }
}

100

101

102

103

104

105

106

107

108

109

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static int H, W;

static int[,] Map = { };

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

H = hw[0];

W = hw[1];

Map = new int[H, W];

for (int row = 0; row < H; row++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

for (int col = 0; col < W; col++)

Map[row, col] = vs[col];

}

int res = int.MaxValue;

int[,] opt = new int[H, W]; // 最適解保存用

// 1 行目の動作は辞書順で全通り試し

// 2 行目以降の動作は Calc メソッドで処理をする

for (int i = 0; i < 1 << W; i++)

{

int[,] flip = new int[H, W]; // このマスを中心に反転させたか？

for (int j = 0; j < W; j++)

flip[0, W - j - 1] = (i >> j) & 1;

int num = Calc(flip);

// Calc が -1 を返したときは解なし。

// 0 以上の値を返したときは最小値のときはこれを更新する

if (num >= 0 && res > num)

{

res = num;

opt = (int[,])flip.Clone();

}

if (res < int.MaxValue)

{

Console.WriteLine(res);

for (int row = 0; row < H; row++)

{

int[] arr = new int[W];

for (int col = 0; col < W; col++)

arr[col] = opt[row, col];

Console.WriteLine(string.Join(" ", arr));

}

else

Console.WriteLine("IMPOSSIBLE");

}

static int Calc(int[,] flip)

{

for (int row = 1; row < H; row++)

{

for (int col = 0; col < W; col++)

{

// (i - 1, j)が黒色ならこのマスを反転させるしかない

if (Get(row - 1, col, flip) != 0)

flip[row, col] = 1;

}

// 最後の行が全部白かチェック

for (int col = 0; col < W; col++)

{

// チェック不合格 → 解なし

if (Get(H - 1, col, flip) != 0)

return -1;

}

// チェックを通過したので反転回数をカウントして返す

int res = 0;

for (int row = 0; row < H; row++)

{

for (int col = 0; col < W; col++)

res += flip[row, col];

}

return res;

}

// マス(row,col)の状態を取得する

static int Get(int row, int col, int[,] flip)

{

int[] dx = { -1, 0, 0, 0, 1 };

int[] dy = { 0, -1, 0, 1, 0 };

// もとの状態とそのマスおよびこれと隣接するマスの差分から(row,col)の状態を取得する

// もとの状態と差分の合計から表か裏かがわかる

int value = Map[row, col];

for (int i = 0; i < 5; i++)

{

int r = row + dx[i];

int c = col + dy[i];

if (0 <= r && r < H && 0 <= c && c < W)

value += flip[r, c];

}

return value % 2;

}

反転 (ライツアウト) 蟻本読書会

端から順に決まる貪欲法

C – Boxes and Candies

差分更新で計算量を減らす

Face The Right Way (POJ No.3276)

2回やったら元に戻る性質を利用する

H – 植林

反転 (ライツアウト)

Fliptile (POJ No.3279)

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ