O - Computer どういう思考で解いたかを書き下します indexは断わりが無ければ0-indexedです まず当然ですがコンピュータの性能は買うたびに良くなると考えていいです。 そして、この問題は使うコンピュータの性能ごとに、区間を分割する問題として考える事…

atcoder.jp 解説をみてピンと来なかったところを補足する形の自分用のメモです。 まず、K個を足して平均に置き換えるという操作は分かりにくいので 上のように操作をK分木で表す事にする そして、1の頂点の深さをa1....am 0の頂点の深さをb1.....bnとする す…

atcoder.jp 主客転倒 問題 左右対称な区間が与えられ、それぞれの区間には得点がある 得点は中心に近いほど高い。 D以上の間隔で点をN個まで置く時、得点の合計を最大化せよ 問題を言い換えていきます。 まず隣り合う点の距離はDだとして良いです なぜなら点…

atcoder.jp 解法 割り振り方において、Mで割った余りが異なる物同士は互いに影響を及ぼさないので、 割った余り毎にどう割り振るか組み合わせで考える。 また、K個ちょうどで考えると難しいので、K個のグループに分けるが0人のグループがあってもいいという…

D - Unique Subsequence 考えたこと dp[i] := iを先頭に使ったときの答えとして iを後ろから更新する時にどう遷移するかを考える 以降A[i]の後ろにA[j]から始まる部分列を付け加えられる事を iにjを加えられると呼ぶことにする 上の図を見るとA[i]==A[j]かつi

C - Maximize GCD 考えたこと 今回は関係ないが、よくある最大公約数の性質として gcd(A1, A2, ... , An) | sum(A1, A2, ... , An)となる 似た問題で何回かi, jを選びA[i]++, A[j]--としたうえでの最大公約数を最大化するものがあったが、それにはこの性質が…