はじめに

普段 AtCoder Beginner Contest (ABC) などアルゴリズム系の競技プログラミングのお世話になっています。

8/24 の ABC368 参加ボタンを開催直前に押そうとしたところ、うっかり同時開催中の AtCoder Heuristic Contest (AHC) 036 の参加ボタンを押してしまいました。 ¹

ヒューリスティック。アルゴリズム系と違い、最適な答えを求めるのは難しくて、制限時間内によさげな解を探すというものです。詳しくは AtCoder の紹介をどうそ。

AHC036 提出締め切りまで 1週間以上。この締め切りの長さが怖いところ。まあでもできる範囲で頑張りますか…… と試してみました。

そうしたところ、そこまで AHC 怖くない、実装速度タイムアタック要素が少ないからふつうのプログラミング (?) に近いかも、という感じでした。そんな初参加の記録をまとめた参加記です。

概要

AHC036 を Rust で参加した記録です
使った技術:
- Floyd-Warshall
- 4分木
- Hilbert Order
振り返り、反省点
- 複数回調べられる実装になっていない
  - 探索自由度が高いままで、1回の試行が遅すぎ
- 分析方法が分からない、バグに気づかない
  - Visualizer を WA 検出にしか使えなかった
感想

問題の解説はほかの方にお任せします。

日ごと

8/24(土) 参加

AHC 参加ボタンを押しただけです。頭を抱えながら ABC368 に挑んでいました。

8/25(日) 問題を読む、C++ の実装を写経して通す

問題ページに C++, Python のサンプルコードが付いていました。これをそのまま提出すれば点数がもらえます。これをもとに調整すれば良い。優しい！

Rust はありません。写経します。ラムダ式の再帰以外はそのまま書けました。

0点は免れました。祝。

サンプルコードが何をしているかと言うと:

A = [0, 1, 2, ..., n - 1, 0, 0, ...] のように各頂点 1個ずつ登録している
- ★1: 後ろの方は使っていない。隣接関係も使っていない
次に進む pos_to を読み込む
pos_to に向かうパスの 1つを、2次元座標でゴールに近い方を優先する、深さ優先全探索で探す
- ★2: 最短のパスとは限らない
そのパス 1歩ずつに対して、 B を A から 1つずつコピーしてきて、信号を切り替える
- ★3: B の長さは 4～24 あるのに、最初の 1つしか使っていない

いろいろ問題点が見つかります。この ★ をつぶしていけば、参加者の半分くらいの順位にはなりそうかな、という期待を持ちました。

日	スコア
8/25	431,876

小さなスコアほど良い問題です。ここをベースラインとして、スコアを減らす方法を考えていきます。

8/26(月) `A` の並びを近いもの順に変える、`B` を全部使う

★3: B の長さは 4～24 あるのに、最初の 1つしか使っていない

B の長さすべてコピーするようにします。1個コピーも、並んだ24個コピーも、おなじ 1手分のコストです。まとめてコピーして、かつそのコピーした信号が次の手に辿るものなら、コピー回数が減ってお得です。

このためには、「A の並びが、辺でつながっているものが近くにあると良い」となります。

そこで最初、4分木として並び替えることを考えました。 (1024, 1024) の座標を「縦に 2分割 → 横に 2分割 → 縦に 2分割 → 横に 2分割 → ……」した数字順で 1次元に並び替えれば、と。再帰的に解像度を上げていく感じです。 3D やっている人は LoD (Level of Detail) の雰囲気です。

並び替えました。

fn build_a(la: usize, xy: &[(usize, usize)]) -> Vec<usize> {
    let mut v = Vec::new();
    v.reserve(xy.len());

    for (i, &(x, y)) in xy.iter().enumerate() {
        let mut z = 0usize;
        for j in 0..10 {
            if x.bit_test(j) {
                z |= 1 << (j * 2);
            }
            if y.bit_test(j) {
                z |= 1 << (j * 2 + 1);
            }
        }
        v.push((z, i));
    }
    v.sort();

    let mut results = vec![0; la];
    for (i, &(_, j)) in v.iter().enumerate() {
        results[i] = j;
    }
    results
}

また、 1つだけコピーしていた B を、幅 lb の分だけまとめてコピーするようにしました。 1次元の順番で、次に進みたい場所が cur, 移動先が pos_to なら、移動先に近づくように cur.. または ..=cur の配列を選びます。

これでスコアが大幅に小さくなりました。

日	スコア
8/25	431,876
8/26	182,930

8/27(火) パスの探索方法を変える / 初手を増やす

サンプル実装では、DFS で最初に見つかったパスだけを調べていました。しかし、 2次元座標でゴールに向かう方がお得とは限りません。あとから遠回りするかもしれません。

fn dist2((x0, y0): (usize, usize), (x1, y1): (usize, usize)) -> usize {
    x0.abs_diff(x1).pow(2) + y0.abs_diff(y1).pow(2)
}

信号を変えずに辿れるところすべてから DFS するとか、少し書き換えてみましたが、あまり大きくは変わらず。

日	スコア
8/26	182,930
8/27	144,093

辺の数が少ないパスを DFS で探してみても、信号の状態によってはスコアが下がるわけではない、ということで試行錯誤していました。

8/28(火)～31(土)昼パスの探索方法を変える / 最短パスにする

★2: 最短のパスとは限らない

ここを改めて考えます。

サンプル問題のグラフです。双方向グラフです。

このパスがスコア増につながるかは信号の状態によります。

たとえば配列 A が [5, 6, 0, 4, 3, 2, 1] のように並んでいて、連続する信号 4 つを on にできる場合には、信号 B を適切に選ぶことで 6 → 1 以外はすべて 1手で辿ることができます。 6 → 4 と辿るときには B を [0, 4, 3] とすれば、6 → 0 → 3 → 4 ができます。他の辿り方もあります。

このように「1手で動ける範囲」を用意しておけば、BFS が最短経路をたどるように動かせるはずです。

ワーシャル–フロイド法 - Wikipedia

変数が多そうなので、Floyd-Warshall 法を使いました。頂点数 600 なら $O(N^3)$ もあまり怖くない。 ²


fn build_d(graph: &[Vec<usize>], groups: &[BTreeMap<usize, usize>]) -> Vec<Vec<usize>> {
    let n = groups.len();
    let mut d = vec![vec![n + 1; n]; n];
    for i in 0..n {
        d[i][i] = 0;
    }

    for (u, v) in graph.iter().enumerate() {
        for (&v, _) in &groups[u] {
            d[u][v] = d[u][v].min(1);
        }

        for &v in v {
            for (&v, _) in &groups[v] {
                d[u][v] = d[u][v].min(1);
            }
        }
    }

    floyd_warshall(d)
}

fn floyd_warshall(mut d: Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let n = d.len();
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                d[i][j] = d[i][j].min(d[i][k] + d[k][j]);
            }
        }
    }
    d
}

バグ埋め込みすぎで 4日かかりました。Visualizer にサンプル出力を入れてみたら、ここはつながっていないなど指摘され続けまして。ほんと、なんとか動いて良かった……。

日	スコア
8/26	182,930
8/31 18:00	104,670

8/31(土) 夕方 `A` の後ろ側に長い道路を入れる

ここまでに A の先頭 N 要素を、2次元座標が近い頂点を 1次元配列としても近くなるように埋めました。後ろの方はまだ使っていませんでした。

後ろ側は高速道路のように、縦横まっすぐ伸ばすような道路を余裕がある限りたくさん埋めてみました。

この結果です。速くなりました。

日	スコア
8/31 18:00	104,670
8/31 19:37	86,603

いったん ABC369 (21:00-22:40) に移ります。AHC で頭がいっぱいだからと Unrated で。

8/31(土) 夜 4分木をヒルベルト曲線にしたつもり

A の配置は近いものが固まっていそうです。でもそれで十分かを、ここで確認します。

2つの問題点に気づきます。

7 → 8 のように、1次元では近くても 2次元では大きく移動する場所がある ★4
2次元的に近くてもグラフの接続関係としては近いとは限らない ★5

★4 を考えます。 4分木ではたしかにこのように飛ぶことがありますが、飛ばなくてもいい配置があるはず。なんかそういうのを曲線で平面を埋め尽くすフラクタル図形で見たことがあるような……。

ここでネット検索。

ああ、ヒルベルト曲線。ならきっと、ヒルベルト曲線を使って 2次元の頂点を 1次元に並び替えるというのも、誰かやっているはず。

さらにネット検索。

これです！ありがたく拝借します。

fn hilbert_order(mut x: usize, mut y: usize) -> usize {
    const MAX: usize = 1 << 10;
    let mut d = 0;
    let mut s = MAX >> 1;
    while s > 0 {
        let rx = (x & s) > 0;
        let ry = (y & s) > 0;
        let r = (if rx { 3 } else { 0 }) ^ (if ry { 1 } else { 0 });
        d += s * s * r;
        s = s >> 1;
        if ry {
            continue;
        }
        if rx {
            x = MAX - 1 - x;
            y = MAX - 1 - y;
        }
        swap(&mut x, &mut y);
    }
    d
}

次のような並び替えになります。常に 2次元座標が隣り合います。

これでスコアは？

日	スコア
8/31 19:37	86,603
9/01 00:17	84,509

少しよくなっているけれど全然期待ほどではない……。まあ先に進みます。

期待ほどよくなっていなかったのは、写経を間違えてちゃんと隣になっていなかったためでした、この参加記を書いている途中に気づきました。う……。

9/1(日) A の順番を少し入れ替える、A の後ろ側の並びを調整

2次元的に近くてもグラフの接続関係としては近いとは限らない ★5

この対策として、A の配列で近い 2点を選んで、入れ替えた方がスコアが良くなりそうなら入れ替える、というのを行います。締め切り 1日前にしてようやくヒューリスティックコンテストの入り口にたった気分です。ぜんぜん実装時間が足りません。複数回調べて一番良いものを出力する、なんてことはできません。

「入れ替えた方がスコアが良くなりそうなら」は、本当に入れ替えて最短手数を調べると時間がかかりすぎます。そこで、隣接関係だけを見て評価関数を作りました。評価関数と最後の結果があっているかは調べられていません。

ないよりはマシだけれど、すごく怪しい評価関数と順番入れ替えでした:

// 少し順番を入れ替える
let n = graph.len();
for diff in [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1] {
    for i in 0..(n - diff) {
        let mut score0 = 0; // 入れ替え前
        if i >= diff && graph[a[i]].contains(&a[i - diff]) {
            score0 += 1;
        }
        if i < n - diff - 1 && graph[a[i + diff]].contains(&a[i + diff + 1]) {
            score0 += 1;
        }

        let mut score1 = 0; // 入れ替え後
        if i >= diff && i < n - diff && graph[a[i + diff]].contains(&a[i - diff]) {
            score1 += 1;
        }
        if i < n - diff - 1 && graph[a[i]].contains(&a[i + diff + 1]) {
            score1 += 1;
        }

        if score0 < score1 {
            a.swap(i, i + diff);
        }
    }
}

A の後ろ側の並びを縦横の高速道路と環状線みたいな感じに入れ替えて、ほんの少しスコアを改善し、これで終了です。

こんなイメージでした。ヒルベルト曲線の画像は Wikipedia より。赤い点は追加道路で、この問題についてはあまり数が設定できず途中で打ち切りでした。

日	スコア
9/01 00:17	84,509
9/01 22:03	82,384

お疲れさまでした。

振り返り、反省点

いろいろ経験不足を感じました。

複数回調べられる実装になっていない

次のように進めました。

どこで切っても良いような A を決める (すぐ終わる) ★
- 頂点の一筆書きに近くなるようにヒルベルト順を使って並び替える。そうすればどこで切っても近い点が並び、一回の信号切り替えで複数の場所を辿れるはず
- ヒルベルト順は近い範囲に集まるはずなので、遠くに辿りやすい道路を追加で用意する
A を使った最短の信号切り替えを最も少ないと何回で 2頂点間を移動できるか、すべての組み合わせを Floyd-Warshall 法で調べる (0.3秒ほど)
それをもとに問題設定の通り頂点間を移動し続け、B を更新しつつ標準出力に結果を出す (すぐ終わる)

試行錯誤ができるとすると 1. です。2. と 3. は試行錯誤がありません。でも、 2. の手順で最短の信号切り替え回数を調べようとすると 1回ですごく時間がかかります。1. で評価関数を設定しても、それが本当に 2., 3. で良い感じになるのか分かりません。

試行回数を増やせるように、たとえば「どこで切っても近い点が並び」というのをやめて、次のような方法もありました。

A を、B の長さ lb 単位の切り替えグループとする。A[(i*lb)..((i+1)*lb)] ができるだけ辺で連結するようにする
近い 2頂点を適当に入れ替えを試す。グループの連結性が今まで以上になりそうなら、グループを何回移動するかをやってみて、良ければ実際に変える。グループがまとまっているので探索空間が狭く、1回あたり高速なはず
制限時間に近づいたら、一番良さそうな手順を具体的に 1歩ずつ作る

ヒューリスティックコンテストと言うと、焼きなまし法とかビームサーチみたいな、良さそうな試行を効率的に行う方法を適用というイメージです。そこまで全然たどり着きませんでした。

そこまでは難しくても、A の後ろ側の並び方を4通りほど置き換えて一番良さそうなものを採用するくらいはできると良かったなというのは、反省点です。最短パスを求めるところまで動いたのが締め切り 2日前だと思うと、高望みかもです。

分析方法が分からない、バグに気づかない

今回実験に使ったデータは、問題文中のサンプルと、Visualizer 初期データの 2つでした。これ以外は全然見ていません。B の長さが違った時にどういう動きをするのかも調べられませんでした。

Visualizer の実行も、ここからロジックの弱いところを見つけることはできず、ただ WA にならないことを確認するツールにだけなっていました。勿体ない。

これからほかの方の参加記を見て、どうやっているのか知りたいところです。

できる範囲で可視化や単体テスト書きをするのが良かったです。この参加記を書いているときにヒルベルト曲線が間違っていることに気づき、2行直したところスコア更新。

さらに追加道路も思った通り動いていませんでした。こちらも書き換えたところスコア向上。これはひどい。いつもアルゴリズム系コンテストでバグと戦っているのに、ヒューリスティックが確認せずに期待通り動くわけがないのでした……。

日	スコア	延長戦順位
9/01 00:17 提出版	82,384	267
9/07 ヒルベルト修正版	78,903
9/08 追加道路修正版	77,870	239

追加道路修正版のコードです。

アルゴリズムコンテストだと WA や TLE という形で気づけるところが、ヒューリスティックだと一部間違っていても答えが出てしまいます。難しいです。

最後に

いろいろと準備不足や反省点はあるものの、完走できて良かったです。ヒューリスティックは参加する敷居が高いと思っていました。本当にうっかりですが、良いきっかけになりました。次に挑戦するときには、もう少しうまくできるんじゃないかなと思います。

ヒューリスティックコンテストは社会人に向いている、という話を以前聞いていました。アルゴリズム系のように典型を覚えていなくても挑めます。ゆっくり考えて試行錯誤できます。なんなら今回の問題はベースの実装があって、評価関数をちょっと書き換えるだけでもスコアが良くなります。たしかに気楽です。

その分やれることがいくらでもある、時間泥棒でした。いやほんと。

AHC コンテスト後の X (Twitter) 等での方針公開わちゃわちゃ感が楽しいです。アルゴリズム系も楽しいですけれど、アルゴリズム系では近い話に落ち着くことが多く。ヒューリスティックは本当に様々で、1週間考えても全然思いつかなかったことにぽろっと気づかされます。この記事もそんな 1つになっていればいいなと思います。

ここまでで初参加記を終わります。この記事を見てヒューリスティックコンテストに興味を持つ方、参加する方がいると幸いです。

あまり調子が良くないから ABC に Unrated で参加しようとしたら、参加登録後に Unrated ボタンがなくて気づいたという……。うっかりすぎます。 ↩
普段は重み 1 固定の Dikstra として 01-DFS することが多いです。今回は辺の数が多そうだったため、Floyd-Warshall してみました。コンテスト後に 01-DFS も試したところ、Floyd-Warshall の方がすこし高速でした。 ↩