104. AtCoder参加記録（AtCoder Beginner Contest 248）

15回参加でレート 1035 です。

f:id:ibako_piyo:20220416231256p:plain

f:id:ibako_piyo:20220416231325p:plain

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

ABCDを通して、FGExは未解答です。Eは通せず。

f:id:ibako_piyo:20220416231415p:plain

各問題の感想など。

2分6秒。

数列に分解して HashSet から除外して残ったものを出すようにしました。

2分2秒。

倍々ゲームなので早々に決着します。というわけで、計算量を深く考えなくても普通にシミュレーションすればOK。

13分55秒。

割とややこしいDPです。 $dp[i 番目まで見た, 総和が j ] := 通り数$ 。

遷移は、 $\displaystyle dp[i, j] = \sum_{k=\max(1, j-M)}^{j - 1} dp[i - 1, k]$ 。

初期状態は、 $dp[1, j] = 1 (1 \le j \le M)$ 、 $dp[1, j] = 0 (M \lt j \le K)$ 。

計算量は $O(NKM)$ です。

14分33秒。

数列に登場した数ごとに、前から順にインデックスリストを作っておきます。クエリでは二分探索で条件を満たす（インデックスリストにおける）最大インデックス・最小インデックスを出せば、答えを求められます。

計算量は $O(N + Q \log N)$ 。

$K = 1$ のとき明らかに Infinity です。また、 $K \ge 2$ であれば直線は一意に定まります。

2点を取って直線を算出し、ここから重複したものを省けばよいとは思いましたが、何か無限にバグらせていて 3WA で撃沈。幾何を久々に見たので、ちゃんと復習しておきます…。Diff 的にも解きたい問題でした。

Eを見て嫌な予感がしたのでこっちも見てみましたが、少し考えて青Diffっぽさを感じたのでやめました。

見てないです。

C をもう少し早く通したかったのと、E は普通に悔しいな、と思いました。水パフォ出せるようにならないと…。

イバコの生存記録