AHC002 解説 - eijirouの競プロ参加記

f:id:eijirou_kyopro:20220211183916p:plain — Seed=0 の出力

コンテスト中は2,786,732点で380位、コンテスト後は6,019,141点で6位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

紹介する解法は一例です。もっといい解法があると思います。

問題概要

$50\times 50$ マスのグリッド上にタイルが敷き詰められています。各タイルは $1\times 1,1\times 2,2\times 1$ のいずれかの大きさです。各マスには得点が設定されており、そのマスを通ったときに得点を得ることができます。 $(s_i,s_j)$ からスタートするような経路で、各タイルをたかだか一度しか通らないもののうち、得点ができるだけ高いものを求めてください。

方針

探索順に優先度をつけたDFS（深さ優先探索）を0.25秒間行い、その後、2点選んでその間を変更する形で焼きなまし法を行いました。

なお、この解法は1位のats5515さんのツイートを参考にしています。 https://twitter.com/ats5515/status/1386324082581405705

DFSについて

貪欲法の欠点

貪欲解法の1つとして、移動可能なマスのうち、最も得点が高いものを選ぶというものが考えられます。

実装例（クリックで展開）

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

struct Solver {
    vector<int> dx = {-1,1,0,0};
    vector<int> dy = {0,0,-1,1};
    int n = 50;
    int si;
    int sj;
    vector<vector<int>> t = vector<vector<int>>(50, vector<int>(50));
    vector<vector<int>> p = vector<vector<int>>(50, vector<int>(50));
    int t_max = 0;
    vector<bool> used;
    int score = 0;
    vector<int> x;
    vector<int> y;

    void input() {
        cin >> si >> sj;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> t[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> p[i][j];
            }
        }
    }

    void init() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                t_max = max(t_max, t[i][j]+1);
            }
        }
        used = vector<bool>(t_max, false);
    }

    void push(int i, int j) {
        assert(!used[t[i][j]]);
        used[t[i][j]] = true;
        x.push_back(i);
        y.push_back(j);
        score += p[i][j];
    }

    void greedy() {
        push(si, sj);
        while (true) {
            int best_d = -1;
            int best_p = -1;
            for (int d = 0; d < 4; d++) {
                int xd = x.back() + dx[d];
                int yd = y.back() + dy[d];
                if (0 <= xd && xd < n && 0 <= yd && yd < n) {
                    if (!used[t[xd][yd]] && best_p < p[xd][yd]) {
                        best_d = d;
                        best_p = p[xd][yd];
                    }
                }
            }
            if (best_d == -1) {
                break;
            }
            push(x.back()+dx[best_d], y.back()+dy[best_d]);
        }
    }

    void print() {
        for (int i = 0; i < x.size()-1; i++) {
            for (int d = 0; d < 4; d++) {
                if (x[i]+dx[d] == x[i+1] && y[i]+dy[d] == y[i+1]) {
                    cout << string(abs(x[i+1]-x[i])+abs(y[i+1]-y[i]), "UDLR"[d]);
                    break;
                }
            }
        }
        cout << endl;
    }
};

int main() {
    Solver solver;
    solver.input();
    solver.init();
    solver.greedy();
    solver.print();
}