RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1177346

Source codeソースコード

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision

#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif
#define pops(x) __builtin_popcount(x)
using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL  MOD=1E9+7;
constexpr double eps=1e-7;
struct Action{
    string str;
    vector<int> ints;
};
int change_cnt,pass_cnt;
vector<int> sold(10),came(10);

struct Problem{
    const int turn= 1000;
    const int cap_combination=24310;
    const vector<int> ttttt={1000,100,10,1};
    const int bound=31;
    //const vector<int> sell_thre={20,26,30,34,37,39,42,44,46,48};
    const vector<int> sell_thre={20,22,24,26,28,30,32,34,36,38};
    const int search_width=5;
    const int c_f=40;
    const double score_per_turn=75.0;

    int n,d,t;
    vector<vector<int>> index;
    vector<vector<vector<int>>> graph;
    vector<vector<vector<int>>> sellable_masks;
    vector<vector<pair<int,double>>> shortest_time;
    vector<vector<int>> best_change;
    vector<double> state_value;
    unordered_map<LL,int> mp;
    vector<int> capacity,amount,tank_num;
    queue<Action> Q;
    bool give_up;
    Problem(LL n):
        n(n),
        graph(cap_combination,vector<vector<int>>(8)),
        sellable_masks (cap_combination,vector<vector<int>>(51,vector<int>())),
        shortest_time (cap_combination,vector<pair<int,double>>(51)),
        best_change(cap_combination,vector<int>(51,-1)),
        state_value(cap_combination),
        capacity(n),
        amount(n),
        tank_num(n),
        give_up(false){};

    void solve(){
        precalc();
        for(int i=0; i<turn; ++i){
            input();
            if(!Q.empty()){
                act();
                continue;
            }
            int tank_state=mp[get_tank_state(capacity)];
            int filled= get_filled_mask(capacity, amount);
            vector<pair<int,int>> tanks_select;
            for(auto i : sellable_masks[tank_state][d]){
                tanks_select.emplace_back(pops(i-(i&filled)),i);
            }
            sort(tanks_select.begin(),tanks_select.end());
            auto it=lower_bound(tanks_select.begin(),tanks_select.end(),make_pair(min(threshold(),t),0));
            if(it>tanks_select.begin() /*&& d>=sell_thre[(it-1)->first]*/ /*d>=bound*/){ //詰めて売れる
                vector<int> to_sell={0};
                auto nxt=lower_bound(tanks_select.begin(),tanks_select.end(),make_pair((it-1)->first,0));
                int mask=nxt->second-(nxt->second&filled);
                DBG(mask,filled,nxt->second)
                for(int b=0; b<8; ++b){
                    if(mask&(1<<b))Q.push({"fill",{tank_num[b]}});
                    if(nxt->second&(1<<b)){
                        to_sell[0]++;
                        to_sell.push_back(tank_num[b]);
                    }
                }
                //暇ならfillしておく
                for(int b=7; b>=0; --b){
                    if (!(filled&(1<<b))&& !(mask&(1<<b)) && (int)Q.size()<t-1){
                        Q.push({"fill",{tank_num[b]}});
                    }
                }
                Q.push({"sell",to_sell});
            }else if(d>=bound){
                //move?

                pair<int,int>success_rate;
                if(!give_up){
                    success_rate=change_success_rate(tank_state,filled);
                    DBG(success_rate)
                }
                if(!give_up && (double)success_rate.first/ttttt[0]*d*d/t>score_per_turn){//changeして勝負
                    Q.push({"change",{tank_num[success_rate.second]}});
                }else{//降りた
                    give_up=true;
                    //if(accumulate(capacity.begin(),capacity.end(),0)<c_f){
                    if(false){
                        Q.push({"change",{tank_num[0]}});
                    }else{
                        Q.push(change_fill_pass(tank_state,filled));
                    }
                }
            }else{ //安いので売らない
                Q.push(change_fill_pass(tank_state,filled));
            }
            #if MYDEBUG
            usleep(20000);
            cerr<<flush;
            #endif
            act();
        }
    }
    int threshold(){
        for(int i=0; i<8; ++i){
            if(d<sell_thre[i])return i;
        }
        return 8;
    }

    double evaluate(int state, int mask, int pass=0){
        double ret=0.0;
        for(int nxt_d=bound; nxt_d<=50; ++nxt_d){
            int min_step=10,max_step=8-pops(mask);
            //int diff=140-max_step;
            //int diff=60+max_step;
            int diff=100;
            for(auto i : sellable_masks[state][nxt_d]){
                min_step=min(min_step,pops(i-(i&mask)));
            }
            if(min_step<10){
                for(int nxt_t=min_step+1; nxt_t<=10; ++nxt_t){
                    //ret+=(nxt_d*nxt_d+1000-(min(max_step+1,nxt_t)*100)/100;
                    ret+=(nxt_d*nxt_d+diff*10-(min(max_step+1,nxt_t)+1-pass)*diff)/100;
                }
            }else{
                ret+=nxt_d*nxt_d*shortest_time[state][nxt_d].second;
                //
            }
        }
        return ret/(50-bound+1);
    }

    Action change_fill_pass(int state, int filled){
        double pass_score=evaluate(state, filled,1),maxi=pass_score;
        DBG(pass_score)
        Action ret={"pass",{}};
        //change smallest
        for(int i=0; i<2; ++i){
            double change_score=0.0;
            if(i&&(index[state][i]==index[state][i-1])) continue;
            vector<pair<int,int>> amount(8),tmp(8);
            for(int j=0; j<8; ++j){
                amount[j].first=index[state][j];
                amount[j].second=((filled>>j)&1);
            }
            amount[i].second=0;
            for(int draw=1; draw<=10; ++draw){//generate new state
                tmp=amount;
                tmp[i].first=draw;
                sort(tmp.begin(),tmp.end());
                vector<int> nxt(8);
                int new_mask=0;
                for(int j=0; j<8; ++j){
                    nxt[j]=tmp[j].first;
                    new_mask+=(tmp[j].second<<j);
                }
                int new_state=mp[get_tank_state(nxt)];
                change_score+=evaluate(new_state,new_mask,t==1);
            }
            change_score/=10;
            DBG(change_score)
            if(change_score>maxi){
                maxi=change_score;
                ret={"change",{tank_num[i]}};
            }
        }
        //fill largest empty tank
        if(filled!=255){
            int b;
            for(b=7; b>=0; --b){
                if(!((filled>>b)&1)) break;
            }
            double fill_score=evaluate(state,filled|(1<<b),t==1);
            DBG(fill_score)
            if(fill_score>maxi){
                maxi=fill_score;
                ret={"fill",{tank_num[b]}};
            }
        }
        return ret;
    }

    pair<int,int> change_success_rate(int state, int fill_mask,int depth=1){
        int maxi=0,ret=0;
        for(int i=0; i<search_width; ++i){
            if(i&&(index[state][i]==index[state][i-1])) continue;
            vector<pair<int,int>> now(8),tmp(8);
            for(int j=0; j<8; ++j){
                now[j].first=index[state][j];
                now[j].second=((fill_mask>>j)&1);
            }
            int cnt=0;
            now[i].second=0;
            for(int draw=1; draw<=10; ++draw){
                tmp=now;
                tmp[i].first=draw;
                sort(tmp.begin(),tmp.end());
                vector<int> nxt(8);
                int new_mask=0;
                for(int j=0; j<8; ++j){
                    nxt[j]=tmp[j].first;
                    new_mask+=(tmp[j].second<<j);
                }
                int new_state=mp[get_tank_state(nxt)];
                bool f=false;
                for(auto v: sellable_masks[new_state][d]){
                    if(pops(v-(v&new_mask))<t-depth){
                        cnt+=ttttt[depth];
                        f=true;
                        break;
                    }
                }
                if(depth<=2&&!f){
                    cnt+=change_success_rate(new_state,new_mask,depth+1).first;
                }
            }
            if(cnt>ret)maxi=i,ret=cnt;
        }
        return {ret,maxi};
    }

    void precalc(){
        vector<int> loop(8);
        int cnt=0;
        for(loop[0]=1; loop[0]<=10; ++loop[0]){
            for(loop[1]=loop[0]; loop[1]<=10; ++loop[1]){
                for(loop[2]=loop[1]; loop[2]<=10; ++loop[2]){
                    for(loop[3]=loop[2]; loop[3]<=10; ++loop[3]){
                        for(loop[4]=loop[3]; loop[4]<=10; ++loop[4]){
                            for(loop[5]=loop[4]; loop[5]<=10; ++loop[5]){
                                for(loop[6]=loop[5]; loop[6]<=10; ++loop[6]){
                                    for(loop[7]=loop[6]; loop[7]<=10; ++loop[7]){
                                        LL tmp=0;
                                        for(int i=0; i<8; ++i){
                                            tmp+=loop[i];
                                            tmp<<=4;
                                        }
                                        index.push_back(loop);
                                        mp[tmp]=cnt;
                                        bf(loop,sellable_masks[cnt],shortest_time[cnt]);
                                        cnt++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i=0; i<cap_combination; ++i){
            vector<int> tmp;
            for(int j=0; j<n; ++j){
                for(int k=1;k<=10; ++k){
                    tmp=index[i];
                    tmp[j]=k;
                    sort(tmp.begin(),tmp.end());
                    int nxt=mp[get_tank_state(tmp)];
                    graph[i][j].push_back(nxt);
                }
            }
        }
        for(int dist=0; dist<2; ++dist){ //距離"dist"まで
            for(int i=0; i<cap_combination; ++i){
                for(int a=bound; a<=50; ++a){
                    double maxi=shortest_time[i][a].second*60;
                    for(int j=0; j<n; ++j){
                        double tmp=0;
                        for(int v: graph[i][j]){
                            tmp+=(5.0-shortest_time[v][a].second*2)*shortest_time[v][a].second;
                            //tmp+=6*shortest_time[v][a].second/(1.0+shortest_time[v][a].second);
                            //1/(1+1/x)~=(-2x^2+5x)/6 (0<x<1)
                        }
                        if(tmp>maxi){
                            maxi=tmp;
                            best_change[i][a]=j;
                        }
                    }
                    shortest_time[i][a].second=maxi/60;
                }
            }
        }
    }

    void bf(vector<int>&c, vector<vector<int>> &t_table, vector<pair<int,double>> &s){
        for(int i=bound; i<=50; ++i){
            s[i].second=10000.0; //inf
            //
        }
        for(int filling_tank=1; filling_tank<=255; ++filling_tank){
            int amount=0;
            int bitcnt=0;
            for(int b=0; b<8; ++b){
                if((filling_tank>>b)&1){
                    amount+=c[b];
                    ++bitcnt;
                }
            }
            if(bound<=amount && amount<=50){
                t_table[amount].push_back(filling_tank);
                s[amount].second=min(s[amount].second,(double)bitcnt);
                //
            }
        }
        for(int i=bound; i<=50; ++i){
            sort(t_table[i].begin(),t_table[i].end());
            s[i].second=1.0/s[i].second;
            //
        }
    }

    LL get_tank_state(vector<int> &c){
        LL ret=0;
        for(int i=0; i<8; ++i){
            ret+=c[i];
            ret<<=4;
        }
        return ret;
    }

    int get_filled_mask(vector<int> &c, vector<int> &a){
        int ret=0;
        for(int i=0; i<8; ++i){
            if(c[i]==a[i])ret+=(1<<i);
        }
        return ret;
    }

    void input(){
        cin >> d >> t;
        vector<vector<int>> p(8,vector<int>(3));
        for(int i=0; i<n; ++i){
            cin >> p[i][0];
        }
        for(int i=0; i<n; ++i){
            cin >> p[i][1];
            p[i][2]=i+1;
        }
        sort(p.begin(),p.end());
        for(int i=0; i<n; ++i){
            capacity[i]=p[i][0];
            amount[i]=p[i][1];
            tank_num[i]=p[i][2];
        }
    }

    void act(){
        if(t==1 || Q.front().str=="pass" || Q.front().str =="sell"){
            give_up=false;
            came[(d-1)/5]++;
            if(Q.front().str =="sell")sold[(d-1)/5]++;
        }
        if(Q.front().str =="change")change_cnt++;
        if(Q.front().str =="pass")pass_cnt++;
        cout << Q.front().str;
        for(auto i : Q.front().ints)cout << ' ' <<i;
        cout << endl;
        Q.pop();
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    long long n=8;
    Problem p(n);
    p.solve();
    cerr<<"changed:"<<change_cnt<<"\n";
    cerr<<"passed:"<<pass_cnt<<"\n";
    for(int i=0; i<10; ++i){
        cerr<<i<<' '<<came[i]<<' '<<sold[i]<<endl;
    }
    return 0;
}

Submission

Task問題 A - 石油王Xの憂鬱
User nameユーザ名 057_Hoi_koro
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 7756219
Source lengthソースコード長 13839 Byte
File nameファイル名
Exec time実行時間 1445 ms
Memory usageメモリ使用量 93448 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 149628 / 417500 subtask_01_01.txt
test_02 152868 / 417500 subtask_01_02.txt
test_03 154181 / 417500 subtask_01_03.txt
test_04 159380 / 417500 subtask_01_04.txt
test_05 144011 / 417500 subtask_01_05.txt
test_06 156419 / 417500 subtask_01_06.txt
test_07 161438 / 417500 subtask_01_07.txt
test_08 154121 / 417500 subtask_01_08.txt
test_09 165265 / 417500 subtask_01_09.txt
test_10 167489 / 417500 subtask_01_10.txt
test_11 162196 / 417500 subtask_01_11.txt
test_12 154229 / 417500 subtask_01_12.txt
test_13 154671 / 417500 subtask_01_13.txt
test_14 155402 / 417500 subtask_01_14.txt
test_15 150338 / 417500 subtask_01_15.txt
test_16 157852 / 417500 subtask_01_16.txt
test_17 155893 / 417500 subtask_01_17.txt
test_18 157589 / 417500 subtask_01_18.txt
test_19 155660 / 417500 subtask_01_19.txt
test_20 153333 / 417500 subtask_01_20.txt
test_21 154590 / 417500 subtask_01_21.txt
test_22 157802 / 417500 subtask_01_22.txt
test_23 146123 / 417500 subtask_01_23.txt
test_24 149175 / 417500 subtask_01_24.txt
test_25 156438 / 417500 subtask_01_25.txt
test_26 153703 / 417500 subtask_01_26.txt
test_27 162304 / 417500 subtask_01_27.txt
test_28 158375 / 417500 subtask_01_28.txt
test_29 153439 / 417500 subtask_01_29.txt
test_30 149238 / 417500 subtask_01_30.txt
test_31 159648 / 417500 subtask_01_31.txt
test_32 149844 / 417500 subtask_01_32.txt
test_33 154375 / 417500 subtask_01_33.txt
test_34 153425 / 417500 subtask_01_34.txt
test_35 154298 / 417500 subtask_01_35.txt
test_36 154755 / 417500 subtask_01_36.txt
test_37 158244 / 417500 subtask_01_37.txt
test_38 152709 / 417500 subtask_01_38.txt
test_39 149987 / 417500 subtask_01_39.txt
test_40 154411 / 417500 subtask_01_40.txt
test_41 158187 / 417500 subtask_01_41.txt
test_42 151870 / 417500 subtask_01_42.txt
test_43 150276 / 417500 subtask_01_43.txt
test_44 160220 / 417500 subtask_01_44.txt
test_45 155603 / 417500 subtask_01_45.txt
test_46 153142 / 417500 subtask_01_46.txt
test_47 156204 / 417500 subtask_01_47.txt
test_48 155482 / 417500 subtask_01_48.txt
test_49 151638 / 417500 subtask_01_49.txt
test_50 158751 / 417500 subtask_01_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 990 ms 91400 KB
subtask_01_02.txt AC 1154 ms 91400 KB
subtask_01_03.txt AC 964 ms 91404 KB
subtask_01_04.txt AC 1240 ms 91404 KB
subtask_01_05.txt AC 1154 ms 91404 KB
subtask_01_06.txt AC 1052 ms 91400 KB
subtask_01_07.txt AC 1153 ms 91396 KB
subtask_01_08.txt AC 1120 ms 91400 KB
subtask_01_09.txt AC 1206 ms 91396 KB
subtask_01_10.txt AC 1056 ms 91400 KB
subtask_01_11.txt AC 1239 ms 91400 KB
subtask_01_12.txt AC 1445 ms 91400 KB
subtask_01_13.txt AC 1191 ms 91408 KB
subtask_01_14.txt AC 1155 ms 91404 KB
subtask_01_15.txt AC 1049 ms 91404 KB
subtask_01_16.txt AC 1063 ms 91396 KB
subtask_01_17.txt AC 1150 ms 91404 KB
subtask_01_18.txt AC 1033 ms 91404 KB
subtask_01_19.txt AC 1106 ms 93448 KB
subtask_01_20.txt AC 1168 ms 91404 KB
subtask_01_21.txt AC 1098 ms 91404 KB
subtask_01_22.txt AC 1203 ms 91400 KB
subtask_01_23.txt AC 1159 ms 91400 KB
subtask_01_24.txt AC 1136 ms 91404 KB
subtask_01_25.txt AC 1223 ms 93448 KB
subtask_01_26.txt AC 1046 ms 91400 KB
subtask_01_27.txt AC 1220 ms 91400 KB
subtask_01_28.txt AC 1071 ms 91392 KB
subtask_01_29.txt AC 1119 ms 91404 KB
subtask_01_30.txt AC 1180 ms 91400 KB
subtask_01_31.txt AC 1029 ms 91400 KB
subtask_01_32.txt AC 1047 ms 91404 KB
subtask_01_33.txt AC 994 ms 91404 KB
subtask_01_34.txt AC 1151 ms 91400 KB
subtask_01_35.txt AC 1146 ms 91400 KB
subtask_01_36.txt AC 1106 ms 91400 KB
subtask_01_37.txt AC 1216 ms 91400 KB
subtask_01_38.txt AC 1080 ms 91396 KB
subtask_01_39.txt AC 1123 ms 91400 KB
subtask_01_40.txt AC 1111 ms 91396 KB
subtask_01_41.txt AC 1169 ms 91400 KB
subtask_01_42.txt AC 1210 ms 91396 KB
subtask_01_43.txt AC 1089 ms 91404 KB
subtask_01_44.txt AC 1097 ms 93448 KB
subtask_01_45.txt AC 1057 ms 91404 KB
subtask_01_46.txt AC 1095 ms 91400 KB
subtask_01_47.txt AC 1160 ms 91400 KB
subtask_01_48.txt AC 1222 ms 91396 KB
subtask_01_49.txt AC 980 ms 91400 KB
subtask_01_50.txt AC 1100 ms 91404 KB