問題 解法 解答 問題 beta.atcoder.jp 解法 問題を読むと DP という気持ちになるので，以下のように DP を定義する： dp(i, f) := i 番目の要素まで見たときの最大値（f が true の時，効用を０にすることが可能で，f が false の時，効用を０に出来ない） f…

問題 解法 解答 問題 beta.atcoder.jp 解法 偶数行・列の長さの累積和と奇数行・列の長さの累積和の２つを計算しておく．そうすれば，各クエリにおいて座標が (偶数，偶数) と (奇数，奇数) の黒マスの面積の合計が O(1) で計算でき，この２つを足し合わせれ…

結果 A - Measure B - Exchange C - Align 結果 ３完（700 点・80:31），1389 位中 248 位，レート変動無し．途中参加になってしまったので Beginner の方に参加した．C 問題を一発 AC 出来たのはよかった． A - Measure beta.atcoder.jp B - Exchange beta.…

問題 解法 解答 問題 beta.atcoder.jp 解法 小さい数，大きい数，小さい数，... のように並べていくのが最適だと分かるので，隣り合う要素の差の合計の式を書くと， (a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n) になる．ここで，両端の要素を除いた …