全完と思ったらG2をHackされてしまった。
コンテスト後のツイート
G1 行って帰るコストを前計算して貪欲
— titia (@titia_til) February 3, 2023
G2 0もしくはn+1から行ってテレポートするまでのコストを前計算し、小さい順に取っていく。初回は0から行かなくてはいけないので、全てn+1から行っていた場合は、一回を0からに変更できるか調べる
G2. Teleporters (Hard Version)
解説AC。
ツイートで書いたのは本質的に間違っていた。（大枠はあっているので、このツイートの解法だけ読むと正しいようにも見えるが、正しい解法を理解はしていなかった）
ツイートの通り、
・0もしくはn+1から行ってテレポートするまでのコストを前計算し、小さい順に取っていく
として、0から行ったものが一つでもあればOK。問題は全てn+1から行っていた場合。
一回だけ0から行き、他はn+1から行くことになるので、n+1だけから行ったものだけをソートし（Bとする）、累積和を取っておく。その上で、
・0から行ってi番目のものを取ったとする。すると、残りは、c-(A[i]+i+1)。これを累積和に対して二分探索し、そのindexをxとする。xより前にBにA[i]+(n-i)があるか調べ、あればx-1が答えの候補。なければ、xが答えの候補。
・さらに、xの前にA[i]+n-iがある場合は、c-(A[i]+i+1)+(A[i]+n-i)まで使えるので、これを累積和に対して二分探索する。似たような場合分けして、答えの候補が得られる。
という感じで解ける。
後半の処理がDiv.4にしてはかなり難しかった。
また、この説明では添え字をいい加減に書いているが、添え字を合わせるのも大変。
0 件のコメント:
コメントを投稿