オーダーを極める思考法：最強最速アルゴリズマー養成講座（3/3 ページ）

[高橋直大，ITmedia]

実装方針の検討

　この問題は、探索系の問題に見えますが、単なる数学の問題とも取れます。まずは愚直に組んでみましょう。

　前提として、A+Bの全体数は固定なので、0の数だけで状態を表すことが可能です。よって、0の数の取り得る範囲は、0からA＋Bまでなので、最大20万程度の状態しかないことが分かります。また、20万回以上のループが発生しないことも分かるため、これを利用して、探索を組んでみましょう。

　まずの状態をリストに入れ、そこから遷移可能な状態をすべて調べ、いままで出現していない状態であれば次に探索するリストに加え、0の数が0となるか探索先がなくなるまで調べる、といった単純な幅優先探索を用いてみます。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
public class BinaryFlips {
    public int minimalMoves(int A, int B, int K)
    {
        if (A == 0) return 0; //動かす必要のない時
        if (A + B < K) return -1; //ひっくり返せない時
        int[] array = new int[A + B + 1];
        for (int i = 0; i <= A + B; i++) array[i] = -1;
        List<int> nownode = new List<int>();
        List<int> nextnode = new List<int>();
        nownode.Add(A);
        array[A] = 0;
        while (nownode.Count > 0)
        {
            foreach (int i in nownode) //iは0の数
            {
                for (int j = Math.Max(0, K - (A + B - i)); j <= Math.Min(i, K); j++) //jは0をひっくり返す数
                {
                    int nextzero = i + (K - 2 * j); //遷移する次の状態の0の数
                    if (array[nextzero] == -1)  //初めて到達する地点であれば、次の探索に加える
                    {
                        if (nextzero == 0) return array[i] + 1; //答えが見つかれば、それを返す
                        array[nextzero] = array[i] + 1;
                        nextnode.Add(nextzero);
                    }
                }
            }
            //次のターン用にnextをnowに
            nownode.Clear();
            foreach (int k in nextnode) nownode.Add(k);
            nextnode.Clear();
        }
        return -1;
    }
}

　はい、1ページ目の説明を読んだ人であれば、もう即座に突っ込みを入れられるはずです。外側のiのループは、状態数が200,000ですので、最悪のケースを考えれば200,000ほどループします。実際は100,000ほどです。内側のjのループは、ほぼKなので、最大100,000程度。大ざっぱな計算になりますが、一番内側の計算数は200,000*100,000で20,000,000,000（200億）回程度になってしまいます。これでは話になりませんね。明らかに時間制限に引っかかってしまいます。

　よって、ここから工夫してどうやって制限時間内に計算を終わらすかを考えていきたいと思います。

方針1：探索範囲を狭める

　まずは、前記のアルゴリズムの計算量を減らしていくことで、実行時間を短くして解く方針で考えてみたいと思います。いきなりヒューリスティックな方法になりますが、探索の際、すべての遷移可能な状態について調べるのではなく、

• 0をできる限り多くする場合
• 1をできる限り多くする場合
• できるだけ0の数をKに近づける場合（上から、下からで2つ）

の4通りで十分でないか、と予想を立てることができます。0の数をKに近づけるのは、0の数をKにすることができれば、次のターンで0の数を0にすることが可能となるからです。これを実装すると以下のようになります。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
public class BinaryFlips {
    int[] array;
    int a, b, k;
    List<int> nownode = new List<int>();
    List<int> nextnode = new List<int>();
    public int minimalMoves(int A, int B, int K)
    {
        if (A == 0) return 0; //動かす必要のない時
        if (A + B < K) return -1; //ひっくり返せない時
        array = new int[A + B + 1]; a = A; b = B; k = K;
        for (int i = 0; i <= A + B; i++) array[i] = -1;
        nownode.Add(A);
        array[A] = 0;
        while (nownode.Count > 0)
        {
            foreach (int i in nownode) //iは0の数
            {
                check(i, Math.Max(0, K - (A + B - i))); //0をできるだけ増やす
                check(i, Math.Min(i, K)); //1をできるだけ増やす
                check(i, Math.Min(Math.Max((i + 1) / 2, K - ((A + B) - i)), K)); //Kに上から近づける
                check(i, Math.Min(Math.Max(i / 2, K - ((A + B) - i)), K)); //Kに下から近づける
            }
            //次のターン用にnextをnowに
            nownode.Clear();
            foreach (int next in nextnode) nownode.Add(next);
            nextnode.Clear();
        }
        return array[0];
    }
    public void check(int nowzero, int usezero)
    {
        int nextzero = nowzero + k - 2 * usezero; //出来るだけ0を増やす＝できるだけひっくり返す1を多く
        if (array[nextzero] == -1)  //初めて到達する地点であれば、次の探索に加える
        {
            array[nextzero] = array[nowzero] + 1;
            nextnode.Add(nextzero);
        }
    }
}

　ただし、あくまでも予想として解いているので、本当にこの方法で正しい結果が出るのかを証明する必要があります。競技中に証明するのは難しいですが、実際これは最適解を出すことが可能であり、後述する別の方法により、これが正しいと導くことが可能となります。

方針2：可能な範囲を記憶する

　上の方法ではいいかげんすぎるので、今度は単純に配列にデータを格納するのではなく、データの持ち方に工夫をしていくことで、計算量を減らしていこうと思います。

　何度か手でシミュレートしていけば分かるのですが、この問題は、0のカードを変更する枚数を1枚ずつ変化させることで、1つおきの連続した状態を得ることができます。よって、配列ではなく、どこからどこまでの範囲、という形でデータを持つことが可能です。そのため、1手ごとに、0の数の最大数、最小数を更新していき、最小数が0になるまで繰り返すだけで、最小ターン数を求めることが可能となります。

　これを考慮し、偶奇を考慮した上でソースコードを書いていくと、以下のようになります。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
public class BinaryFlips {
    public int minimalMoves(int A, int B, int K)
    {
        if (A == 0) return 0; //動かす必要のない時
        if (A + B < K) return -1; //ひっくり返せない時
        int i = 0;
        int minvalue = A, maxvalue = A; //0の枚数の現在の最大値、最小値を格納。偶数か奇数のみしかないのに注意
        for (i = 0; i <= A + B; i++)
        {
            int nextminvalue, nextmaxvalue;
            //まず可能な限り0を減らす→1をひっくり返すことを考える
            if (minvalue <= K && maxvalue >= K) //最大値と最小値の間にKがある場合
            {
                if (minvalue % 2 == K % 2) return i + 1; //Kとの偶奇が合えば、すべて1にすることができる
                else nextminvalue = 1; //そうでないと、どうしても1枚0が残ってしまう
            }
            else nextminvalue = Math.Min(Math.Abs(K - minvalue), Math.Abs(K - maxvalue)); //その他の場合は、端のみ考えればよい
            //同様に最大値も求める
            if (minvalue <= (A + B - K) && maxvalue >= (A + B - K))
            {
                if ((A + B - maxvalue) % 2 == K % 2) nextmaxvalue = A + B;
                else nextmaxvalue = A + B - 1;
            }
            else nextmaxvalue = A + B - Math.Min(Math.Abs((A + B - K) - minvalue), Math.Abs((A + B - K) - maxvalue));
            minvalue = nextminvalue;
            maxvalue = nextmaxvalue;
        }
        return -1;
    }
}

　以上のようになりますが、これが一番自然な解き方ではないでしょうか。

方針3：数学的に解く

　ここで、少し数学的にこの問題を解いてみましょう。

　i回のターンですべてを1にすることが可能だと仮定します。カードをひっくり返す回数は、i*K回となります。これに、もともと0だったものがA枚あるので、A枚ひっくり返すのは確定で、残りのひっくり返す回数をrestとすると、rest=i*K-A枚です。

　この残りの回数restをどうするかといえば、同じカードを2回ひっくり返す、を繰り返せばよいことになります。この操作ができる回数は、

• もともとのカードが0のとき、（i-1）/2回
• もともとのカードが1のとき、i/2回

となります。理由は簡単で、0のカードは最初に1回ひっくり返さなければならないのに対し、1は最初から1なので、最初から無駄にひっくり返す行為をすることができます。

　よって、無駄にひっくり返すことができる回数をuseとすると、use=（（i/2）*B+（（i-1）/2）*A）*2と表すことができます。

　このrestとuseを利用して、

• 十分に無駄なひっくり返す操作ができる必要があるので、rest≦use
• まずA枚以上ひっくり返せないと話にならないので、rest≧0
• ひっくり返す数の偶奇が合う必要があるので、rest%2=0

の3つの条件が満たされると、iターンで仮定に矛盾が生じず、すべて1にすることが可能であるといえます。

　以上より、この条件が満たされる最小のiを調べることで、必要なターン数を求めることができます。これを書くと、以下のようにすっきりと書くことができました。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
public class BinaryFlips {
    public int minimalMoves(int A, int B, int K)
    {
        for (long i = 0; i <= A + B; i++)
        {
            long rest = i * K - A;
            long use = ((i / 2) * B + ((i - 1) / 2) * A) * 2;
            if (rest >= 0 && rest % 2 == 0 && rest <= use) return (int)i;
        }
        return -1;
    }
}

　このコードではループを使って最小のものを求めていますが、これは直接解くことも可能です。ただし、前述のソースで速度は十分であり、場合分けが面倒になってきてミスが増えやすくなるため、競技中であれば前述のソースで十分ではないでしょうか。

　今回は幾つかの実装方針に沿ってコーディングしてみましたが、好みも出るところですし、各自の好きなものを選んでよいと思います。ちなみに筆者は最後のソースコードが一番のお気に入りですが、これを本番中に思いつけるかどうかは分かりません。どの実装方針でも、

• 制限時間を超過しない
• 厳密に最適解が出力される

　この2つを満たしているのであれば、組んでしまって問題ないかと思います。ほかにも方法があるかもしれないので、ぜひ探してみてください。「こんな実装もある」などのご意見もお待ちしています。それでは次回もお楽しみに！

著者プロフィール：高橋直大（たかはし　なおひろ）

Microsoftが毎年開催している「Imagine Cup 2008」のアルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。TopCoderでは誰もが恐れるRedcoderとして活躍中。先日開催された「天下一プログラマーコンテスト」では特別賞を受賞した。現在、慶應義塾大学環境情報学部2年。口癖は「みょんみょん」。