競プロ解法紹介～大局観で高得点を取る！～

2016年03月20日（8時間）に開かれたマラソン形式の競技プログラミングコンテスト、chokudai contest1の解法紹介です。
公式ビジュアライザはこちら。
公式解説スライドはこちら。

問題概要「高橋君の山崩しゲーム」※原文引用

高橋君は、あるゲームを考えました。

• はじめに、30×30 のマスを用意し、それぞれのマス目に 1 以上 100 以下の整数を書き込む。
• 以下の一連の操作を手と呼び、これを繰り返して、ゲームの終了を目指す。
  • ステップ 1 ： 1 つのマスを選ぶ。ステップ 2 に進む。
  • ステップ 2 ：選んでいるマスに書かれた整数を 1 減らす。ステップ 3 に進む。
  • ステップ 3 ：選んでいるマスから上下左右に隣接するマスの中で、そのマスに書かれた数が、選んでいるマスと同じ数（つまり、元々書かれていた数より 1 少ない数）かつ 0 以外の数であれば、そのマスを連続して選び、ステップ 2 に戻っても良い。選ばない場合はこの手を終える。
• 全てのマスを 0 にしたらゲームの終了となる。

高橋君は、このゲームを手の数を出来るだけ少なくしたいです。高橋君の代わりに、手を出力するプログラムを作成してください。

採点方法
10 個のテストケースが存在し、各テストケースにつき点数が付けられる。
そのテストケースについて、出力が正しければ、 100000−手数 の点数が得られる。
全てのテストケースの和が、その回答の点数となる。

図解

解法

では解いていきましょう。最良解を得るためには、上手く連続した手を選べるかがポイントです。
今回は高度なアルゴリズムを使わず、当時のランキング1ページ目（20/500人超）を目指します。

正の点数を取る解法

まずは、連続して手を選ぶことは忘れて、愚直に崩していきます。

Main.java

import java.util.Scanner;

/**
 * chokudai contest1
 * @author tsukammo
 */
public class Main {
    final static int row = 30, col = 30; // map size

    public static void main(String[] args) {
        new Main().solve();
    }

    int[][] map = new int[row][col];

    void solve() {
        input();
        solveFool();
    }

    void input() {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                map[i][j] = sc.nextInt();
            }
        }
    }

    void solveFool() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                while (map[i][j]-- > 0) {
                    System.out.println((i + 1) + " " + (j + 1));
                }
            }
        }
    }
}

上記を提出すると541,032点でした。全10ケースのため、平均約46,000手がかかっている計算です。

連続値の取得を考慮した解法

次に、山のてっぺんから可能な限り連続して崩していきます。
追加する機能は、「山のてっぺんの判定」・「現在のマスから上下左右に連続値が無いか調べる」の2つです。
難しいアルゴリズムは書けないので、全て頭から順にfor文を回して選ぶだけです。

Main.java

// 略
public class Main {

    // 中略

    // 変更
    void solve() {
        input();
        //solveFool();
        solveWisdom();
    }

    // 4方向探索用
    final static int[] dx = new int[] { 1, 0, 0, -1 };
    final static int[] dy = new int[] { 0, 1, -1, 0 };

    void solveWisdom() {
        int[] p = chooseTop();
        while (p != null) {
            // 可能な限り連続で崩す
            while (true) {
                int x = p[0];
                int y = p[1];
                System.out.println((x + 1) + " " + (y + 1));
                map[x][y]--;
                // 4方向探索
                int[] next = null;
                for (int d = 0; d < dx.length; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (outMap(nx, ny)) {
                        continue;
                    }
                    if (map[x][y] == map[nx][ny] && map[nx][ny] > 0) {
                        next = new int[] { nx, ny };
                        break;
                    }
                }
                if (next != null) {
                    p = next;
                    continue;
                }
                break;
            }
            p = chooseTop();
        }
    }

    // 山のてっぺんを探す
    int[] chooseTop() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (isTop(i, j)) {
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }

    // 山のてっぺんかを判定
    boolean isTop(int x, int y) {
        for (int d = 0; d < dx.length; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (outMap(nx, ny)) {
                continue;
            }
            if (map[x][y] <= 0 || map[nx][ny] > map[x][y]) {
                return false;
            }
        }
        return true;
    }

    // 場外判定
    boolean outMap(int x, int y) {
        return !(x > -1 && y > -1 && x < row && y < col);
    }

    // 以下略
}

上記を提出すると800,640点でした。当時のランキングで123位となります。
優勝者が890,000点代ですので、あと10%以上向上の余地がありますが、ここから点数を上げていくには工夫が必要となります。

大局を捉えた解法

先程のプログラムでは、見つけた側から出力しているため他の組み合わせではより高得点のものが存在するはずです。厳密解を求められるオーダーではないため、上手く最良解を選びたい所ですが、どのようにすれば良いでしょうか。
自然な発想では「なるべく長く連続で崩せる組み合わせを採用する。」という解法が思いつくと思います。

が、この方法は多くの場合で点数が悪化します。※是非試して見て下さい。

まずは先程のプログラムの出力途中の様子を確認しましょう。

どうでしょうか。頭から順にてっぺんとなるマスを見つけては崩していくため、崩し終わった部分と、未実施の部分で崖が形成されているのがわかると思います。

ここで魔法を使います。

Main.java

// 略
public class Main {
    // 中略

    // Before 4方向探索用
    //final static int[] dx = new int[] { 1, 0, 0, -1 };
    //final static int[] dy = new int[] { 0, 1, -1, 0 };
    // After 4方向探索用
    final static int[] dx = new int[] { 0, -1, 0, 1 };
    final static int[] dy = new int[] { -1, 0, 1, 0 };

    // 以下略

ご覧の通り、4方向探索順序を変えただけです。
上記を提出すると862,195点、当時のランキングで13位です。やったね！

事象の解説

まず、何が起きているのか確認します。下記は同じ入力に対しての途中の状態です。なだらかな坂が形成されており、連続で長く崩せる状況であることがわかると思います。

このような状況が起きる理由を下記イメージ図で説明します。

上記のように優先順序を変えるだけで、終盤になるに連れその差は顕著に現れます。
これが魔法の正体です。

最後に

ここまで読んで頂きありがとうございました。アルゴリズムではなく、データ空間の大局を捉えるというマラソン形式のコンテストの面白さが伝われば幸いです。
また、弊社では2018/02/17（土）に、同様の形式でのマラソン形式のコンテスト「Hack To The Future」の予選を開催予定です。
本記事で紹介したように、難しいアルゴリズムや高い数学力・実装力がなくとも、上手く問題の性質を掴むことで1ページ目の順位、つまり決勝のオンサイト出場権を手に入れることができる可能性があります。
興味を持たれた方は、是非その腕前をご披露下さい。

以上