問題文を読み違えて手間取った。
https://yukicoder.me/problems/no/1898
問題
N頂点の連結無向グラフがある。
各頂点には人が立っており、正整数の書かれたカードを3枚持っている。
プレイヤーは、正整数の書かれたカードをもって頂点1に降り立つ。
その後、辺に沿って移動するわけだが、最初の頂点1及び以降の移動時は、持っているカードの整数の和が、その頂点に立っている人のものより多くなければいけない。
その後、プレイヤーはカードを1枚だけその相手と交換できる(交換しなくてもよい)。
同じ点・辺を複数回移動し、複数回カードを交換してもよい場合、頂点Nに到達できる総和最小のカードの3枚組を答えよ。
解法
カードを入れ替えることを考えると、総和がSとなる3枚を選ぶなら、(S-2),1,1と組むのが最良である。
あとはSを二分探索しよう。
カードの整数の総和は増えるしかないので、一度到達可能になった点は以後何度も移動できる。
よって、実質複数回カード交換も可能となる。
例外として、初回頂点1のみ1回しかカードが交換できない。
これを踏まえて以下のように処理する。
- 初期状態で頂点1のプレイヤーに総和で勝てるか判定し、勝てるなら1枚カードを交換する。勝てないならこのSでは頂点Nに到達不可。
- その状態で、頂点1の隣接点のいずれかに移動可能か判定する。移動不可能であれば、このSでは頂点Nに到達不可。
- あとは任意回数カード交換が可能なので、未到達の頂点のうち、到達済み頂点に隣接し、かつそこにいる人の3枚のカードの総和が最小な順に移動していこう。
int N,M; vector<int> E[202020]; int A[202020],B[202020],C[202020]; int vis[202020]; int hoge(int CA) { int CB=1,CC=1; ZERO(vis); //初手だけ確認 if(CA+CB+CC<=A[0]+B[0]+C[0]) return 0; int add=max({0,A[0]-1,B[0]-1,C[0]-1}); int ok=0; FORR(e,E[0]) if(CA+CB+CC+add>A[e]+B[e]+C[e]) ok=1; if(ok==0) return 0; priority_queue<pair<int,int>> Q; vis[0]=1; Q.push({-A[0]-B[0]-C[0],0}); while(Q.size()) { int cur=Q.top().second; Q.pop(); if(A[cur]+B[cur]+C[cur]>=CA+CB+CC) return 0; if(cur==N-1) return 1; vector<int> V={CA,CB,CC,A[cur],B[cur],C[cur]}; sort(ALL(V)); CA=V[5]; CB=V[4]; CC=V[3]; FORR(e,E[cur]) if(vis[e]==0) { Q.push({-A[e]-B[e]-C[e],e}); vis[e]=1; } } return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } FOR(i,N) cin>>A[i]>>B[i]>>C[i]; int ret=1<<30; for(i=29;i>=0;i--) if(hoge(ret-(1<<i))) ret-=1<<i; cout<<ret<<" "<<1<<" "<<1<<endl; }
まとめ
最初交換できるカードにもう少し制限があるかと勘違いしてしまった。