mooakiのブログ

貪欲に出来ることはまだあるかい?乱択に出来ることはまだあるかい?

AHC014でとりあえず貪欲法を書くまでの話

経緯

AHC014 が終わった翌日、地域の焼肉イベントが感染対策に配慮しつつ行われまして、そこで近所に先日出来たばかりのクラフトビール工場のビールも振舞われまして、要するに酔ってたんですね。

こんなことをつぶやいてしまったら「じゃあお前はどうやってんだ」って、まぁ、なりますね。あーあ。

AHC014では 111位、TopCoderMarathon Match も参加してますが順位表の真ん中へんをうろうろし続けてるだけで、決してヒューリスティック/マラソンが強い訳ではないので自分のやり方をマネして強くなれる保証は一切ないのですが、晒してみれば「そこは無駄だろ」とか「自分のこの実装の方が良い」とかの見識の呼び水になるやもしれんと自分に言い聞かせて、AHC014を題材にとりあえず貪欲までを書いてみることにします。言語は競プロで使える言語界の絶対王者 C++です。クラスや変数の命名規則がメチャクチャですがご容赦ください。

プログラムの下準備

これは自分もまだ試行錯誤中ですが、Solverクラスのsolve()関数に実際の解法を書くようにして main() からそれを呼び出してます。

Solver クラス

class Solver
{
    public:

    Solver() {};

    void init() {
        cin >> N;
        cin >> M;

        nei8rc = vector<vector<int>>(N * N, vector<int>(8));
        // 8近傍事前計算
        rep(r, N) {
            rep(c, N) {
                rep(dir, 8) {
                    int r0 = r + DR8[dir];
                    int c0 = c + DC8[dir];
                    if(inside(r0, c0)) { // グリッドの内側か判定するマクロ
                        nei8rc[RC(r, c)][dir] = RC(r0, c0);
                    } else {
                        nei8rc[RC(r, c)][dir] = OUTSIDE;
                    }
                }
            }
        }
    }

    void solve() {
        srand(time(NULL));
        init();
        STATE state;
        state.input();
        state.init();
        state.make_answer();
        state.output();
    }
};

「8近傍事前計算」というのは bowwowforeachさんの

というアイデアを拝借したものです。ありがとうございます。これを使うとp1からdir方向にあるp2まで辺を張る関数は

    void draw1(int p1, int p2, int dir) {
        for(int p = p1; p != p2; p = nei8rc[p][dir]) {
            set_con(p, dir); // 点pからdir方向に辺を張る
        }
    }

みたいに書けます。dir方向にp2がないとバグりますが、p1からdir方向にある印がp2のはずなのでチェックは省略してます。

STATE クラス

また、現在の状態を表すものは STATE クラスにまとめておきます。AHC014 で言うとグリッドの印の有無、辺の有無、その時点での解、スコアなどです。

class STATE {
    public:
    Grid g;
    vector<Answer> ans;
    int score;
    set<int> points;
    vector<vector<int>> near_point;
   // 以下略
};

Grid クラスはそのまんまグリッドのクラスです。Marathon Match ではグリッドの問題が多いので基本的なのをテンプレファイルに書いて使いまわしてます(詳しくは後述)。Answer クラスは一回分の解を持つクラス(今回だと p1,p2,p3,p4)で、そのvectorとして一連の解を保持します。points はその時点で探索する点で、最初は読み込んだ点をすべて追加して、印をつけるたびに追加したり、もう四角を作るのに使えなくなった点は除外したりします除外はするつもりだけでしてませんでした(^^;。near_point は各印の8方向の最寄の印です。これも初期化時に求めておいて、新しい印をつけるたびにその8方向上の点についてだけ更新します。こうすることで各印からの8方向の印をいちいちグリッド上で探す必要がなくなります。

Grid クラス

class Grid
{
    public:
    int N;
    vector<int> grid;
    Grid() {}
    Grid(int n) {
        N = n;
        grid.resize(n * n);
    }
    // 略
    int& operator[](int i) {
        return grid[i];
    }
};

grid は各点の印の有無と8方向の辺を int の各ビットに対応させて1次元ベクターで保持しています。

#define DIR_R  0x0001
#define DIR_RD 0x0002
#define DIR_D  0x0004
#define DIR_LD 0x0008
#define DIR_L  0x0010
#define DIR_LU 0x0020
#define DIR_U  0x0040
#define DIR_RU 0x0080
#define MARK   0x0100

と各ビットを定義しておいて

    // 点rcからdir方向に辺を張る
    void set_con(int rc, int dir)   // setConnect にするべきでは?
    {
        int nrc = nei8rc[rc][dir];
        int rdir = (dir + 4) % 8;
        assert(nrc != OUTSIDE);        
        grid[rc] |= (1 << dir);
        grid[nrc] |= (1 << rdir);
    }
 
    // 点rcのdir方向の辺の有無
    bool isConnected(int rc, int dir)
    {
        return (grid[rc] & (1 << dir)) != 0;
    }
 
    // 印をつける
    void setMark(int rc)
    {
        grid[rc] |= MARK;
    }
 
    // 印の有無
    bool isMarked(int rc)
    {
        return (grid[rc] & MARK) != 0;
    }

といった関数でアクセスします。余談ですが、こういう変数名や関数名で毎度悩んだあげく微妙な命名をしてしまって本当に恥ずかしいのですが、提供されているビジュアライザのソースを参考にすればいいのかもしれないと今回のコンテスト中に思いつきました。次回からそうしてみようと思います。

また[]演算子をオーバーライドすることで

    Grid g(N);  // N*N のグリッド
    g[x * N + y] = 0;
    //g.grid[x * N + y] = 0;

の様に書けます。実際は[]の中が毎回書くのは面倒だしたまにバグらせるので

#define RC(r, c) ((r) * N + (c))
#define R(rc) (rc / N)
#define C(rc) (rc % N)

とマクロ定義することでg[RC(x, y)] = 0と書けるようにしています。Gridクラス自体の配列を作ったら不具合ある気がしますが、今のところそれをしたことはないので、とりあえずOKです(は?)。

下準備はこんなところですかね。

貪欲法で解を作る

下準備ができたので、いよいよ何かしら解を作って出力します。まず作れる四角をリストアップし、その中から1つを出力するのを繰り返すことにします。

たまたま解説放送と同じだったのですが、各印をp3としてdir方向にある点をp2、dir方向から90°回転した方向をdir4、dir4方向にある印をp4としてp1を求め、辺を共有してないか、途中に印がないかなど確認する関数canMakeRect()を書きます。

    // 出来ないなら -1、できるならp1
    int canMakeRect(int p3, int dir) {
        int p2 = near_point[p3][dir];
        int dir4 = (dir + 2) % 8;
        int p4 = near_point[p3][dir4];
        if(g.isConnected(p3, dir)) return -1;  // p2方向にすでに辺がある
        if(g.isConnected(p3, dir4)) return -1; // p4方向にすでに辺がある
        if(p2 == OUTSIDE || p4 == OUTSIDE) return -1; //p2,p4方向に印がない
        if(g.isConnected(p2, dir4) || g.isConnected(p4, dir)) return -1; // p2からp1方向またはp4からp1方向に辺がある
        int p1x = R(p4) + R(p2) - R(p3);
        int p1y = C(p4) + C(p2) - C(p3);
        int p1 = RC(p1x, p1y);
        if(g.isUsed(p2, p1, dir4)) return -1; // p2,p1間に印がある
        if(g.isUsed(p4, p1, dir)) return -1;  // p4,p1間に印がある
        if(g.isMarked(p1)) return -1; // p1に印がある
        return p1;
    }

これを使える印それぞれに8方向で調べ、対角のマンハッタン距離が一番小さいものを解の一つとします。

    int  make_answer1()
    {
        //          dist,     p3 , dir
        vector<pair<int, pair<int, int>>> candi; // 候補を入れる
        for(auto p3 : points) {
            rep(dir, 8) {
                int p1 = canMakeRect(p3, dir);
                if(p1 >= 0) {
                    int dist = abs(R(p1) -R(p3)) + abs(C(p1) - C(p3));
                    candi.push_back({dist,{p3, dir}});
                }
            }
        }
        if(candi.size() > 0) {
            sort(candi.begin(), candi.end());
            int idx = 0;
            draw(candi[idx].second);
            return candi[idx].second.first;
        }
        return -1;
    }

これを候補がなくなるまで(-1が返ってくるまで)繰り返します。

    void make_answer()
    {
        int res;
        do {
            res = make_answer1();
        } while(res >= 0);
    }

これで Seed=0 では629389点。 提出すると 32629578 点になります。とりあえず貪欲法できました。

まとめ

コンテスト中に「縦横の四角が作れるようになったので次は斜めを実装」というツイートを見た気がするのですが、四角の向きごとに判定するルーチンを書くとコード量もバグを埋め込む可能性も増え、デバッグに費やす時間も増えがちです。今回やったように点と向きで縦横も斜めも同じく判定できるようにすればコード量もデバッグ時間も減らせ、より高度な解法に取り組む時間が増やせるかもしれません。同じようなコードを何度も書いているのに気付いたら「これは一般化できないか?」と考えてみるといいかも知れません。怠惰はプログラマの三大美徳の一つですしね。

今回のコードの改良の先に順位表1ページ目があるかは自分の実力ではわかりませんし、次の AHC でそのまま使えるということもないとは思いますが、何か一つでもヒントになったり、話題の呼び水になれば幸いです。不慣れで分かりずらい記事になってしまったと思いますが読んでいただきありがとうございました。