#770796 (C++17) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	shamio
提出日時	2022-06-12 18:10:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	163 ms / 2,000 ms
コード長	6,041 bytes
コンパイル時間	2,314 ms
実行使用メモリ	22,692 KB
スコア	0
平均クエリ数	1000.00
最終ジャッジ日時	2022-06-12 18:10:35
合計ジャッジ時間	20,803 ms
ジャッジサーバーID （参考情報）	judge15 / judge11
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	129 ms 21,916 KB
testcase_01	AC	143 ms 22,016 KB
testcase_02	AC	146 ms 21,964 KB
testcase_03	AC	133 ms 22,620 KB
testcase_04	AC	135 ms 22,228 KB
testcase_05	AC	133 ms 21,892 KB
testcase_06	AC	136 ms 22,620 KB
testcase_07	AC	132 ms 22,612 KB
testcase_08	AC	135 ms 22,612 KB
testcase_09	AC	141 ms 22,016 KB
testcase_10	AC	130 ms 21,992 KB
testcase_11	AC	144 ms 21,904 KB
testcase_12	AC	128 ms 21,928 KB
testcase_13	AC	125 ms 21,940 KB
testcase_14	AC	135 ms 22,600 KB
testcase_15	AC	127 ms 22,216 KB
testcase_16	AC	127 ms 22,264 KB
testcase_17	AC	127 ms 21,952 KB
testcase_18	AC	130 ms 22,216 KB
testcase_19	AC	130 ms 22,600 KB
testcase_20	AC	128 ms 22,228 KB
testcase_21	AC	143 ms 22,444 KB
testcase_22	AC	131 ms 22,620 KB
testcase_23	AC	128 ms 22,456 KB
testcase_24	AC	126 ms 21,892 KB
testcase_25	AC	136 ms 22,576 KB
testcase_26	AC	127 ms 22,264 KB
testcase_27	AC	132 ms 21,892 KB
testcase_28	AC	131 ms 22,612 KB
testcase_29	AC	126 ms 22,004 KB
testcase_30	AC	139 ms 22,612 KB
testcase_31	AC	141 ms 22,632 KB
testcase_32	AC	134 ms 22,228 KB
testcase_33	AC	131 ms 21,780 KB
testcase_34	AC	131 ms 22,444 KB
testcase_35	AC	132 ms 22,576 KB
testcase_36	AC	130 ms 22,620 KB
testcase_37	AC	130 ms 22,264 KB
testcase_38	AC	132 ms 22,600 KB
testcase_39	AC	129 ms 21,928 KB
testcase_40	AC	141 ms 21,940 KB
testcase_41	AC	132 ms 21,992 KB
testcase_42	AC	128 ms 21,892 KB
testcase_43	AC	143 ms 21,904 KB
testcase_44	AC	132 ms 21,904 KB
testcase_45	AC	132 ms 21,892 KB
testcase_46	AC	130 ms 21,940 KB
testcase_47	AC	130 ms 21,916 KB
testcase_48	AC	129 ms 22,432 KB
testcase_49	AC	140 ms 22,004 KB
testcase_50	AC	138 ms 22,564 KB
testcase_51	AC	128 ms 21,904 KB
testcase_52	AC	127 ms 21,992 KB
testcase_53	AC	129 ms 21,768 KB
testcase_54	AC	130 ms 22,204 KB
testcase_55	AC	133 ms 22,004 KB
testcase_56	AC	130 ms 21,992 KB
testcase_57	AC	135 ms 22,576 KB
testcase_58	AC	131 ms 21,940 KB
testcase_59	AC	144 ms 21,940 KB
testcase_60	AC	134 ms 22,276 KB
testcase_61	AC	140 ms 22,216 KB
testcase_62	AC	132 ms 21,904 KB
testcase_63	AC	132 ms 22,216 KB
testcase_64	AC	134 ms 21,808 KB
testcase_65	AC	134 ms 22,600 KB
testcase_66	AC	132 ms 21,952 KB
testcase_67	AC	131 ms 21,880 KB
testcase_68	AC	135 ms 21,992 KB
testcase_69	AC	147 ms 21,928 KB
testcase_70	AC	126 ms 22,016 KB
testcase_71	AC	128 ms 22,240 KB
testcase_72	AC	134 ms 22,432 KB
testcase_73	AC	130 ms 22,276 KB
testcase_74	AC	133 ms 21,992 KB
testcase_75	AC	133 ms 21,756 KB
testcase_76	AC	129 ms 21,780 KB
testcase_77	AC	130 ms 21,952 KB
testcase_78	AC	146 ms 22,552 KB
testcase_79	AC	146 ms 21,964 KB
testcase_80	AC	131 ms 21,992 KB
testcase_81	AC	132 ms 22,612 KB
testcase_82	AC	131 ms 22,692 KB
testcase_83	AC	135 ms 22,468 KB
testcase_84	AC	129 ms 21,780 KB
testcase_85	AC	132 ms 22,264 KB
testcase_86	AC	132 ms 22,276 KB
testcase_87	AC	139 ms 21,916 KB
testcase_88	AC	145 ms 22,444 KB
testcase_89	AC	131 ms 22,276 KB
testcase_90	AC	124 ms 22,216 KB
testcase_91	AC	126 ms 22,552 KB
testcase_92	AC	128 ms 22,576 KB
testcase_93	AC	132 ms 21,748 KB
testcase_94	AC	130 ms 21,648 KB
testcase_95	AC	131 ms 21,916 KB
testcase_96	AC	145 ms 22,108 KB
testcase_97	AC	149 ms 22,588 KB
testcase_98	AC	163 ms 21,928 KB
testcase_99	AC	157 ms 21,892 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

#include <sys/time.h>

using namespace std;

void debug() { 
    std::cerr << std::endl;
    std::cerr << "↑ [line:" << __LINE__ << "]" << std::endl;
}
template<class Head, class... Tail>
void debug(Head&& head, Tail&&... tail) {
    std::cerr << head << ", ";
    debug(std::forward<Tail>(tail)...);
}

class XorShift128 {
private:
    uint32_t x, y, z, w;

public:
    XorShift128() : x(123456789), y(362436069), z(521288629), w(88675123) { }
    uint32_t rnd() {
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    uint32_t rnd(const int n) {
        return rnd() % n;
    }

    uint32_t rnd(const int l, const int r) { // [l, r]
        return rnd() % (r - l + 1) + l;
    }
};

long long get_time() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    long long result =  tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
    return result;
}

template<class T>
ostream& operator<<(ostream& ostr, const vector<T>& vec) {
    ostr << "(";
    for (const T& val : vec) {
        ostr << val << ", ";
    }
    ostr << ")";
    return ostr;
}

mt19937 engine(890482);

XorShift128 xor_shift_128;
long long start;

const int N = 20;
const int MAX_TURNS = 1000;
const int MAX_MOVES = 400;
const int SH = 0, SW = 0, GH = N - 1, GW = N - 1;

const double NOT_ARRIVED = 2.0;
const double NO_WALL = 1.0;
const int NIL = -1;

const int DH[4]      = { -1,   0,   1,   0};
const int DW[4]      = {  0,  -1,   0,   1};
const char D_CHAR[4] = {'U', 'L', 'D', 'R'};

int H, W, P;
double prob;

array<array<double, N - 1>, N> no_wall_prob_ver;
array<array<double, N>, N - 1> no_wall_prob_hor;

void init() {
    // input
    cin >> H >> W >> P;

    // others
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            no_wall_prob_ver[i][j] = NOT_ARRIVED;
            no_wall_prob_hor[j][i] = NOT_ARRIVED;
        }
    }
    prob = (double)P / 100.0;
}

bool in_grid(int h, int w) {
    return 0 <= h && h < N && 0 <= w && w < N;
}

void print_output(const vector<int>& output) {
    for (const int di: output) {
        cerr << D_CHAR[di];
        cout << D_CHAR[di];
    }
    cerr << endl;
    cout << endl;
}

double& get_no_wall_prob(int hi, int wi, int hj, int wj) {
    if (hi == hj) {
        // vertical wall
        int mn = min(wi, wj);
        int mx = max(wi, wj);
        assert(mn + 1 == mx);
        return no_wall_prob_ver[hi][mn];
    } else if (wi == wj) {
        // horizontal wall
        int mn = min(hi, hj);
        int mx = max(hi, hj);
        assert(mn + 1 == mx);
        return no_wall_prob_hor[mn][wi];
    } else {
        assert(false);
    }
}

void update_no_wall_prob(const vector<int>& output, const int end_turn) {
    int h = SH, w = SW;
    for (int ti = 0; ti < end_turn - 1; ++ti) {
        int di = output[ti];
        int nh = h + DH[di];
        int nw = w + DW[di];
        double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);
        no_wall_prob = NO_WALL;
        h = nh;
        w = nw;
    }

    int di = output[end_turn - 1];
    int nh = h + DH[di];
    int nw = w + DW[di];
    double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);
    if (no_wall_prob == NOT_ARRIVED) {
        no_wall_prob = NO_WALL - 0.000001;
    }
    if (no_wall_prob < NO_WALL) {
        no_wall_prob *= prob;
    }

    // for (int hi = 0; hi < N; ++hi) {
    //     for (int wi = 0; wi < N - 1; ++wi) {
    //         cerr << "ver (" << hi << ", " << wi << "): " << no_wall_prob_ver[hi][wi] << endl;
    //     }
    // }
    // for (int hi = 0; hi < N - 1; ++hi) {
    //     for (int wi = 0; wi < N; ++wi) {
    //         cerr << "hor (" << hi << ", " << wi << "): " << no_wall_prob_hor[hi][wi] << endl;
    //     }
    // }
}

int get_opposite_dir(int di) {
    return (di + 2) % 4;
}

const double INF = 1000000.0;
array<int, 4> dir = {0, 1, 2, 3};
vector<int> find_shortest_path() {
    array<array<double, N>, N> dists;
    array<array<int, N>, N> prev;
    for (int hi = 0; hi < N; ++hi) {
        for (int wi = 0; wi < N; ++wi) {
            dists[hi][wi] = INF;
            prev[hi][wi] = NIL;
        }
    }
    dists[SH][SW] = 0.0;
    priority_queue<tuple<double, int, int>> pq;
    pq.emplace(make_tuple(-0.0, SH, SW));
    while (!pq.empty()) {
        tuple<double, int, int> tpl = pq.top(); pq.pop();
        double d = -get<0>(tpl);
        int h = get<1>(tpl);
        int w = get<2>(tpl);
        if (dists[h][w] != d) {
            continue;
        }
        if (h == GH && w == GW) {
            break;
        }

        shuffle(dir.begin(), dir.end(), engine);
        for (const int di : dir) {
            int nh = h + DH[di];
            int nw = w + DW[di];
            if (!in_grid(nh, nw)) {
                continue;
            }

            const double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);
            double nd = d + (NOT_ARRIVED - no_wall_prob);
            if (nd < dists[nh][nw]) {
                dists[nh][nw] = nd;
                prev[nh][nw] = di;
                pq.emplace(make_tuple(-nd, nh, nw));
            }
        }
    }

    // restore
    vector<int> route;
    int h = GH;
    int w = GW;
    while (!(h == SH && w == SW)) {
        int di = prev[h][w];
        route.emplace_back(di);
        int opp_di = get_opposite_dir(di);
        h += DH[opp_di];
        w += DW[opp_di];
    }
    reverse(route.begin(), route.end());
    
    return route;
}

void solve() {
    for (int turn = 0; turn < MAX_TURNS; ++turn) {
        cerr << "turn: " << turn << endl;
        vector<int> output = find_shortest_path();
        assert(output.size() <= MAX_MOVES);
        print_output(output);
        int end_turn;
        cin >> end_turn;
        if (end_turn == -1) {
            break;
        }
        update_no_wall_prob(output, end_turn);
    }
}

int main() {
    start = get_time();

    init();
    solve();

    long long end = get_time();
    cerr << "time elapsed: " << end - start << endl;
}

yukicoder

結果

テストケース

ソースコード