今日の競プロ(2020/4/14) - gyouzasushi’s diary

JOI 2問

グリッドを有向グラフと見たときの閉路の長さの合計。

連結成分ごとに考える。ある頂点に置かれたロボットが十分な時間のあとにどの頂点にいるか、は「閉路中の適当な頂点までの距離 mod 閉路の長さ」によって決まるので、これが被らないように数えていく。実装だいぶ苦労したけど、最終的に結構すっきり書けて嬉しい。

$dp[i][j][k]=i$ 行目 $j$ 番目の石まで、一行飛ばし $k$ 回で行くときの危険度の $\min$ 。

座標圧縮 + いもす法。メモリ制限64MBがちょっとしんどかったけど、連結判定に幅優先探索を使ったらいけた。××深さ優先探索　×UnionFind