pretestは全完でした。→システムテストも通っていました！
ツイートだと読みにくいと思うので、Gだけ補足。
G. Moving to the Capital
Step1 都市1から各都市が何歩でいけるか（問題文中のdを）調べる。ここではDと書く。
Step2 それぞれの都市iから逆向きに一歩進んだ都市をjとして、ANS[i]=min(D[i],D[j])とする。高々一回だけ問題文中の2の移動をして良い、というルールを使った感じです。
Step3 各都市からDが大きい方へたどってみてANSの最小値が答え。問題文の1の移動でDが大きい方へは進めるので、これで答えが求まります。
としました。
Step3は再帰で書くのが簡単だと思う……けれど、CodeforcesのPyPyではこの深さの再帰は無理（エラーが出る）。（なお、AtCoderならエラーなしでいけるはずですが、PyPyの再帰は遅いので、間に合うかは分かりません）
なので、どうしようか考えたけど、Dが大きい都市から見ていけば再帰なしでいけた。
0 件のコメント:
コメントを投稿