人権なし

競プロで解いた問題や開発の進捗などの記録です

2018-10-28から1日間の記事一覧

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open):B - Neutralize

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

技術室奥プログラミングコンテスト #3:D - 巨大チェスボード

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

Tenka1 Programmer Beginner Contest

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

Tenka1 Programmer Beginner Contest:C - Align

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