Codeforces Round #517 (Div. 2)

久しぶりの投稿です(Codeforcesは久しぶりではない)

紫になりました。やったー!

D - Minimum Path

解法は以下のSlackのトークを参考にしてください。

f:id:xuzijian629:20181022113849p:plain

ところでこの問題を解いているときに、以前のHackerRankのUniversity Codesprint 5の問題を思い出しました(今回のこどふぉの問題よりずっと難しいしあんまり関係ない話です)。

www.hackerrank.com

これですね。今回はpathの長さが2n-1固定なので貪欲でいけましたが、どういう順序で回ってもいい場合は貪欲ではできません。その場合は、suffixに注目したDPをします。これは知っていたのですが、HackerRankはTLE解法を高速化して通したので、DPを書いたことがなく、今回の問題でけっこうびびりました。

DPにstringを保存する(つまり、dp[i]をi番目の頂点からゴールにいく文字列で最小のものとする)とMLEするので、何を保存するのかなと思いましたがdp[i]を、iから遷移できる頂点のうちもっとも辞書順で小さな頂点、としてできる。文字列の比較は、suffix arrayとかを使ってやる模様

↓↓参考↓↓

ei1333.hateblo.jp