A - Excavation

AHC018 お疲れさまでした！
春休みに入ったのでコンテスト期間中 (ほぼ) ずっとやってました。。

ほぼ自分のためのメモ書きなので読みづらい部分もあるかと思いますが、せっかくなので記録として残したいと思います。

注記

この記事および私の実装では、x 座標を上下、y 座標を左右として書いています。
つまり、問題文・ビジュアライザと x,y が逆です。
が、軸の向き (正負) は同じで、下方向・右方向がプラスです。

問題概要

200x200 の土地があって、家と水源がある。
岩盤を掘って、なるべく少ない体力で全部の家に水が流れるようにしてね。

やったこと

とりあえずリンク集です。

• 提出一覧
• GitHub ※コンテストが終わってから GitHub に上げました。

要約すると

• 26 回目の提出 が最後
• AtCoder 上の pretest コスト合計: 5,681,762
• グリッドサンプリングをして、ざっくりとコストを求める
• ダイクストラで一番コストが小さくなりそうな経路を探す
• $C$ の値に応じて、パワーを変える
• サンプリングした点と点の間をまっすぐ引く
• 要約おわり。メモを飛ばして「結果と感想」までスキップする

とりあえずやってみる

とりあえずフルパワー ($P=5000$) で、家から一番近い水源に伸ばしてみます。
経路もとりあえず「まず上下に移動して x 座標を同じにして、左右に移動して y 座標も同じにする」といった感じでとにかくシンプルな実装。

提出 #1 / ― / 122,175,793 / 2,614,585.58
「提出 / Diff / AtCoder 上でのコスト総和 / ローカル(Seed0 ～ 100)のコスト平均」という形式で書きます。

近い順にしてみる

水源に近い順につなげていくようにしてみます。
また、水源から遠いところは、ほかの家からもつなげられるようにします。

これで多少はコストが下がるはずです。

提出 #2 / Diff / 104,020,592 / 2,162,998.51

heap を使ってみる

先ほどのコードでは、「この家から一番近い水源から引っ張る」「マンハッタン距離で小さい順につなげる」という実装をしました。
これでは、すでに水が引かれた家を水源としてみなすことをしていないので、改善します。

ここで、 BinaryHeap (C++ でいう priority_queue) を使ってみます。
これにより、新しく水源が追加された (= 家に水が引かれた) ときにも、距離が小さい順に処理ができます。

提出 #3 / Diff / 102,759,315 / 2,112,404.47

まあほんとに微減っていう感じ。

パワーを見直す

さすがに全部フルパワーは効率悪いので、パワーを最適に使うようにしたいです。
そこで、まずは入力の生成方法を見てみます。

二次元の Perlin noise

？？？ 初耳、とりあえずスキップ。。

ロジスティック関数で変換する

知ってる！0 から 1 の間に収まるように変換するやつ。

$p = \mathrm{randf}(2.0, 4.0)$ を選ぶ。 $S_{i,j} = \mathrm{pow}(S_{i,j}, p)$ と更新する。

ん、これ、0 ～ 1 の累乗だから割と小さくなりそう

10 以上 5000 以下の範囲に線形スケーリング

ってことは、5000 が出てくる確率は割と低そう。
逆に、小さい数字がよく出てきそう。

ということで、調べてみます。
seed 0 から 100 までの岩盤の耐久度について、統計を取ってみました。

import os

res = []
for i in range(0, 101):
  with open(f".{os.sep}tools{os.sep}in{os.sep}{i}.txt") as f:
    lines = f.readlines()
    cnt = 0
    for line in lines:
      cnt += 1
      if 2 <= cnt and cnt <= 201:
        res.append(line.split(" "))

print(len(res))
with open("res.txt", "w") as f:
  f.write("".join(["\t".join(x) for x in res]))

15MB になっちゃった...(果たして $4 \times 10^6$ 個ものデータを使う必要はあったのか...？)
ここで、 Excel に貼り付けて、統計してみます。

https://github.com/a01sa01to/ahc018/blob/main/Stats.xlsx
ここからダウンロードできます (作成者情報が載ったまま Push してしまったわけですが、どうせ公開情報なのでお気になさらず...)。

中央値は 234 、平均値は 776.58 になりました。
ということで、試しにパワーを 234 に設定してみます。

提出 #4 / Diff / 14,681,473 / 323,684.93

およそ 8 分の 1 になりました。いい感じ。

無駄を省く

すでに水路が引かれたのに、目標地点の座標と同じになるまで伸ばしているケースがありました。
この無駄を省きます。

提出 #5 / Diff / 14,638,120 / 323,134.77

割とこれで改善するケースが少ないので、あまり変わりません。

頑丈さの離散化？

やったこととしてメモ。
提出はしてませんが、とりあえずパワーを 234 で固定してみると、画像をシャープ化 (?) しているような感じにできるように見えました。
つまり、岩盤を「パワー 234 で壊れるまで掘る回数」でグループ分けをします。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int a, b, c, d;
  scanf("%d %d %d %d", &a, &b, &c, &d);
  printf("%d %d %d %d\n", a, b, c, d);
  rep(i, a) rep(j, a) {
    int x;
    scanf("%d", &x);
    printf("%d%c", 10 + (x / 234) * 234, " \n"[j == a - 1]);
  }
  rep(i, b) {
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%d %d\n", x, y);
  }
  rep(i, c) {
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%d %d\n", x, y);
  }
  return 0;
}

Seed0 で見てみます。

なんか見やすい。山の等高線のような感じに見えます。

パワーの再調整

統計を見てみると、割と小さい数字が多く、全体の 3 割強が 64 以下だとわかったので、パワーを 234 から 64 に設定してみます。
$C$ には最大で 128 が入ってくるので、 $\max(C, 64)$ にしてみました。

提出 #6 / Diff / 14,299,456 / 530,540.18

まあまあ改善しました。

最適解を求める

とりあえず、何か見えないかと思って、頑丈さも含めた入力から最適解を求めてみます。
コストをその岩盤の頑丈さとして、各家からダイクストラを回して、(頂点数が少ないので実装が楽な) 順列全探索します。
パワーは、その岩盤の頑丈さに設定します。
まあ水路の途中から伸ばすパターンは考えてないので 偽 最適解なんですが。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)

struct P {
  int x, y;
  P(): x(-1), y(-1) {}
  P(int x, int y): x(x), y(y) {}
  bool operator<(const P& p) const {
    return tie(x, y) < tie(p.x, p.y);
  }
};

const vector<int> dx = { 1, 0, -1, 0 };
const vector<int> dy = { 0, 1, 0, -1 };

int main() {
  // Input
  int n, w, k, c;
  cin >> n >> w >> k >> c;
  constexpr int Power = 64;
  vector Grid(n, vector<int>(n));
  rep(i, n) rep(j, n) {
    cin >> Grid[i][j];
  }
  vector<P> src(w + k);
  rep(i, w + k) cin >> src[i].x >> src[i].y;

  // Dijkstra
  vector dist(w + k, vector(n, vector<pair<int, P>>(n, { 1e9, { -1, -1 } })));
  rep(i, w + k) {
    P start = src[i];
    dist[i][start.x][start.y] = { 0, { -1, -1 } };
    priority_queue<pair<int, P>, vector<pair<int, P>>, greater<pair<int, P>>> que;
    que.push({ 0, start });
    while (!que.empty()) {
      auto [d, p] = que.top();
      que.pop();
      if (dist[i][p.x][p.y].first < d) continue;
      rep(dir, 4) {
        int nx = p.x + dx[dir];
        int ny = p.y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        int nd = d + Grid[nx][ny];
        if (dist[i][nx][ny].first > nd) {
          dist[i][nx][ny] = { nd, p };
          que.push({ nd, { nx, ny } });
        }
      }
    }
  }

  // Permutation Exhaustive Search
  vector<P> ans;
  vector<int> p(k);
  iota(p.begin(), p.end(), 0);
  do {
    vector<P> anstmp;
    rep(_i, k) {
      int i = p[_i];
      pair<int, int> best = { 1e9, -1 };
      rep(j, w + _i) {
        int x = (j < w ? j : p[j - w] + w);
        if (best.first > dist[i + w][src[x].x][src[x].y].first) {
          best = { dist[i + w][src[x].x][src[x].y].first, j };
        }
      }
      P pt = src[best.second < w ? best.second : p[best.second - w] + w];
      while (pt.x != -1) {
        anstmp.push_back(pt);
        pt = dist[i + w][pt.x][pt.y].second;
      }
    }
    if (ans.size() < anstmp.size()) swap(ans, anstmp);
  } while (next_permutation(p.begin(), p.end()));

  // Print
  for (auto [x, y] : ans) {
    if (Grid[x][y] > 0) {
      cout << x << ' ' << y << ' ' << Grid[x][y] << endl;
      Grid[x][y] = 0;
    }
  }
  return 0;
}

多少無駄はあるものの、コストは 50 万強から 7 万弱になりました。
だいぶ減ってる。(それはそう)

やっぱり、頑丈さが低いところを通っているようです。
まあ問題はインタラクティブでどうやってこういった経路を求めるかなんですが。。

画像のモザイク化

地点の一部分を代表としてサンプリングすることで、少しでもいい経路が見通せるようになるかと思ったので見てみます。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int a, b, c, d;
  scanf("%d%d%d%d", &a, &b, &c, &d);
  printf("%d %d %d %d\n", a, b, c, d);
  constexpr int rad = 3;
  vector Grid(a, vector<int>(a));
  rep(i, a) rep(j, a) scanf("%d", &Grid[i][j]);
  for (int i = rad; i < a; i += 2 * rad + 1) {
    for (int j = rad; j < a; j += 2 * rad + 1) {
      for (int dx = -rad; dx <= rad; dx++) {
        for (int dy = -rad; dy <= rad; dy++) {
          int x = i + dx, y = j + dy;
          if (x < 0 || x >= a || y < 0 || y >= a) continue;
          Grid[i + dx][j + dy] = Grid[i][j];
        }
      }
    }
  }
  rep(i, a) rep(j, a) printf("%d%c", Grid[i][j], " \n"[j == a - 1]);
  rep(_, b) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d %d\n", x, y);
  }
  rep(_, c) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d %d\n", x, y);
  }
  return 0;
}

1x1, 3x3, ..., 15x15 の範囲でモザイク化してみました。順番に表示されます。
(よく見ると右端・下端はモザイクかかってませんが、観察なので気にしないことにします)

うーん、あまり考察は進まず。。。

硬いほうを避ける

上で考えたように、ダイクストラを使って最短経路を求めたいと思いました。
でも元のコストがわからないので、どうしようもない気がする？

そこで、いくつか間隔をあけて、パワー 128 で掘った回数を基準にコストを設定し、ダイクストラを回してみました。 (皆さんやっている「グリッドサンプリング」です)
DFS で上下左右を探索して、目標地点に近くなったら直接つなげます。

間隔は狭いと正確ですが、その分掘る回数が増え、コストが大きくなってしまうので、とりあえず間隔は 15 にしてみます。

提出 #7 / Diff / 9,198,259 / 217,913.38

およそ 3 分の 2 になりました。

探索方向の修正

上のビジュアライザの結果を見てみると、なんか無駄がある気がします。
最初の家から探索するとき、水源が左下にあるのに、右から探索してしまっているように見えます。

実際にコードを見てみると、やはり探索方向が間違っていました。
それを修正します。

ついでに、DFS の探索幅を 10 に狭めて、ダイクストラを回す際に斜めにも行けるようにしてみます。
(Diff では「幅を 8 に変更」と書いてありますが、コードを見る限り 10 が正しいです)

提出 #8 / Diff / 8,026,170 / 193,473.17

これだけで 1 割ほど改善しました。やっぱり探索方向が大事。

ここで 2 ページ目に載りました。やった～

また、いろいろやってみてスコアがよかったので、探索の間隔を 12 に広げました。

提出 #9 / Diff / 7,715,157 / 182434.93

遠いほうを避ける

DFS を回しているとき、たどりつけなかった場合、他の方向で行けるところまで (無制限に) 行ってしまっていました。
ある程度遠くまで行ってしまうと無駄打ちになってしまうと思ったので、確率的に遠いほうを避けるようにしてみます。

判定する式は以下のようにして、この式が満たされていれば諦めるようにしました。

ここで、$d_s$ はスタート地点から目標地点までのユークリッド距離、$d_n$ は現在地点からの距離です。
4 で割ったのは実験しててスコアが良さそうだったから。

右側の試し削りがなくなってますね。

提出 #10 / Diff / 8,005,622 / 175,871.55

ローカル平均では改善しているものの、 AtCoder 上では下がってしまいました。。
誤差だと信じて、このままにしてみます。

この後、始点から離れすぎたところも避けるようにしてみたものの、スコアが下がっちゃったので、仕方なく Revert 。。。

提出 #11 / Diff / 8,448,120 / 181017.90

動的に目標点を設定する

ここでは、右下の家まで、左下の家からつなごうとしています。
しかし、現在見ている場所 (ピンクの四角) からだと、青い四角の水源に向かったほうが近いのでは？

ということで、現在見ている場所から、すでに水が引かれた家 or 水源までの距離を計算して、その距離が最も近いところを目標点として探索するようにしてみます。

提出 #12 / Diff / 7,157,644 / 164,264.03

うん、いいかんじ。

水路の途中から引く

また Seed 29 を見てみます。

ここから左上の家に行こうとしてるんですが、ここを左に突き進んでいって、水路を途中からつなげたほうがよくない？
ということで、水路の途中から引けるように実装。

提出 #13 / Diff / 6,988,742 / 159,619.52

コメントをつける

後になって困らないよう、コメントをつけておきます。

ついでに遊び心も。

// ヤー！パワー！！
//
// 　　　　ノ从从从ヽ
// 　　　 /ミミ 彡彡∧
// 　　　｜／￣￣￣＼｜
// 　　　 Y　==　==　Y
// 　　　(|　ヽ〉ノ　|)
// 　　　 ( 　 |　　 )
// 　　　 ｜ ﾉヽノヽ｜
// 　　　／＼((￣)/／
// 　　／ ＼ ヽ二ノ＼
// 　／⌒＼ ＼　　 | ヽ
// `/　　　ヽ ＼＿ノ　|
// ｜　　　 |　　　_　|
// ｜　　　ノ　　 へヽ|
// ｜　　　)ノ　 / 三|
// ｜　　／￣￣￣　_ノ
// 人　　　　　　／
// 　＼＿＿＿＿／
//
const POWER: u32 = 128;

(http://heno2.com/2ch/v.php?16443 ここから引っ張ってきました。)

すでに掘ったところから探す

Seed 29 のまたこの盤面。

画像の中央付近にをよく見ると、掘られた部分が斜めに 2 つ並んでいるように見えます。
この並んでいるのは、別地点から探索を開始したものです。

つまり、すでに掘ったところから再帰すれば、新たに近いところを掘らなくて済むのでは？

提出 #14 / Diff / 6,981,472 / 159,702.50

「近いところ」はマンハッタン距離が 8 以下としましたが、それほど効果はなかったみたいです。

パワーの調整 v3

これまで、パワーを 128 で決め打っていましたが、128 の 1 回で壊れたら、割と 64 でも壊れるんじゃ...？
ということで条件付確率を求めてみたところ、77%強になったので、実装してみました。

提出 #15 / Diff / 6,223,395 / 144,755.85

かなり減りました。

また、同じパワーで何回も掘るのは非効率なので、硬そうな場所はパワーを強めて掘るようにしてみます。
けどちょっと増えたので Revert しました。。

提出 #16 / Diff / 6,307,071 / 146,583.28

さらに減るかなと思って、128 の 1 回で壊れたらパワーを 32 にしてみます。
ちなみに、条件付確率は 57%強。

提出 #17 / Diff / 6,054,465 / 141,432.35

割と改善しました。
ここまでくるとコストの減り具合が少なくなってくるのでうーん。。

でも暫定 30 位になりました。

すでに流れているなら無視

このように、膨らんでしまうケースがあったので、これをなくしたいと思いました。
目標地点に行く段階で、上下左右 1 マスずつ見て、すでに水が流れていたらその先は無視するように実装。

提出 #18 / Diff / 6,067,567 / 141,408.14

悪くなったので Revert します。
コードは 提出#17 とまったく同じです。

提出 #19 / Diff / 6,077,720 / ―
(ローカル平均コストについては、同じコードなので計測していません)

確率的遷移をやめる

19 番目の提出で、17 番目の提出をそのまま出しただけなのにスコアが下がってしまった。
これはまあ「時間いっぱいまで ○○ する」とかをせず、ただ確率的にやってるせいなので、やめてみることにします。
「ローカルでスコア上がってるのに提出したら下がった 」ということも少しでも避けたいので。

それでも、提出#10 で考えたように、遠いところは掘らないようにしたいです。
よって、スタート地点から目標地点までの距離 ×2 以上離れているところについては、掘らないようにします。

提出 #20 / Diff / 5,975,229 / 140,009.03

「遠い」判定を変える

「遠い」判定を 2 倍としていたのですが、 手動三分探索 で試してみたところ、2.15 倍 (の round) がスコアが良かったので、これを提出します。

提出 #21 / Diff / 5,983,733 / 139,788.15

ローカルでは良かったものの、提出するとスコアが下がってしまった。。Revert しておく。

斜め移動の倍率を変える

斜め移動はコストを高めに設定していました。というのも、縦横移動の探索幅よりも広くなってしまい、信頼ができないと考えたので。

そこで、斜め移動のコスト倍率を 3 から 4 に設定してみる。

提出 #22 / Diff / 6,023,092 / 139,093.15

うーん、これも微妙に悪くなった。Revert 。

とりあえず 提出#20 と同じコードで提出。

提出 #23 / Diff / 5,975,229 / 140,009.03

そしてお気持ち表明

パワーの再調整 v4

用事があったので、数日ぶりの提出。
120 位くらいまで下がってしまいました。かなしい。

同じ場所を何度も何度も掘ると、コスト $\Sigma(C+P)$ がどんどん高まってしまいます。
そこで、 $C$ が高い場合にはなるべく少ない回数で掘るようにします。

とりあえず $C$ の値を 0.25 ～ 1.25 のあたりの間に線形スケーリングして、さらに高火力が必要そうな場所についてはさらに倍率を上げてみます。
念のため min(5000) をします。

let power: u32 = ((POWER as f64 * src_num.min(target_num) as f64 * (c as f64 / 32.0 + 1.0) / 4.0).round() as u32).min(5000);

提出 #24 / Diff / 5,840,069 / 138,793.61

ここにも提出#17 のアイデアを取り入れ、始点と終点が両方ともパワー 128 で掘れている場合は、その間はパワー 32 で掘ってみます。

提出 #25 / Diff / 5,707,108 / 135,203.44

ここで 100 位に復帰します。(が、最終日ということもあってすぐに下がりそう)

パワーの再調整 v5

高火力で掘った後は、岩盤も脆くなっているはずです。
そこで、高火力で掘った後は、だんだんとパワーを下げていくようにします。
ここでも 手動三分探索 をしてみたところ結果が良かった、 $P_{next} = \mathrm{round}(P_{now} / 1.5)$ と更新してみます。

提出 #26 / Diff / 5,681,762 / 135,087.36

この後、いいアイデアを思いつくことなく終了。。
(というか、何も思いつかずに TopCoder と CodinGame に登録してしまい、そっちのけになってしまった)

暫定 124 位、推定 Perf 1,954 でした。

結果と感想

この後システムテストでなぜか 1 ケースだけ TLE してしまい、135 位に。。Perf は 1,918 でした。
test_2961 (0-indexed) で落ちていたので、 seeds.txt の 2962 行目(1-indexed) にあった Seed 1539066823124647274 を実際にローカルで試してみたところ、 Stack Overflow してしまいました。
実装の詰めが甘かった、これはかなしい

でも入青できてうれしいです！！
ほんとは Top 100 に入りたかったんですが、また今度頑張ります！

完全ルールベースでこのスコアまで来たのは少し意外でした。
いつもだったら焼きなましやらビームサーチやらいろいろやっていると思いますが、今回全く使いませんでした。
まあ上位勢はいろいろやっていたみたいですが。。
私もマップの推定などやってみたかったんですが、実装力不足でこちらも断念。。。

統計情報をせっかく集めたのでそれを埋め込んでみようと思ったんですが、ファイルが 20MB になり、コンパイラが死んでしまい、断念。。。

今回初めて Rust で書いてみたので戸惑いながらの実装でしたが、慣れると割と書きやすいですね。
よく安全と聞くので今後もマラソン形式では Rust で書いていきたいと思います。

後日追記

なんと、景品対象者内で 110 位であったようで、景品を獲得することになりました！ありがとうございます！
AtCoder では初の景品獲得なので、とてもうれしいです！