【C#】ABC417 C問題のみ解説備忘録

筆者が数学苦手勢なので、そういう人向けです。数学得意な人からすれば同じことを言い方だけ変えて言いまくっているようなものです。

使用環境　C# 11.0
　　　　　.NET 7.0.20

C問題はj-i=A[i]+A[j]となるようなiとjの組み合わせを数えるというもの。

制約は1<=N<=200000、数列Aの各要素も同じく200000まで。

つまりはindex（要素の番号）同士の差と、同じ位置にある数列の数同士の和が一緒になればよい。

まずは素朴に探索していく解法を考える。

iを0からnまで、jをiからnまでとしたfor文中にj-i=A[i]+A[j]を判別するif文を書けば全探索ができそう。

しかし、問題中の制約下では組み合わせnCrにより19,999,900,000（約199億）通りとなり、確実に間に合わない。

どうにかできそうなのはj-i=A[i]+A[j]の式なのだけど、どうにかして=の右辺か左辺にi同士、j同士をくっつけられそうな気がする。まあそれ中学数学でやるやつらしいんだけど

そうして式を変形して簡略化できる、ということはiを固定すると探索すべきjが定まって簡単に探索できることに気付くはず。iを計算して、それに合うjも探索する。O(n)でいけそうな気がしてくる。

具体的にはj-i=A[i]+A[j]は移項すればj-A[j]=i+A[i]のように変形できる。i+A[i]の登場回数を保存しておき、j-A[j]を探索してその分の登場回数を回答用の変数に足していけばよい。

他のアプローチもあると思うが、筆者のやり方ではi+A[i]を配列のindexとして、動的計画法っぽくdp[i+A[i]]++とすれば、dp[j-A[j]]でそのまま登場回数にアクセスできる。dp[]の要素数はi+A[i]が上限なので制約的にも400000で十分。この動的計画法っぽい書き方はC問題やD問題で割と頻出するような気がする。実装上は別に動的計画法でもなんでもないけど。配列を利用したこういう書き方は割と便利だったというか配列の要素数そのものに意味を付加するやり方が実践中に思い浮かぶかどうか。頭のいい人とか何年もプログラミングやってる人からすれば、もはや定番の手法なのかもなあというところ。特に解説が必要ないくらい。

ここら辺は公式解説のC++のコード例ではmapという連想配列を使ってたけど、全く同じ働きをする型がC#にはない。keyが無ければアクセス時に勝手に作ってくれるとかそういうやつ。
Dictionary<k,v>が近いけど、C#らしいお作法が必要で少し面倒。下記みたいなやつで確かめてみた。

// Dictionary<k,v>はこう使うのだ
Dictionary<int,int> dict = new()
{
    [0] = 1,
    [1] = 2,
    [2] = 3
};

dict[0]++;    // ブラケット記法を使ったインクリメントは可能
//dict[3]++ 実行時例外、初期化されてねーからcontainsKey()使え
foreach ((int k, int v) in dict)
{
    Console.WriteLine($"(k,v)==({k},{v})");
}
//(k,v)==(0,2)
//(k,v)==(1,2)
//(k,v)==(2,3)

// Dictionary<k,v>はこう使うのだ
Dictionary<int,int> dict = new()
{
    [0] = 1,
    [1] = 2,
    [2] = 3
};

dict[0]++;    // ブラケット記法を使ったインクリメントは可能
//dict[3]++ 実行時例外、初期化されてねーからcontainsKey()使え
foreach ((int k, int v) in dict)
{
    Console.WriteLine($"(k,v)==({k},{v})");
}
//(k,v)==(0,2)
//(k,v)==(1,2)
//(k,v)==(2,3)

ループ内にdict[hoge]を置くのであればどこかしらにcontainsKey()を挟む必要がある。これでも定数的に増えるだけなのでO(n²)とかにはならないはず。手を動かすのがめんどいだけ。

筆者のアプローチではj-A[j]が負数になると配列ではアクセスできずIndexOutOfRangeExceptionが発生する。mapの場合はインデックスによるアクセスではなく、負数のキーを自動的に作ってくれるので、細かく気にしなくても良い。

この問題の場合、制約的にはAの数列は非負整数なので、i+A[i]もまた非負であり、j-A[j]が負数となるjは無視してよいケースになる。なので普通の配列型を利用できる。この問題ではDictionaryは使わなかったけど、必要なやつもあるんだろうしその場合の実装も課題か。

制約上の通り数は約199億なので答えが2³¹（約21億）を超える可能性がある。
算術オーバーフローはデフォルトのC#では例外としてチェックされないため、REではなくWAになる。

とにかくlongだ！　long使っておけば間違いない。解法が合ってるはずなのにWAになる場合は大抵オーバーフローが起こっている。（3敗）

以上。

移項を忘れた人向け。

AIに解説してもらう方が早いかも。筆者は競プロ久しぶり過ぎて忘れた。灰なのに、いや灰だからか

j-i=A[i]+A[j]　　を移項して分かりやすくする。

↓

j-i-A[j]=A[i]　　右辺の+A[j]を+と-同士で反転して左辺に送る。

↓

j-A[j]=i+A[i]　　左辺の-iも反対して右辺に送る。

移項完了。

追加で解説しておくと+⇔-、*⇔/で反転して=を挟んだ反対側に送るというのは、両辺に同じ操作をすることの言い換え。

j-i=A[i]+A[j]

↓

j-i-A[j]=A[i]+A[j]-A[j]

↓

j-i-A[j]=A[i]

小学生からやってきたように記号は数の左側に付くので、この次は-iを左辺に送りたいね。というような感じ。