結果

問題 No.5016 Worst Mayor
ユーザー 👑 platinumplatinum
提出日時 2023-04-29 16:59:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 220 ms / 2,000 ms
コード長 8,991 bytes
コンパイル時間 2,567 ms
コンパイル使用メモリ 138,764 KB
実行使用メモリ 24,492 KB
スコア 5,664,711,582
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 17:03:39
合計ジャッジ時間 15,652 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 193 ms
24,372 KB
testcase_01 AC 189 ms
23,568 KB
testcase_02 AC 186 ms
23,652 KB
testcase_03 AC 188 ms
23,640 KB
testcase_04 AC 189 ms
23,472 KB
testcase_05 AC 191 ms
23,580 KB
testcase_06 AC 216 ms
23,532 KB
testcase_07 AC 188 ms
24,372 KB
testcase_08 AC 187 ms
24,036 KB
testcase_09 AC 191 ms
24,384 KB
testcase_10 AC 187 ms
23,424 KB
testcase_11 AC 185 ms
24,036 KB
testcase_12 AC 190 ms
24,036 KB
testcase_13 AC 187 ms
23,376 KB
testcase_14 AC 186 ms
24,036 KB
testcase_15 AC 187 ms
23,868 KB
testcase_16 AC 186 ms
23,472 KB
testcase_17 AC 191 ms
23,628 KB
testcase_18 AC 192 ms
24,372 KB
testcase_19 AC 186 ms
24,072 KB
testcase_20 AC 189 ms
23,376 KB
testcase_21 AC 188 ms
23,520 KB
testcase_22 AC 189 ms
23,364 KB
testcase_23 AC 190 ms
23,880 KB
testcase_24 AC 186 ms
24,492 KB
testcase_25 AC 187 ms
24,372 KB
testcase_26 AC 185 ms
23,676 KB
testcase_27 AC 187 ms
24,096 KB
testcase_28 AC 218 ms
23,628 KB
testcase_29 AC 188 ms
24,480 KB
testcase_30 AC 199 ms
23,820 KB
testcase_31 AC 187 ms
23,460 KB
testcase_32 AC 188 ms
24,384 KB
testcase_33 AC 185 ms
23,688 KB
testcase_34 AC 186 ms
24,348 KB
testcase_35 AC 194 ms
23,688 KB
testcase_36 AC 187 ms
23,424 KB
testcase_37 AC 194 ms
23,580 KB
testcase_38 AC 213 ms
23,868 KB
testcase_39 AC 185 ms
24,360 KB
testcase_40 AC 188 ms
24,372 KB
testcase_41 AC 185 ms
24,060 KB
testcase_42 AC 184 ms
23,376 KB
testcase_43 AC 187 ms
23,640 KB
testcase_44 AC 212 ms
23,400 KB
testcase_45 AC 187 ms
23,676 KB
testcase_46 AC 186 ms
23,664 KB
testcase_47 AC 220 ms
24,252 KB
testcase_48 AC 188 ms
23,364 KB
testcase_49 AC 193 ms
23,436 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cassert>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)

using namespace std;
using LL = long long;
using pii = pair<int,int>;
const int INF = (int)1e9;
const LL LINF = (LL)1e18;
const int grid_size = 14;
const int max_turn = 400;

const int testcase = 0;

const int dy[4] = {0, 0, 1, -1};
const int dx[4] = {1, -1, 0, 0};

enum class file_status{
    local,
    debug,
    submit,
};
file_status now_status = file_status::submit;

void read_input(){
    std::stringstream ss;
    std::string num = std::to_string(testcase);
    int siz = num.size();
    for(int i = 0; i < 4 - siz; i++) num = '0' + num;
    ss << "in/" << num << ".txt";
    FILE *in = freopen(ss.str().c_str(), "r", stdin);
}
void file_output(){
    std::stringstream ss;
    std::string num = std::to_string(testcase);
    int siz = num.size();
    for(int i = 0; i < 4 - siz; i++) num = '0' + num;
    ss << "out/" << num << ".txt";
    FILE *out = freopen(ss.str().c_str(), "w", stdout);
}

random_device rnd;
mt19937 engine(rnd());

bool range_out(int y, int x){
    if(y < 0 || y >= grid_size) return true;
    if(x < 0 || x >= grid_size) return true;
    return false;
}

// 入力の受け取り
int N, T;
vector<pii> S, G;
// 各道路の評価 (0 - 181 が東西、182 - 363 が南北)
double roads[13*14*2];
vector<pii> road_eval;

struct road_pos{
    int a, b, c, d;
    road_pos(int a, int b, int c, int d) :
    a(a), b(b), c(c), d(d) {}
};
road_pos convert(int road_num){
    // 東西の道路
    if(road_num < 13 * 14){
        int y = road_num / 13, x = road_num % 13;
        int a = y + 1, c = y + 1;
        int b = x + 1, d = x + 2;
        return road_pos(a, b, c, d);
    }
    // 南北の道路
    else{
        road_num -= 13 * 14;
        int y = road_num % 13, x = road_num / 13;
        int a = y + 1, c = y + 2;
        int b = x + 1, d = x + 1;
        return road_pos(a, b, c, d);              
    }    
}
int calc_road_num(int y, int x, int k){
    // 東西の道路
    if(k == 0){ // 東へ
        return y * 13 + x;
    }
    else if(k == 1){ // 西へ
        return y * 13 + x - 1;
    }
    // 南北の道路
    else if(k == 2){ // 南へ
        return 13 * 14 + x * 13 + y;
    }
    else{ // 北へ
        return 13 * 14 + x * 13 + y - 1;
    }
}

struct path{
    int y, x;
    int highway;
    int dist;
    path(int y, int x, int h, int d) :
    y(y), x(x), highway(h), dist(d) {}
    bool operator> (const path& p) const{
        return dist > p.dist;
    }
};
LL CalcProfit(vector<int>& highway){
    LL res = 0;
    rep(i,N){
        priority_queue<path,vector<path>,greater<>> pq;
        vector dist = vector(grid_size, vector<int>(grid_size, INF));
        pq.emplace(S[i].first, S[i].second, 0, 0);
        dist[S[i].first][S[i].second] = 0;
        while(!pq.empty()){
            path p = pq.top(); pq.pop();
            if(p.y == G[i].first && p.x == G[i].second){
                res += 60 * p.highway;
                break;
            }
            if(p.dist != dist[p.y][p.x]) continue;
            rep(k,4){
                int ny = p.y + dy[k], nx = p.x + dx[k];
                if(range_out(ny, nx)) continue;
                int nd = p.dist;
                int road_num = calc_road_num(p.y, p.x, k);
                int cost = 1000;
                if(highway[road_num]){
                    cost = 223;
                }
                nd += cost;
                if(nd >= dist[ny][nx]) continue;
                dist[ny][nx] = nd;
                if(highway[road_num]){
                    pq.emplace(ny, nx, p.highway + 1, nd);
                }
                else{
                    pq.emplace(ny, nx, p.highway, nd);
                }
            }
        }
    }
    return res;
}

LL CalcScore(vector<pii>& actions){
    assert((int)actions.size() == T);
    LL res = (int)1e6;
    int staff = 1;
    vector<int> highway(13*14*2);
    for(auto& action : actions){
        int kind = action.first;
        if(kind == 1){
            int cost = 1e7 / sqrt((double)staff);
            assert(cost <= res);
            res -= cost;
            highway[action.second] = 1;
        }
        else if(kind == 2){
            staff++;
        }
        else{
            res += 50000;
        }
        /*
        LL profit = CalcProfit(highway);
        if(now_status == file_status::debug){
            cout << "profit = " << profit << endl;
        }
        res += profit;
        */
    }
    return res;
}

void calc_roads(){
    rep(i,N){
        int a = S[i].first, b = S[i].second;
        int c = G[i].first, d = G[i].second;
        if(a > c) swap(a, c);
        if(b > d) swap(b, d);
        double y_mid = (double)(a + c) / 2;
        double x_mid = (double)(b + d) / 2;
        double yl = (double)a - y_mid, yr = (double)c - y_mid;
        double xl = (double)b - x_mid, xr = (double)d - x_mid;
        // 東西の道路
        for(int y = a; y <= c; y++){
            for(int x = b; x < d; x++){
                int num = 13 * y + x;
                roads[num] += 20.0;
            }
        }
        // 南北の道路
        for(int x = b; x <= d; x++){
            for(int y = a; y < c; y++){
                int num = 13 * 14 + 13 * x + y;
                roads[num] += 20.0;
            }
        }
    }
    for(int i = 0; i < 13 * 14 * 2; i++){
        road_eval.emplace_back((int)roads[i], i);
    }
    sort(road_eval.begin(), road_eval.end(), greater<>());
}

struct node{
    int turn;
    LL cash;
    int staff, highway;
    LL eval;
    LL profit;
    vector<pii> actions;
    node(){
        turn = 0;
        cash = (int)1e6;
        staff = 1;
        highway = 0;
        eval = cash;
        profit = 0;
    }
    bool construction(){
        if(highway >= 13 * 14 * 2) return false;
        int cost = 1e7 / sqrt((double)staff);
        if(cost > cash) return false;
        cash -= cost; eval -= cost;
        eval += (max_turn - turn) * road_eval[highway].first;
        actions.emplace_back(1, road_eval[highway].second);
        // 収益を更新する
        /*
        vector<int> constructed_highway(13*14*2);
        for(int i = 0; i <= highway; i++){
            constructed_highway[road_eval[i].second] = 1;
        }
        profit = CalcProfit(constructed_highway);
        */
        profit += road_eval[highway].first;
        highway++;
        return true;
    }
    void gather_staff(){
        staff++;
        actions.emplace_back(2, -1);
    }
    void funding(){
        cash += 50000; eval += 50000;
        actions.emplace_back(3, -1);
    }
    void update(){
        turn++;
        cash += profit;
    }
    bool operator< (const node &v) const{
        return eval < v.eval;
    }
};

node BeamSearch(){
    priority_queue<node> pq;
    const int beam_width = 100;
    pq.emplace();
    rep(t,T){
        priority_queue<node> next_pq;
        rep(i,beam_width){
            if(pq.empty()) break;
            node v = pq.top(); pq.pop();
            // 高速道路の建設
            node v1 = v;
            if(v1.construction()){
                v1.update();
                next_pq.emplace(v1);
            }
            // 協力者の招集
            node v2 = v;
            v2.gather_staff();
            v2.update();
            next_pq.emplace(v2);
            
            // 資金調達
            if(v.turn > 100){
                node v3 = v;
                v3.funding();
                v3.update();
                next_pq.emplace(v3);
            }
        }
        pq = next_pq;
    }
    node best_node;
    int best_score = 0;
    while(!pq.empty()){
        node v = pq.top(); pq.pop();
        if(v.cash > best_score){
            best_node = v;
            best_score = v.cash;
        }
    }
    return best_node;
}

int main(){
    if(now_status != file_status::submit){
        read_input();
        file_output();
    }

    cin >> N >> T;
    rep(i,N){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        S.emplace_back(a, b);
        G.emplace_back(c, d);
    }
    calc_roads();
    if(now_status == file_status::debug){
        for(auto& val : road_eval){
            cout << val.first << " " << val.second << endl;
        }
    }

    node best_node = BeamSearch();
    vector<pii> ans = best_node.actions;
    rep(i,T){
        if(now_status == file_status::submit){
            int u, v;
            cin >> u >> v;
        }
        int kind = ans[i].first;
        if(kind == 1){
            int num = ans[i].second;
            road_pos p = convert(num);
            cout << kind << " " << p.a << " " << p.b
            << " " << p.c << " " << p.d << endl;
        }
        else cout << kind << endl;
    }
    if(now_status != file_status::submit){
        cerr << "score = " << CalcScore(ans) << endl;
    }

	return 0;
}
0