#929200 (C++17) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	👑 jupiro
提出日時	2023-11-17 14:52:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	64 ms / 3,000 ms
コード長	9,048 bytes
コンパイル時間	2,851 ms
コンパイル使用メモリ	233,976 KB
実行使用メモリ	6,548 KB
スコア	2,103,390,626
最終ジャッジ日時	2023-11-17 14:52:57
合計ジャッジ時間	11,375 ms
ジャッジサーバーID （参考情報）	judge14 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	47 ms 6,548 KB
testcase_01	AC	44 ms 6,548 KB
testcase_02	AC	48 ms 6,548 KB
testcase_03	AC	39 ms 6,548 KB
testcase_04	AC	48 ms 6,548 KB
testcase_05	AC	54 ms 6,548 KB
testcase_06	AC	49 ms 6,548 KB
testcase_07	AC	49 ms 6,548 KB
testcase_08	AC	51 ms 6,548 KB
testcase_09	AC	48 ms 6,548 KB
testcase_10	AC	50 ms 6,548 KB
testcase_11	AC	47 ms 6,548 KB
testcase_12	AC	50 ms 6,548 KB
testcase_13	AC	53 ms 6,548 KB
testcase_14	AC	51 ms 6,548 KB
testcase_15	AC	51 ms 6,548 KB
testcase_16	AC	58 ms 6,548 KB
testcase_17	AC	45 ms 6,548 KB
testcase_18	AC	45 ms 6,548 KB
testcase_19	AC	54 ms 6,548 KB
testcase_20	AC	48 ms 6,548 KB
testcase_21	AC	45 ms 6,548 KB
testcase_22	AC	45 ms 6,548 KB
testcase_23	AC	45 ms 6,548 KB
testcase_24	AC	47 ms 6,548 KB
testcase_25	AC	35 ms 6,548 KB
testcase_26	AC	40 ms 6,548 KB
testcase_27	AC	41 ms 6,548 KB
testcase_28	AC	47 ms 6,548 KB
testcase_29	AC	47 ms 6,548 KB
testcase_30	AC	53 ms 6,548 KB
testcase_31	AC	44 ms 6,548 KB
testcase_32	AC	39 ms 6,548 KB
testcase_33	AC	52 ms 6,548 KB
testcase_34	AC	51 ms 6,548 KB
testcase_35	AC	39 ms 6,548 KB
testcase_36	AC	50 ms 6,548 KB
testcase_37	AC	45 ms 6,548 KB
testcase_38	AC	40 ms 6,548 KB
testcase_39	AC	64 ms 6,548 KB
testcase_40	AC	45 ms 6,548 KB
testcase_41	AC	49 ms 6,548 KB
testcase_42	AC	42 ms 6,548 KB
testcase_43	AC	53 ms 6,548 KB
testcase_44	AC	46 ms 6,548 KB
testcase_45	AC	43 ms 6,548 KB
testcase_46	AC	40 ms 6,548 KB
testcase_47	AC	50 ms 6,548 KB
testcase_48	AC	46 ms 6,548 KB
testcase_49	AC	49 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

constexpr int inf = (int)1e9 + 7;
constexpr int N = 50, M = 20;
constexpr int dr[] = {1, 0, -1, 0};
constexpr int dc[] = {0, 1, 0, -1};
using Board = std::array<std::array<int, N>, N>;

struct Bomb
{
    int bomb_id;
    int C, L;
    std::vector<int> dr, dc;
    Bomb() {}
    void input()
    {
        std::cin >> this->C >> this->L;
        this->dr.resize(this->L), this->dc.resize(this->L);
        for (int i = 0; i < this->L; i++)
        {
            std::cin >> this->dr[i] >> this->dc[i];
        }
    }
};

void input(Board &board, std::array<Bomb, M> &Bombs)
{
    int _n, _m;
    std::cin >> _n >> _m;
    for (int i = 0; i < N; i++)
    {
        std::string s;
        std::cin >> s;
        for (int j = 0; j < N; j++)
        {
            if (s[j] == '.')
                board[i][j] = 0;
            if (s[j] == '@')
                board[i][j] = 1;
            if (s[j] == '#')
                board[i][j] = 2;
        }
    }
    for (int i = 0; i < M; i++)
    {
        Bombs[i].input();
        Bombs[i].bomb_id = i;
    }
}

bool is_board_valid(const int r, const int c)
{
    return 0 <= r and r < N and 0 <= c and c < N;
}

std::pair<int, int> calc_wall_and_store_count(const int r, const int c, const Board &board, const Bomb &bomb)
{
    int wall = 0, store = 0;
    for (int i = 0; i < bomb.L; i++)
    {
        const int nr = r + bomb.dr[i];
        const int nc = c + bomb.dc[i];
        if (is_board_valid(nr, nc))
        {
            if (board[nr][nc] == 1)
                store += 1;
            if (board[nr][nc] == 2)
                wall += 1;
        }
    }
    return std::pair<int, int>{store, wall};
}

void calc_dist(const int sr, const int sc, std::array<std::array<int, N>, N> &dist, std::array<std::array<std::pair<int, int>, N>, N> &back, const Board &board)
{
    for (int i = 0; i < N; i++)
    {
        std::fill(dist[i].begin(), dist[i].end(), inf);
        std::fill(back[i].begin(), back[i].end(), std::pair{-1, -1});
    }
    using T = std::tuple<int, int, int>;
    std::queue<T> q1, q2;
    dist[sr][sc] = 0;
    q1.emplace(0, sr, sc);
    while (not q1.empty() or not q2.empty())
    {
        int d = -1, r = -1, c = -1;
        if (not q1.empty() and not q2.empty())
        {
            if (std::get<0>(q1.front()) <= std::get<0>(q2.front()))
            {
                std::tie(d, r, c) = q1.front();
                q1.pop();
            }
            else
            {
                std::tie(d, r, c) = q2.front();
                q2.pop();
            }
        }
        else if (not q1.empty())
        {
            std::tie(d, r, c) = q1.front();
            q1.pop();
        }
        else if (not q2.empty())
        {
            std::tie(d, r, c) = q2.front();
            q2.pop();
        }
        else
        {
            assert(false);
        }
        if (d > dist[r][c])
            continue;
        for (int i = 0; i < 4; i++)
        {
            const int nr = r + dr[i];
            const int nc = c + dc[i];
            if (is_board_valid(nr, nc))
            {
                if (board[nr][nc] == 0 and dist[nr][nc] > dist[r][c] + 1)
                {
                    dist[nr][nc] = dist[r][c] + 1;
                    back[nr][nc] = {r, c};
                    q1.emplace(dist[nr][nc], nr, nc);
                }
                if (board[nr][nc] != 0 and dist[nr][nc] > dist[r][c] + 2)
                {
                    dist[nr][nc] = dist[r][c] + 2;
                    back[nr][nc] = {r, c};
                    q2.emplace(dist[nr][nc], nr, nc);
                }
            }
        }
    }
}

void calc_path(const int sr, const int sc, const int er, const int ec, std::vector<std::pair<int, int>> &res, const std::array<std::array<std::pair<int, int>, N>, N> &back)
{
    std::vector<int> path;
    int cr = er, cc = ec;
    while (cr != sr or cc != sc)
    {
        for (int i = 0; i < 4; i++)
        {
            const int pr = cr - dr[i];
            const int pc = cc - dc[i];
            if (is_board_valid(pr, pc) and back[cr][cc] == std::pair<int, int>{pr, pc})
            {
                path.emplace_back(i);
                cr = pr, cc = pc;
            }
        }
    }
    while (not path.empty())
    {
        res.emplace_back(1, path.back());
        path.pop_back();
    }
}

void solve(Board board, const std::array<Bomb, M> &bombs)
{
    std::array<std::array<int, N>, N> dist;
    std::array<std::array<std::pair<int, int>, N>, N> back;
    std::set<std::pair<int, int>> store_set, wall_set;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == 1)
                store_set.emplace(i, j);
            if (board[i][j] == 2)
                wall_set.emplace(i, j);
        }
    }
    int min_bomb_id = -1;
    {
        int max_l = -1;
        int min_c = inf;
        for (int i = 0; i < M; i++)
        {
            if (bombs[i].C < min_c or (bombs[i].C == min_c and max_l < bombs[i].L))
            {
                min_c = bombs[i].C;
                min_bomb_id = i;
                max_l = bombs[i].L;
            }
        }
    }
    std::vector<std::pair<int, int>> res;
    std::vector<std::pair<int, int>> gomi;
    int sr = 0, sc = 0;
    while (not store_set.empty())
    {
        calc_dist(sr, sc, dist, back, board);
        long long res_score = -(long long)inf * 1000;
        int r = -1, c = -1;
        int res_store_r = -1, res_store_c = -1;
        int bomb_id = -1;
        int d = inf;
        for (const auto &[to_r, to_c] : store_set)
        {
            if (dist[to_r][to_c] < d)
            {
                res_store_r = to_r;
                res_store_c = to_c;
                d = dist[to_r][to_c];
            }
        }
        calc_path(sr, sc, res_store_r, res_store_c, res, back);
        calc_dist(res_store_r, res_store_c, dist, back, board);
        auto f = [&](const int tr, const int tc) -> void
        {
            if (not is_board_valid(tr, tc))
                return;
            {
                auto i = min_bomb_id;
                auto [erase_store, erase_wall] = calc_wall_and_store_count(tr, tc, board, bombs[i]);
                const long long score = erase_wall + erase_store;
                if (erase_wall + erase_store > 0 and res_score < score and not(erase_wall < (int)wall_set.size() and erase_store == (int)store_set.size()))
                {
                    res_score = score;
                    bomb_id = i;
                    r = tr, c = tc;
                }
            }
        };
        gomi.clear();
        for (int tr = res_store_r - 10; tr <= res_store_r + 10; tr++)
        {
            for (int tc = res_store_c - 10; tc <= res_store_c + 10; tc++)
            {
                if (is_board_valid(tr, tc))
                    gomi.emplace_back(tr, tc);
            }
        }

        std::sort(gomi.begin(), gomi.end(), [&](auto i, auto j)
                  { return dist[i.first][i.second] > dist[j.first][j.second]; });

        while (not gomi.empty())
        {
            f(gomi.back().first, gomi.back().second);
            gomi.pop_back();
            if (res_score == bombs[min_bomb_id].L)
                gomi.clear();
        }

        if (bomb_id == -1)
        {
            for (int tr = 0; tr < N; tr++)
            {
                for (int tc = 0; tc < N; tc++)
                {
                    if (not is_board_valid(tr, tc))
                        continue;
                    f(tr, tc);
                }
            }
        }
        if (bomb_id == -1)
            break;
        assert(board[res_store_r][res_store_c] == 1);

        res.emplace_back(2, bomb_id + 1);

        calc_path(res_store_r, res_store_c, r, c, res, back);
        res.emplace_back(3, bomb_id + 1);
        sr = r, sc = c;
        assert(0 <= bomb_id and bomb_id < M);
        const auto &bomb = bombs[bomb_id];
        for (int i = 0; i < bomb.L; i++)
        {
            const int nr = r + bomb.dr[i];
            const int nc = c + bomb.dc[i];
            if (is_board_valid(nr, nc))
            {
                if (board[nr][nc] == 1)
                {
                    store_set.erase(store_set.find({nr, nc}));
                }
                if (board[nr][nc] == 2)
                {
                    wall_set.erase(wall_set.find({nr, nc}));
                }
                board[nr][nc] = 0;
            }
        }
    }
    const std::string DIR = "DRUL";
    std::cout << res.size() << "\n";
    int cost2 = 0;
    for (const auto &[t, val] : res)
    {
        if (t == 1)
        {
            std::cout << 1 << " " << DIR[val] << "\n";
        }
        else
        {
            std::cout << t << " " << val << "\n";
            if (t == 2)
            {
                cost2 += bombs[val - 1].C;
            }
        }
    }
    std::cerr << cost2 << "\n";
}

int main()
{
    Board board;
    std::array<Bomb, M> bombs;
    input(board, bombs);
    solve(board, bombs);
}

yukicoder

結果

テストケース

ソースコード