AtCoder ABC369 C問題 がACにならない

Question

実現したいこと

• AtCoder の ABC369 の C問題がACにならない原因を突き止めたいです。

前提

AtCoder の ABC369 の C問題に回答したところ、AC * 19, WA * 2でWAとなりました。しかし、原因がわかりません。
問題のページのurlを以下に添付します。

https://atcoder.jp/contests/abc369/tasks/abc369_c

言語はC#を用いています。
アルゴリズムは尺取り法を用いました。

該当のソースコード

var n = long.Parse(Console.ReadLine());
var a = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList();

var r = 0;
var ans = 0;
for (int l = 0; l < n; l++) // l から始まる等差数列の数をansに足していく
{
    while (true)
    {
        if ((r > l + 1 && a[r] - a[r - 1] != a[l + 1] - a[l])) // r を含めると等差数列が終わる
        {
            r--; // 手前までは等差数列
            ans += r - l + 1;
            break;
        }
        else if (r == n - 1) // 最後まで到達し、尚且つ等差数列である
        {
            ans += r - l + 1;
            break;
        }
        r++;
    }
}
Console.WriteLine(ans);

試したこと

• 問題のページにある入力例を入力し、出力が出力例と一致することを確認しました。

• 極端な場合として N = 1の場合と、Aiが10^9に近い場合を試し、想定通りの出力であることを確認しました。

• ChatGPTを用いて原因究明を試みましたが、失敗に終わりました。

Answer 1

以下の入力例に対し、正しい出力は20000100000になるはずですが、ご提示のコードだと-1474736480になります。

200000
1 1 1 ...(20万個の繰り返し)... 1

Comments

[LunaShoot]

回答ありがとうございます。
Nが大きい場合に原因があるようなのでそれを踏まえてコードを改善してみます。

[LunaShoot]

ans が int型でオーバーフローしていたというとても初歩的なミスでした。long型に変えたら通りました。
ありがとうございました。

Answer 2

l == n-1の時に配列aの上限を超えてアクセスしてませんか？

    if ((r > l + 1 && a[r] - a[r - 1] != a[l + 1] - a[l])) // r を含めると等差数列が終わる

外側のループでlがインクリメントした際にrの値がそのままなのもおかしいですね。r=lにリセットしないとだめだと思います。

Comments

[LunaShoot]

回答ありがとうございます。私の考えでは、どちらも問題ないと思っています。

最初の条件 r > l + 1 の時点で l == n - 1 の場合ははじかれると思います。なぜなら、 r == n - 1 に達すると r++ が実行されないため、 r <= n - 1 だからです。

また、 r = l という初期化についてなのですが、 l が更新されるのは、等差数列が崩れた時です。例えば、l = 3 の場合、r = 7 までは等差数列であったが、 r = 8 を含めると等差数列ではなくなるという状況の時、 l = 4 となり、そのとき r = 7 となります( r-- によって)。ここで、l = 3 から r = 7 は等差数列だったので、 l = 4 から r = 7 も必ず等差数列になります。したがって、r = l と初期化せずとも、l はそのままでも問題ないと考えました。
また、 r = l と初期化しても誤りにはならないと思ったため書き加えて提出してみたところTLEとなりました。