nakashiiiの自由帳

自由に書きます

【初参加】AtCoder Heuristic Contest 011 参戦日記 (Sliding Tree Puzzle)

競プロ AHC

はじめてヒューリスティックコンテストに参加したので、忘れないうちに感想とやったことをまとめたいと思います。
参加時の状態はこんな感じです。

上記の通り、ヒューリスティックコンテストは初参戦で、なおかつ事前予習ゼロでした。
「とりあえず参加して、なんとなく動くアルゴリズムを提出できれば OK」
という感じで、あまり気負わず参加しました。

予習がなくて大丈夫かな？という不安もありましたが、思ったよりも雑に提出できてとっても楽しめました。
アルゴ灰〜緑くらいで「参加してみたいけど、何すればいいか分からないな、、」という人の参考になればうれしいです。

ちなみに本記事は

の 3 部構成ですので、興味のあるところを適当に読んでいただければと思います。

目次

今回の問題

A - Sliding Tree Puzzle

ざっくり言うと、

  • N*N の盤面が与えられるので、時間内に「なるべく大きい木」をつくってください

という問題です。 ここで「木」というのは、以下のようなグラフを指します。

  • 閉路がない
  • 連結である
  • 木の大きさ = 頂点数

空白マスを 1 マスずつ移動しながら, 規定の操作回数以内で木を作っていきます。
以下の動画見るとイメージが掴めると思います。

AHC011 ビジュアライザ

まず感想

いきなり感想なのですが、想像していたよりずっと楽しかったです！！！
普段はアルゴの ABC のコンテストをメインに競プロを楽しんでいるのですが、それとは違った楽しさがありました。
以下、楽しかったポイントです
（感想なんかいいから、何やったの？という方は、こちら に飛んでください）

  • 自分の書いたアルゴリズムがビジュアライザで動く
  • 最高得点がスコアになるので, 雑に提出できる
  • どんどん点数がよくなる

自分の書いたアルゴリズムがビジュアライザで動く

公式からブラウザで動作するビジュアライザが提供されているので、答えをそこに貼り付けるだけで、 ぐるぐると自分の書いたアルゴリズム通りに、マスが移動します

試しにこちらの文字列 RRRDLUULDDDDLUUUR を以下の URL の「Output」のとこに貼って、再生ボタンを押すと動く様子が分かります。
https://img.atcoder.jp/ahc011/df8bb452a2.html?lang=ja

自分が書いたプログラムの動きが目で見て分かるというのは、けっこう感動します。 はじめて動いた時はすごくテンションがあがりました！

最高得点がスコアになるので, 雑に提出できる

アルゴのコンテストだと WA や TLE するとペナルティがあって、レーティングに響きます。したがって、提出する時は慎重に動作確認が必要で、緊張感があります
一方ヒューリスティックの場合、WA や TLE してもすぐに自分のスコアが下がることはありません。最終的なスコアは、「最後の提出に対するシステムテストのスコア」のみで決まります。

つまり、最終的に AC するコードを書けてればよく、それまでは WA し放題なのです！！！やったね！！（ただし、最終提出から 30 分の提出制限があります）

そのため、「スコアよくなるか分からないけど、ちょっと実装内容変えてみた」みたいなのをガンガン試せます！ このあたりもヒューリスティックコンテストならではだな、と感じました。

どんどん点数がよくなる

取り組み方にもよると思うのですが、私の場合は、
雑な動くコードを提出する → 改善できそうなところを直す → 再提出する → 改善できそうなところを直す → ...
という感じで進めていったので、頻繁にスコアが上昇して楽しかったです。

スコアの遷移は以下のような感じです。（後半あんまり伸びてないですね、、）
5/28 14 時: 2,869,199
5/31 14 時: 5,180,532
5/31 19 時: 8,285,682
6/02 14 時: 9,485,743
6/02 19 時: 10,311,706
6/03 06 時: 11,095,544
6/03 13 時: 11,688,503
6/04 09 時: 11,903,356

感想まとめ

ヒューリスティックコンテスト初参加してみて、思っていたよりかなり参加するハードルが低いと思いました。
具体的には以下です。

  • 事前予習なし、環境構築なし（いつも競プロやる環境だけ）
  • 長期コンテストなら自分が取り組みたいタイミングで取り組める
  • レーティングが下がらないので、精神的に気楽

楽しかった点ばかりでも微妙なので、ヒューリスティックコンテストで個人的なデメリットを挙げるとすると以下です。（本当は無いですが、無理やり挙げてみます）

  • 参加中は解法に関する言及が一切できないので、ムズムズする（Twitter 見ると、なんだかムズムズしてます笑）
  • 長期だと無限にやることが湧いてくるので、時間を溶かしすぎる
  • アルゴの精進時間をヒューリスティックにあてなきゃいけないので、次回の ABC がちょっと不安

けっこう参加ハードル低いと思うので、気になっている方はぜひ次回一緒に参加して楽しみましょう！！

実装内容の解説

ここからは実際にやったことの解説です。
言語は C++です。

おおまか方針としては、「ランダムに盤面を探索して、大きい木の盤面を残していく」という感じです。
アルゴリズム分類的には「乱択」＋「山登り」になるのかな？（詳しくないので、間違ってるかもです、、）
ざっくり以下となります。

  1. 評価関数を用意しておく
  2. 盤面をランダムに探索する
  3. 盤面のランダム探索を繰り返しながら、徐々に木を大きくしていく

以下は上記を図にしたものです。

探索1回目

探索2回目

1. 評価関数を用意しておく

まず問題を解くにあたって現在のスコア(= 木のサイズ)を測定できる必要があります。
いくつかやり方があると思いますが、今回は UnionFind で実装しました。

  • UnionFind で接続できるマスを併合する
  • 併合する時に閉路があれば, スコア無しにする

また、盤面は問題文の通りに 1 マスを 4bit で表現しています。

マスとbitの対応関係（AHC011 問題文より引用）

実装は以下です。

// マス目は4ビットで持つ
using bs = bitset<4>;

/**
 * @brief 盤面を受け取って, 最大の木を返す
 *
 * @param bits 判定する盤面
 * @return vector<int> 最大の木のマス目の集合
 */
vector<int> get_max_size(vector<bs> bits) {
  dsu uf(n * n);                         // 連結・閉路判定用
  vector<bool> is_cyclic(n * n, false);  // ufの親を閉路かマーク

  // 右と下だけ見ていく (盤面外に注意)
  vector<int> dx = {1, 0};
  vector<int> dy = {0, 1};
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int idx = (i * n) + j;  // 現在の位置
      for (int k = 0; k < 2; k++) {
        int nx = i + dx[k];
        int ny = j + dy[k];
        int nidx = (nx * n) + ny;  // 次の位置
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        // 下
        if (k == 0 && (bits[idx] & bs(0b1000)) != bs(0b0000) &&
            (bits[nidx] & bs(0b0010)) != bs(0b0000)) {
          // 閉路判定
          if (uf.same(idx, nidx)) {
            is_cyclic[uf.leader(idx)] = true;
            is_cyclic[uf.leader(nidx)] = true;
          }
          // 併合
          uf.merge(idx, nidx);
        }
        // 右
        if (k == 1 && (bits[idx] & bs(0b0100)) != bs(0b0000) &&
            (bits[nidx] & bs(0b0001)) != bs(0b0000)) {
          // 閉路判定
          if (uf.same(idx, nidx)) {
            is_cyclic[uf.leader(idx)] = true;
            is_cyclic[uf.leader(nidx)] = true;
          }
          // 併合
          uf.merge(idx, nidx);
        }
      }
    }
  }

  // 最大の木の要素集合を返す
  int ans_len = 0;  // 木のサイズ
  vector<int> ans_vec;

  for (auto vec : uf.groups()) {
    // 閉路があれば, スコア無し
    int root = uf.leader(vec.front());
    if (is_cyclic[root]) continue;
    // 最大の木を更新
    if (chmax(ans_len, (int)vec.size())) {
      ans_vec = vec;
    }
  }

  return ans_vec;
}

2. 盤面をランダムに探索する

評価関数ができたら, いよいよランダムに盤面を探索します
おおまかなアルゴリズムは以下です

  1. 上下左右 4 方向のうち, 次に移動する方向をランダムに決める
  2. 実際に動かしてスコアを計算
  3. もし最大スコアなら, 現在の {スコア, 移動経路, 現在の盤面} を保持しておく

以下、いくつか工夫した内容です。

前の位置には戻らないようにする

ランダムだけど、なるべく効率よく探索したいので、自分が前にいた位置には戻らないようにしました。
前の位置に戻ってしまうと、移動回数は増えるのに、盤面は全く変わらないためです。

ひとつ前には戻らない

確定した盤面には到達できないようにする

すでに確定した盤面に対しても、移動を禁止しました。すでに確定した盤面よりも大きな盤面にしていくためです。

確定しているマスは探索しない

同じ場所から動けなくなったら探索を打ち切る

  • 前の位置には戻らないようにする
  • 確定した盤面には到達できないようにする

この２つの制約によって、同じ場所から動けなくなることがあります。
そのため、同じ場所から動けない場合は探索打ち切りとしました。

動けなくなったら、探索を打ち切る

壁面のところはいつでも通れるようにしておく

確定した盤面には到達できないようにすると、空きマスが狭いエリアに閉じ込められることがあります。
そのため、壁際のエリアは常に探索を許可することにしました。

壁際のみを許可としたのは、以下の理由です。

  • 実装が簡単
  • 壁際のみなので、ランダムに動くよりは木のサイズを小さくしない

壁面は常に探索OKにする

というわけで、実装は以下となります。

/**
 * @brief ランダム探索の結果
 *
 */
struct Result {
  int score;             // 木のサイズ
  string moving;         // 移動経路
  vector<char> ng_grid;  // 最大の木の位置をマークした盤面
};

/**
 * @brief 空きマスをランダムに動かして, なるべく大きな木をつくる
 *
 * @param bits 探索する盤面. 最終的に最も大きい木をつくれる盤面に変更する
 * @param x_ini 空きマスの初期 x座標
 * @param y_ini 空きマスの初期 y座標
 * @param ng_grid 確定済みの盤面
 * @return Result
 */
Result random_seach(vector<bs> &bits, int x_ini, int y_ini,
                    vector<char> ng_grid) {
  string moved;                        // 移動経路
  auto max_tree = get_max_size(bits);  // 最大の木
  int score = max_tree.size();         // 最大の木の大きさ
  int max_cnt = 0;             // 最高値を記録した時の, 移動回数
  int move_cnt = 0;            // 移動回数
  int px = IINF, py = IINF;    // 一つ前の位置
  int x = x_ini, y = y_ini;    // 現在の位置
  vector<bs> bits_max = bits;  // 最大スコアの盤面
  vector<char> ng_grid_max = ng_grid;  // 最大スコアの探索NG盤面
  int loop = 0;       // 同じ場所をぐるぐるしているかを判定
  int limit = t / 2;  // 探索回数の上限

  // 適当にたくさん探索する
  while (move_cnt <= limit) {
    loop++;
    // 適当に進む
    int next = get_random(0, 3);
    int nx = x + dx[next];
    int ny = y + dy[next];
    int nidx = (nx * n) + ny;  // 次の位置
    int idx = (x * n) + y;     // 現在の位置

    // もう1回進むところガチャ
    if (loop > 20) break;  // 同じ場所から抜け出せなくなっている
    if (px == nx && py == ny) continue;  // 前と同じ位置には戻らない
    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;  // 盤面外
    if (ng_grid[nidx] == '#') continue;                    // 確定済み
    loop = 0;  // 動けるので, loopを初期化

    // 移動を記録
    moved.push_back(dir[next]);

    // 入れ替えてスコアを計算
    move_cnt++;
    swap(bits[idx], bits[nidx]);
    auto tmp_tree = get_max_size(bits);
    auto tmp_ng_grid = make_char_grid(n, tmp_tree);
    int tmp_score = tmp_tree.size();
    if (chmax(score, tmp_score)) {
      if (move_cnt > t) break;  // 操作回数はtを超えないようにする
      max_cnt = move_cnt;       // 移動回数
      bits_max = bits;          // 最大スコアの盤面
      ng_grid_max = tmp_ng_grid;  // 最大スコアの探索NG盤面
    }

    // 位置を記憶
    px = x, py = y;  // 一つ前の位置
    x = nx, y = ny;  // 現在の位置
  }

  // 最大スコアの盤面に戻す
  bits = bits_max;

  // {スコア, 移動経路, 現在の盤面}
  return {score, moved.substr(0, max_cnt), ng_grid_max};
}

3. 盤面のランダム探索を繰り返しながら、徐々に木を大きくしていく

ここまでで盤面のランダム探索ができるようになったので、あとはそれを適当に繰り返していくだけです。
以下の手順で徐々に木を大きくします。

  • ランダム探索を 50 セットくらい繰り返して, 一番大きな木の盤面を探す
  • 一番大きな木の盤面を初期盤面として, またランダム探索をする(すでにできた木のマスへは移動不可とする)
  • 上記を 10 セットくらい繰り返して、徐々に木を大きくする

これを1セットとして、10セットくらい繰り返す

実装はこちらです。

int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  // 入力
  cin >> n >> t;
  vector<string> s(n);
  for (int i = 0; i < n; i++) cin >> s[i];

  // 探索する盤面初期化
  vector<bs> bits_now = convert_bit_vector(s);  // 入力をbitsetに変換
  vector<char> ng_grid_now = make_char_grid(n, vector<int>());  // 探索NG判定用

  // 探索回数の設定. 数値は動作見ながら微調整
  int limit = floor(5 * (2000.0 / t));  // 同じ盤面を探索する回数
  int d = 10;                           // 探索する深さ

  // 最終的な答え
  string ans;         // 最終的な移動経路
  int ans_score = 0;  // 最終スコア

  // 盤面を確定させながら, いいスコアを探す
  for (size_t i = 0; i < d; i++) {
    // 初期化
    auto [x_ini, y_ini] = get_blank_position(bits_now);  // 空きマスの初期位置
    int max_score = 0;                                   // 最大スコア
    string max_moving = "";     // 最大スコア時の経路
    vector<bs> bits_next;       // 次に探索する盤面
    vector<char> ng_grid_next;  // 次に探索する際の確定済み盤面

    // 同じ盤面をなるべくたくさん探索する
    for (int j = 0; j < limit; j++) {
      // 盤面初期化 (毎回同じ盤面からスタート)
      vector<bs> bits = bits_now;
      vector<char> ng_grid = ng_grid_now;

      // 探索
      auto [score, moving, ng_grid_res] =
          random_seach(bits, x_ini, y_ini, ng_grid);

      // 最大値更新
      if (chmax(max_score, score)) {
        max_moving = moving;  // 移動経路更新
        bits_next = bits;  // 最もいい盤面を, 次のスタート盤面にする
        ng_grid_next = ng_grid_res;
        ans_score = max(ans_score, max_score);
      }
    }

    // 次に探索する盤面をセット
    if (!bits_next.empty()) {
      if (ans.size() + max_moving.size() <= t) {
        ans = ans + max_moving;
        bits_now = bits_next;
        ng_grid_now = ng_grid_next;
      } else {
        break;
      }
    }
  }

  cout << ans << endl;
}

最終的なコード

以下となりました。最終提出はデバッグ用のコメントなど入っているので、より一層読みづらいです m(_ _)m
ちょっとだけ読みやすくした ver.もあるので、そちらを見てもらった方がいいかもです。

日記

最後に最終コードに至るまでツイート＋日記をつらつら書きます。 本当にただの日記なので、ゆるーく読んで頂けると幸いです。

2022/05/28

とりあえず問題文を読む。 うっ、なんか難しそうだけど、1 週間あれば何かしら書けそうかも。 そして、ゆっくりスコアの計算式を眺める。。。うん？これは何もしなくてもスコアもらえるじゃん！

というわけで提出！！

記念すべき初得点。なんにも実装してないけど、得点取れてとってもうれしかった。

2022/05/30

アルゴの精進も続けたい気持ちもあったので、こんな感じで取り組むことに決定

そして、全然方針が決まらず書き始められなかったので、思いつく限り簡単な方針で書くことに決定。
真っ先に思い浮かんだのが、ランダムに空きマスを動かして、一番大きい木の盤面で止める方針。
結果的にこれがほぼそのまま今回の最終方針になった。

2022/05/31

はじめて自分の書いたプログラムでビジュアライザを動かす。めっちゃうれしい！

この日はもう 1 回提出してさらにスコアアップ！
この時点では「時間いっぱいランダムに盤面を探索して, 一番大きな木を出力」というシンプルなアルゴリズムだった。

2022/06/01

コードの量が増えてきて辛くなってきている。

流石にこれ以上は無理と判断して、mainのランダムに探索するところを関数に切り出す作業を実施。 main 関数の見通しがかなりよくなったので、実装＆実験しやすくなった。

2022/06/02

バグ取り、けっこう大変。

ここで「あっ！木の閉路判定してないじゃん！！」に気づく。スコアがめっちゃ伸びるのでは？とワクワクし始める（なお、たいして伸びなかった、、）

10M 突破して、かなりうれしくなってる。
ここで、ランダム探索に加えて、確定した盤面を徐々に大きくする実装を取り入れる。

2022/06/03

だんだんと AHC 沼にハマる様子が分かる

ここで、最初に選んだ盤面が、大きくなりにくい盤面だとスコアが伸びないことに気がつく。 今までの処理をまるまる 2 回分やって、良い方を取る実装を取り入れて、スコアちょい伸び。

2022/06/04

探索回数を少しいじって微増。ここで今回の AHC は切り上げ。

2022/06/05

システムテストなるものがあることを知って、それが最終提出で走ることに焦る。 問題文をちゃんと読むの大切です、、（システムテストは 3 つほど TLE したけど、無事でした）

最後に

かなり長くなってしまいましたが、最後まで読んで頂いてありがとうございます。 参加迷っている方がいれば、次回はぜひAHCをワイワイ一緒に楽しめるとうれしいです！