Cまで三完。
Aからペナを出しやすい問題で、Bがかなり難しい、というDiv. 2としては珍しい回でした。
D. Sum of Paths
解説AC。
配列の各要素それぞれについて、何回ずつpathが通るのかを調べるのがこういう問題の定石。
ただ、それをどう求めれば良いかが難しい。
i番目の配列はi-1かi+1から来る……ということから、長さjのときの最終地点になるものが何個ずつあるかは求められるけど、それだけでは上手くいかない。
公式解説と同じくDP[i][j]で、「長さj, i番目のcellで終わるようなgood pathの個数」とする。
コンテスト後に思いついた方法は後ろから見るものだった。
終着点がDP[･][k]と分かっているから、それぞれがどこから来たかを調べていく。DP[i][j]はDP[i-1][j]とDP[i+1][j]から来ていることを考えれば、その割合が分かる。
たとえば、DP[i][j]のうち、i-1から来た分は、DP[i][j]*DP[i-1][j-1]/(DP[i-1][j-1]+D[i+1][j-1])と求められる。
……としていけば答えを求めることができる。（TLEの提出。PyPyだと厳しい気がするけど、高速な言語ならこの方法で通せるかも？）
公式解説はもっと賢かった。
j歩目でi番目のcellを通るものは、前から見るとj歩でこのcellにたどりつき、後ろから見るとk-j歩でこのcellにたどりついたものである。
よって、DP[i][k]*DP[i][j-k]が求めたいものだ！ というもの。
（DP[i][j]が、「i番目のcellから始まる長さjのgood pathの個数」とも捉えられることを使っている。）
この方法だと割り算する必要がないため、PyPyでもTLEせずにACできる。
0 件のコメント:
コメントを投稿