HACK TO THE FUTURE 2024 / 181位解法

はじめに

めちゃくちゃいい！というような順位ではなかったですが、こんなんなんぼあってもいいですからねというところがあるので書いておきます。何かの参考になれば幸いです。

各日に何を考えていたかなどはこちらの記事で公開しているので、気になる方はこちらも読んでいただけると嬉しいです。ちなみに公開を想定していないガチのメモなので、結構適当に思ったことを書き連ねていて読みにくいです。

問題

部屋のレイアウトと汚れ方が与えられるので、お掃除ロボットのルートを決めてね。

https://atcoder.jp/contests/ahc027

解法

初期解の生成をした後、そのルートを一部破壊して再構築する焼きなましです。

↓seed=0のビジュアライザの様子。Score=1599337

初期解生成フェーズ

初期解は盤面を4x4の16個に分割をします。その後、全体の中で最も汚れているエリアを探し、そのエリアを掃除する貪欲法を書きました。

エリアの掃除はDFSをして行けるところまで掃除してエリアが掃除し終わった場合はその時点で打ち切るというような、サンプルプログラムをちょっと強くしたような動きをしています。今思えば、この掃除順などを突き詰めていったほうが強くなりそうな気がします。

コード(エリアの掃除部分)

fn cleanup_area(i: usize, j: usize, n: usize, color: &Vec<Vec<usize>>, routes: &mut Vec<(usize, usize)>, walls: &Walls) -> (usize, usize) {

    let mut pos = (i, j); // 今の位置

    /* DFS */
    let mut visited = vec![vec![false; n]; n];
    visited[i][j] = true;

    let mut stk = Vec::new();
    for r in 0..4usize {
        let ni = i as isize+ DI[r];
        let nj = j as isize + DJ[r];
        if Walls::is_through(walls, i, j, n, r) && color[ni as usize][nj as usize] == color[i][j] {
            stk.push((ni, nj, r));
        }
    }

    // dirの向きに移動した結果{p_i, p_j}に到達した
    'dfs : while let Some((p_i, p_j, dir)) = stk.pop() {
        if p_i >= 0 {
            if !visited[p_i as usize][p_j as usize] { // 未訪問なら訪れる
                //println!("#{} : {} {} {}", color[i][j], p_i, p_j, dir);

                visited[p_i as usize][p_j as usize] = true;
                pos = (p_i as usize, p_j as usize);
                routes.push((p_i as usize, p_j as usize));

                // 帰りがけの処理を追加する
                // 帰りがけはbit反転
                stk.push((!(p_i + DI[(dir + 2) % 4]), p_j + DJ[(dir + 2) % 4], (dir + 2) % 4));

                // 行きがけの処理を追加する
                for r in 0..4 {
                    let ni = p_i + DI[r];
                    let nj = p_j + DJ[r];

                    if Walls::is_through(walls, p_i as usize, p_j as usize, n, r) && color[ni as usize][nj as usize] == color[i][j] {
                        stk.push((ni, nj, r));
                    }
                }

                // もしエリアをすべて探索しきっていた場合は打ち切って今の座標を帰す
                for idx in 0..n {
                    for jdx in 0..n {
                        if color[i][j] == color[idx][jdx] && !visited[idx][jdx] {
                            continue 'dfs;
                        }
                    }
                }
                return pos;
            }
        }else{
            // 帰りがけは絶対出力
            pos = (!p_i as usize, p_j as usize);
            routes.push((!p_i as usize, p_j as usize));
        }
    }
    pos
}

焼きなまし

初期解の通った順の中から1箇所を乱択し、そこから乱択で決めたr手先までのルートを破壊した後、その間のルートを再構築しました。

ルートの再構築では通る1地点をこれまた乱択できめて、破壊した頭からその点を通ってつなげる場所までの最短路、のような形で決めました。自分的には結構適当な近傍だなぁと思いながらやっていたのですが、これでまず山登りをかけて点数が高くなったので、検索していたたまたま見つけた記事で述べられている

山登りができるということは焼きなましもできるということなので焼く。

を信じて焼いてみたら点数が上がって、めちゃくちゃテンションが上ってました。

スコア計算では問題で配布されているビジュアライザ付属のスコア計算部分を拝借しました。RustでAHCをする特権ですね。ただ、通るルートの全長をLとすると一度スコアを計算するのに$O(L)$かかってしまい効率が悪く、実際初期解のルートが短くなるseed=0では焼きなましが10万回ほど回るのに対し、ある程度長いものだと3,4万回程度しか回っておらず、改善点になっていました。最後の3日は差分計算を眠い頭で書いてたんですが、無限にバグらせ結局かけず...という感じでした。

コード(焼きなまし部分)

  let start_temp = 75isize;
    let end_temp = 15isize;
    let mut new_route;
    'annealing: while get_time() < TL {
        // memo: idxとidx + rangeは、"接続先"であって、ここは変えない
        let idx = rng.gen_range(1..tracking_route.len());
        let range = rng.gen_range(5..100); // 現状の何手先まで変えるか 値は適当. 最後にidx+rangeに接続できないと行けない

        /* その区間を変更していいか判定 */
        let mut passed_in_range = vec![vec![0usize; n]; n];
        if idx + range >= tracking_route.len()-1 { // 最後が変わると困るので、-1してる
            continue 'annealing;
        }
        for i in idx..idx+range {
            passed_in_range[tracking_route[i].0][tracking_route[i].1] += 1;
            if passing_times[tracking_route[i].0][tracking_route[i].1] == passed_in_range[tracking_route[i].0][tracking_route[i].1] {
                // ここが変わるとinvalidな解になるので、やらない
                continue 'annealing;
            }
        }

        let mut pos = tracking_route[idx + range];
        new_route = tracking_route.clone();

        let mut update = vec![];
        let target = vec![(rng.gen_range(0..n), rng.gen_range(0..n)), tracking_route[idx]];

        for i in 0..2 {
            pos = move_to_any_point(pos, n, &d, &mut update, &dist_from_point[target[i].0 * n + target[i].1], &walls);
        }

        update.reverse();
        new_route.splice(idx+1..idx+range, update.clone());
        let new_score = evaluate(n, &d, &new_route);

        let temp = start_temp as f64 + (end_temp - start_temp) as f64 * get_time() / TL;
        let prob = ((prev_score - new_score) as f64 / temp).exp();

        if prob > (rng.gen_range(0..INF) % INF) as f64 / INF as f64 {
            // 改善しているのなら採用
            prev_score = new_score;

            for p in update {
                passing_times[p.0][p.1] += 1;
            }
            for i in idx+1..idx+range{
                passing_times[tracking_route[i].0][tracking_route[i].1] -= 1;
            }

            swap(&mut tracking_route, &mut new_route);
        }
    }

感想など

コンテスト全体のムーブを見直してみると、差分計算がうまく実装できない時点で割り切って初期解をより良くする方針に動いたほうが良さそうだったような気がします。実際、(今回の自分の焼きなまし解よりも良い点が取れるような)貪欲がかけるという話も見かけたし、そもそも焼きなましは初期解が弱ければ限界があるので...

とはいっても、コンテスト本番期間中に焼きなましまで辿り着けたのは今回が初めてで、しかもそれでちょっといい順位まで辿り着けたので嬉しいです。