読み替えに気付くかがカギ。
https://atcoder.jp/contests/abc236/tasks/abc236_g
問題
N頂点T有向辺のグラフが与えられる。
T個の辺は順番がつけられている。
f(i)を、T個の辺のうち先頭f(i)個の辺だけ利用できるとき、1番の頂点からi番の頂点に、ちょうどL回辺に沿った遷移をすることで到達できるような最小の値とする。
各頂点iについてf(i)を答えよ。
解法
j番目の辺の重みをjとすると、f(i)は重みf(i)以下の辺だけでi番の頂点に到達できるような最小の重み、となる。
E(u,v,n) := 辺に沿ってn回移動したとき、u→vに遷移できるような最小の重み(どうやっても遷移不可な場合はinf)
とすると、EをダブリングすることでE(1,i,L)を求めればこれがf(i)となる。
int N,T,L; const int MAT=100; struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);v[0][0]=v[1][1]=1;};}; // Mat mulmat(Mat& a,Mat& b,int n=MAT) { int x,y,z; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=1<<20; FOR(x,n) FOR(z,n) FOR(y,n) { chmin(r.v[x][y],max(a.v[x][z],b.v[z][y])); } return r; } Mat powmat(ll p,Mat a,int n=MAT) { int i,x,y; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=(x==y)?0:(1<<20); while(p) { if(p%2) r=mulmat(r,a,n); a=mulmat(a,a,n); p>>=1; } return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>T>>L; Mat A; FOR(x,N) FOR(y,N) A.v[x][y]=1<<20; FOR(i,T) { cin>>x>>y; A.v[y-1][x-1]=i+1; } A=powmat(L,A,N); FOR(i,N) { x=A.v[i][0]; if(x==1<<20) x=-1; cout<<x<<" "; } cout<<endl; }
まとめ
この言い換え賢いな。