ABC417 振り返り：C問題突破とD問題の壁

みなさん、Atcoder ABC417 お疲れ様でした。
今回は A〜C の3完 という結果でした。久しぶりの 3 完でしたが、C 問題で少し手間取り、さらに RE（実行時エラー）も出してしまったこともあり、最終的にはレートを落とす結果となりました。

C問題の振り返り

問題は、整数列 A=(A1,A2,…,AN)が与えられ、
添字 i,j に対して

j−i=Ai+Aj

を満たす組の数を求める、という内容でした。

素直に二重ループで調べると計算量が O(Nの２乗)となり、N=2×10の5乗では間に合いません。

そこで式を変形し、

j−Aj=Ai+i

と整理しました。

とおくことで、f(j) と g(i) が一致する組み合わせの数を求めればよい、という発想です。

度数をカウントして掛け合わせることで、最終的な答えを計算できます。

例として、

fの度数が　０，０，１，０，２

gの度数が　０，１，１，２，１

の場合、

ｆとｇが一致する数は、0×0＋0×1 ＋ 1×1 + 0×2 + 2×1=3

となります。

実際のコード（抜粋）は以下の通りです。

rep(i,n){

cin >> a[i];

b[a[i]-(i+1)+size_bc/2]++;

}

rep(i,n) c[-(i+1)-a[i]+size_bc/2]++;

ll count = 0;

rep(i,size_bc) count += b[i] * c[i];

この方法で無事 AC を得ることができました。

D問題は「テンション管理」がテーマでした。
登場人物のテンション Xがあり、毎回与えられるプレゼントの価値 P、上昇値 A、下降値 B に応じて、

という更新を N 回行います。そしてこれらの処理全体を Q 回繰り返す、という問題です。

愚直にシミュレーションすると O(NQ) となり、計算時間が間に合わないため、最終状態から逆算し「分岐点」を管理する方法を考えましたが、まとまりませんでした。

公式解説・解説動画では DP・累積和・二分探索 を組み合わせた手法が紹介されており、やや高度で自分の手には余る内容だと感じました。

ポイントは、DP の横軸の数を最大 1000（= max(P) + max(A)）に抑えることで計算量を削減し、さらに 下降値 B に対して累積和を事前計算しておき、高速化のために二分探索を行う、という解法でした。

今振り返ると、D問題よりも E 問題にチャレンジした方がよかったかもしれません。（最短提出時間が D問題の数分の一であったため）問題選択の判断も今後の課題だと感じます。

これで 4 回連続でレートは下降中ですが、C 問題を解けたのは大きな収穫でした。
次回はさらに冷静に問題を選びつつ、もう一歩上を目指したいと思います。

最近は４回連続でレートが落ちていますが、久しぶりにＣ問題が解けたので、ほっとしています。次回は、４完を目指して頑張ります。