はじめに

に引き続き、AtCoder Heuristic Contest 037 に参加してきました。4時間のヒューリスティックコンテストです。

Rated 参加 2回目と言うことで、AHC036 の反省を少し生かして取り組みました。参加して楽しかったから、ほかに興味を持つ方が現れると良いな、という宣伝記事です。

タイトルの上位 2割は、AC した 922名中 179番目という意味でです。全体では上位 1割です。

概要

AHC037 を Rust で参加した記録です
当日の 4時間の流れ (179位: 上位 2割)
感想・反省点
- Good: Visualizer でロジックの不備を見つけられた
- Bad: 今回も貪欲法 1発どりで終わった
- Bad: 3時間過ぎてようやく何をする問題か分かった
延長戦 (84位: 上位 1割)

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

本番中にやったこと

19:00～19:10 問題を読む

問題を読みます。途中を引用します。

あなたは以下の操作を繰り返し行うことで複数の炭酸飲料を作ることができます。

すでに持っている炭酸飲料 $(x,y)∈S$ を一つ選ぶ

$x′ ≥x$ かつ $y′ ≥y$ を満たす整数 $x′,y′$ を選ぶ

$(x,y)$ を二つの容器に分ける。片方はそのまま取っておき、もう一方にシロップと炭酸を加えることで炭酸飲料 $(x′,y′)$ を作る。$S$ に $(x′,y′)$ が追加される。

このとき $(x,y)$ が $S$ から削除されないことに注意してください

コストが $(x′−x)+(y′−y)$ かかる

この合計コストを小さくする問題です。

$(x′−x)+(y′−y)$ と見ると、いかにもマンハッタン距離です。頂点をどう追加すれば良いかという問題になります。

19:10～19:40 最初の提出

頂点を追加することを最初から考えるのは難しいです。まず、「頂点を追加せずに」スコアを伸ばす方法を考えます。

サンプル入力として次を考えました。公式入力例に (1, 1) を足したものです。

すべての炭酸水を (0, 0) から作ると、次のようになります:

(2, 5), (3, 2) の炭酸水は、(1, 1) の炭酸水から作った方が効率的です。このように書き換えます。

頂点を左から順に並べておき、以前に現れた左下の頂点のうちマンハッタン距離が最小のものを探します。全て調べても速度的には $O(N^2)$ で怖くありません。

fn make_result(ab: &BTreeSet<(usize, usize)>) -> Vec<(usize, usize, usize, usize)> {
    let mut result = vec![];

    let mut set = BTreeSet::new();
    set.insert((0, 0));
    for &(a, b) in ab {
        let mut a1 = a;
        let mut b1 = b;
        let mut score1 = usize::MAX;
        for &(a0, b0) in &set {
            if a0 > a || b0 > b {
                continue;
            }
            let score0 = (a - a0) + (b - b0);
            if score0 > score1 {
                continue;
            }
            (a1, b1, score1) = (a0, b0, score0);
        }
        result.push((a1, b1, a, b));
        set.insert((a, b));
    }

    result
}

ここまでの結果:

提出日時	得点	コード長	実行時間
2024-09-15 19:35:42	3,430,697,513	1043 Byte	5 ms

提出したところ、同じスコアの人がたくさんいました。

この make_result 関数は炭酸水追加に強いです。最終提出までそのまま使うことができました。

19:40～21:25 点を挿入する

サンプル入出力の通り、点を挿入してみます。枝分かれしているところで、"└" 字のように境界ボックスの左下に点を追加します。

点 (2, 2) を追加するとコストを 2 減らせます。

変更前: 8
- (1, 1) - (2, 5): 5
- (1, 1) - (3, 2): 3
変更後: 6
- (1, 1) - (2, 2): 2
- (2, 2) - (2, 5): 3
- (2, 2) - (3, 2): 1

マンハッタン距離としては、(1, 1) - (2, 2) の移動を 2回から 1回に減らすことになります。デメリットはありません。

このように、1000個の点に対して、右上に枝分かれがあるときに点を挿入するとどれだけコストを減らせるかを調べ、コストを大きく減らせる順に挿入していけばいい感じになるはず。

提出日時	得点	コード長	実行時間
2024-09-15 19:35:42	3,430,697,513	1043 Byte	5 ms
2024-09-15 21:21:53	3,439,322,760	3118 Byte	26 ms

う、全然良い感じになりません……。

19:25～21:50 バグ取り

Visualizer の結果を見ると、左下だけは縦横の線が見えているものの、ほかの挿入点は全然仕事していないようです。それにこんなに斜めに並ぶはずがない。バグ取り開始。

はい、思いっきり間違えていました。修正。

提出日時	得点	コード長	実行時間
2024-09-15 21:21:53	3,439,322,760	3118 Byte	26 ms
2024-09-15 21:49:10	4,258,571,183	3226 Byte	18 ms

ようやくちゃんと動きました。残り 70分。

追加点は500個弱でした。最大4000個追加できるはずなのに。もしかして5000個使い切る問題ではない？とここで気づきました。

21:50～22:00 挿入点の候補を追加

先の方針には弱点があります。1回処理をすると、左下の角が移動元と同じになります。2回以上処理できません。サンプル入力に対しては無力です。

そこで、「下辺に、左下の次の x」「左辺に、左下の次の y」の 2通りを追加で調べることにしました。あまり良い点ではなさそうですけれど、行わないよりマシです。

少し良くなりました。提出します。

提出日時	得点	コード長	実行時間
2024-09-15 21:49:10	4,258,571,183	3226 Byte	18 ms
2024-09-15 22:00:40	4,526,879,928	4386 Byte	93 ms

21:00～22:00 下辺と左辺を特別扱い

あと1時間以内でコストを下げる実装を書けないか、考えます。

まず、枝をつなぎ変えることを考えました。ヒューリスティックコンテストで上位を取ろうとすると、枝のつなぎ変えを繰り返して徐々にコストを下げる方針になりそうです。でも残り 1時間で実装できる気がしません。

それに、繋ぎ変えると不要な頂点が現れます。コストを減らすために不要な頂点を除くのも大変そうです。

もう 1つ、やはり Visualizer で目立つ、平行な線が現れるところをなんとかしたいです。左辺・下辺でとくに目立ちます。

もう一度制約を見ます。

$A_i =0$ を満たす $i$ が存在する

$B_i =0$ を満たす $i$ が存在する

この 2 つを (0, y), (x, 0) とすると、
下辺に (0, 0) - (x, 0) の、左辺に (0, 0) - (0, y) の線が引かれます。点同士の最短経路に加えて、この 2本の線からの最短経路も加えて良さそうです。

1時間くらいかけて実装し、締め切り 4分前にようやくそれっぽく動きました。提出は 5分に 1回だからこれが最後の提出です。失敗すると大変なことになります。祈りながら提出しました。

提出日時	得点	コード長	実行時間
2024-09-15 22:00:40	4,526,879,928	4386 Byte	93 ms
2024-09-15 22:48:35	4,526,879,928	4386 Byte	94 ms
2024-09-15 22:57:08	4,708,583,272	5290 Byte	91 ms

これで終了です。お疲れさまでした。

提出コード。とても汚いです。

感想・反省点

Visualizer の結果を見て、コードが思った通りに動いているかどうかを確認しながら進められたことが良かったです。ここは前回の反省を生かせました。

少しコードを書いて、テキスト出力できるか確認して、を繰り返しました。

PS> cat in.txt | cargo run --bin ahc037-a >out.txt

最初の区切りの良い実装までで 3時間近くかかり、残り時間ではあまり試行錯誤できませんでした。4時間の短期 AHC、アルゴリズムコンテストに比べると長いはずなのに、時間がどんどん溶けていきます。もっといろいろできると思ったのに、と。

山登り法とかビームサーチとか、試行回数を増やすためには 1回あたりの評価が短くないとできないはずです。今回も全然分かりませんでした。

延長戦 1週間でやったこと

提出最後に行った下辺と左辺の扱いが効果的でした。このように全体に対して縦横の線を延ばしていたらどうなっていたかを、本番後の延長戦で試してみました。

下辺を最後まで使う

まず、下辺を右端まで扱えるようにします。凸包のように押し上げます。

□□■□□□□□□
□□□□□□□□■
□□□□□□□□□
■□□□□■□□□

　↓

□□■□□□□□□
□□□□□●──■
□□□□□│
■────■

の感じで。線の右下には頂点が現れないようにします。下辺のこれより良い選択肢はあまりないはずです。

辺との最近点を考える

次に、左の点から順に、次のように処理します。

左に縦の線分があれば分割して伸ばすことを候補とします
または左下の点に対して、 "┘" のように右下が凸になるような延ばし方を候補にします
- 右側に縦線があると、次の右の点で使えるかもしれないため

この候補の中でもっともコストが小さなものを採用します。

■□□□□　　□□■□□
│□□□■　　□□□□■
│□■□□　　■□□□□
│□□□□　　│□□□□
■□□□□　　■□□□□

　↓

■□□□□　　□□■□□
│□□□■　　□□┃□■
●━■□□　　■━●□□
│□□□□　　│□□□□
■□□□□　　■□□□□

　↓

■□□□□　　□□■□□
│□□□■　　□□●━■
●─■━●　　■─●□□
│□□□□　　│□□□□
■□□□□　　■□□□□

新しい点●を追加します。太線が編集中の経路になります。

アニメーションです:

下辺 (0, 0) - (5, 0) の間に (3, 0) を挿入しているときに、アニメーションでは (0, 0) - (3, 0) を重ねています。実際の出力では (0, 0) - (5, 0) が (0, 0) - (3, 0) と (3, 0) - (5, 0) の 2つに分かれます。

左から右に延ばす方針としてはいい感じそうです。

下からの経路がより良いかを調べる

下から上に延ばす方法も考えられます。もしかすると、より短くなるかもしれません。続けて下から順に調べます。

下に横の線分があれば分割して伸ばすことを候補とします
または左下の点に対して、 "┌" のように左上が凸になるような延ばし方を候補にします

先ほど調べていた右に伸ばしたときのコストと比較し、もしこちらの方が良ければ切り替えます。

■
│
│□□■
│□□│
│□□│□■
│□□│□│
│□□│□│
■──●─●

　↓

■
│
●━━■
│□□:
│□□:□■
│□□:□│
│□□:□│
■──●─●

　↓

■
│
●━━■
│□□:
│□□●━■
│□□┃□:
│□□┃□:
■──●.●

点線はもしかすると右側で使うかもしれません。この時点では他候補として残しておきます。

切り替えると、前に追加した無駄な点が残ってしまうことがあります。でも消して良い点かはすぐには分かりません。消しすぎると余計にコストが増えてしまいます。右下の点は消して良いですが、その左隣を消すのは良くないです。

使われない末端の追加点を消す

枝の末端が無駄な点の場合は、消すデメリットがありません。ばっさり削除します。

●━━■
│□□:
│□□●━■
│□□┃□:
│□□┃□:
■──●.●

　↓

●━━■
│□□:
│□□●━■
│□□┃
│□□┃
■──●

2通り調べる

「左から→下から」に加えて、「下から→左から」についても調べ、よりコストの小さい方を採用することとしました。

    let soda0 = make_soda(&ab);
    let (result0, score0) = make_result(&ab, &soda0);

    let ba = &ab.iter().map(|&(x, y)| (y, x)).collect();
    let soda1 = make_soda(&ba);
    let (result1, score1) = make_result(&ba, &soda1);

    if score0 < score1 {
        println!("{}", result0.len());
        for &(x, y, x0, y0) in &result0 {
            println!("{x} {y} {x0} {y0}");
        }
    } else {
        println!("{}", result1.len());
        for &(x, y, x0, y0) in &result1 {
            println!("{y} {x} {y0} {x0}");
        }
    }

前回 AHC036 に挑戦したときには、結果を調べながらその場で出力していました。2通り調べられない実装になっていました。少し経験値が増えました。

並走対策

![vis_a14_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/118172/f65297a8-e1c1-

Visualizer で見ると、このような並走がたくさん現れていました。隣の線までたどり着いたら止めるのではなく、もっと左まで伸ばして交点を調べるのが良さそうです。

下から延ばした時よりも左に延ばした方が交点が作れて良いなら、下からの長さと同じ分だけは左から延ばして損はしないはずです。

■
│
●──■
│□□:
│□□:□■
│□□:□│
│□□:□│
│□□:□│
■──●─●

　↓

■
│
●──■
│□□:
●━━●━■
│□□:□:
│□□:□:
│□□:□:
■..●.●

問題点として、さらに使われない点が残るようになりました。一応末端から消していくはずですけれど。

効果のない途中の追加点を消す

最後に、追加点が右上に 1回しか使われていないものを削除しました。2回以上同じコストを払うことを防ぐための追加点ですから、1回だけなら意味がありません。もしかするとつなぎ方が変わって少しコストが伸びるかもしれません。

ここまでで延長戦終了です。

延長戦終了

延長戦の最終結果です。

提出日時	得点	コード長	実行時間	補足
2024-09-15 22:57:08	4,708,583,272	5290 Byte	91 ms	本番
2024-09-17 23:10:53	4,846,971,739	3421 Byte	17 ms	線との最近点
2024-09-17 23:50:40	5,015,426,957	4085 Byte	17 ms	下辺を押し上げ
2024-09-18 21:22:00	5,034,014,569	4482 Byte	31 ms	2通り調べる
2024-09-20 21:48:55	5,043,642,668	4938 Byte	43 ms	末端の追加点を消す
2024-09-21 16:14:33	5,153,193,846	6798 Byte	45 ms	並走対策、追加点を消す

本番よりだいぶ良くなりました。これ以上は大変そうです。ここまででひと区切りにします。

延長戦の順位はこうなりました。だいたい上位 1割です。

最終提出コード。とても汚いです。

最後に

延長戦を含め、パズルゲームをゆっくり考えて解く感じで進めていました。実装速度重視なアルゴリズム系コンテストとはまた違う感じで、楽しいです。

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