133. AtCoder参加記録（AtCoder Beginner Contest 267）

36回参加でレート 1374 です。

今回はパフォーマンス 1265 です。

ABCDを通して、FGExは未解答です。Eは通せず。Aで1ペナ…。

各問題の思考過程など。

A

問題

初回提出1分48秒、そこからACまで53秒。

配列に各文字列を入れてインデックスとの差を出力しました。Friday をコピペしたときに何故か空白が入っていて1ペナ…なんで…。

ACコード

B

問題

8分35秒。

書かれている通りにやるだけですが、まあまあ面倒くさかったです。

ACコード

C

問題

7分43秒。正直、Dより難しかったです。

区間の長さが決まっているので、1つずつずらして差分を見る方針が良さそう
計算式を考慮すると、たとえば始点が $i \rightarrow i + 1$ へずれたなら差分は $M \times A_{i+1} - \sum_{j = i}^{i+M-1} A_j$ になる
引き算部分は累積和を持っておけば $O(1)$ で求められるので、始点全探索で $O(N)$ となる

ACコード

D

問題

4分59秒。

Cとほぼ同じ問題で、連続という条件が外れたバージョン
制約を見ると $O(N^2)$ が通るようになっている。一項ずつ見ていって最適なものだけ残す感じにしたいので、DPを考える。
$dp[i,j] := (A_{i} まで見た時の、長さ j の部分列に対する与式の最大値)$ とすればOK。答えは $dp[N,M]$ 。

ACコード

E

問題

初回提出38分36秒。通せず。

この手のはとりあえず操作の反対側から考えてみるが、今回は逆に難しくなりそうなので素直に前から削除していくことに
各頂点に削除コストがあるとして、ある頂点を削除するとその頂点と隣接する頂点の削除コストが減っていくようなイメージ
貪欲アルゴリズムは思いつかないので、解の二分探索を考える。削除コストを MultiSet に入れて、削除可能な頂点を削除コストの大きい順に消して行ってみる。
実装がめちゃくちゃ重くなったが、サンプルは通ったし、 $O(N(\log N)(\log K))$ （ただし $K$ は解の存在しうる最大値）で実行時間制限4秒なので、まぁ大丈夫かな…と出してみるが、WAもTLEも出てボロボロ。
TLEだけならまだしも、WAが出ている意味がわからず、諦めてしまう

解説を読むと方針は普通に合っていて、何処かに実装ミスがあったのだと思われます。あと MultiSet が予想以上に重かったです。

（以下、Upsolve）

本番で提出したコードですが、MultiSet に加えて隣接点を管理していた nexts 変数のディープコピーがボトルネックになっていました。また、WAは二分探索の上限設定ミス（削除コストは隣接点の和を取ることを忘れていて $10^9$ にしていた）だったので、もう少しちゃんと考えれば通せていた問題でした。最近悪い意味で諦めが良くてダメですね…。