これはいろいろ難しい問題でした… 良い問題だと思います。 問題 codeforces.com 解法 まず方針です。なんとなく貪欲な気がしますが, 気づくのが難しいです。 next[i] = (x[i] から n 以内で進める場所にあって, p[i] よりもコストが小さい, 最もx[i] に近い…

こんな簡単に解けると思ってなかったので目からウロコでした。 問題 codeforces.com 解法 dp[n][sum] = ([1, n], [2, n], ..., [n-1, n] という区間で, 和が sum になる場合の数) というのを考えます(antimatter の分はマイナスで数えるので, 要するに dp[n]…

解いてる時はなんとなく提出したら正解だった, という感じでした。 問題 codeforces.com 解法 右に向いてるやつを左から順番に取っていき, その後に左に向いてるやつを右から順番に取っていく, というのが最適な milking の一つです(左に向いてるやつを右か…