きろく

特筆すべき記録のまとめ

JOI 難易度7問題

JOI '18 予選:5 - 森林伐採

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j, d) := マス (i, j) まで d 個のマス(マス (0, 0) と (H, W) を含む)を経由して行くときのコスト」と DP を立てる.マス (i, j) へはマス (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j) から行くこ…

JOI '18 予選:4 - 水ようかん

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j) := 左端から i 個までを切った後のピースの長さが j 以上になるようにうまく切った時の答え」で DP を立てる.DP の漸化式は, dp(i, j) = min( max( dp(k, j), (区間 (k + 1) ~ i の長さ) - j ) ) と…