AtCoder Beginer Contest 200 - C
- AtCoder Beginer Contest 200 - C - Ringo's Favorite Numbers 2
- N個の数列Aが与えられる、N=10^10
- 数列Aから任意のi, j番目を選んだ際に、A[i]-A[j] % 200 == 0になるものの個数を求める
解説
解説の解説
- わからんのではまやんさんのブログを見てみた
- 結局解説を見て理解するまで１時間ぐらいかかった
- Ringo's Favorite Numbers 2
とりあえず、記載の通り
\( A[i]-A[j] \mod 200 = 0 \)
は以下のように変形できるっぽい（まずそこが思いつかないのだが）。
\( A[i] \mod 200 = A[j] \mod 200 \)
それを愚直に実装すると以下のようになるが、Nが大きいしO(N^2)になるのでTLEする（クソ）
愚直版
| + | 提出 #22671299 | |
賢い版
- そこで、解説の通りA[n] % 200の余りを格納する配列cntを用意する
- どんな数を割っても余りは200以下になるので、サイズは適当でいい
- A[n]をそれぞれ200で割って、cnt[]に格納する
cnt = Array.new(202, 0)
\( A[i] \mod 200 = A[j] \mod 200 \)
- そうするとcntのテーブル上で上記の式を満たすもののを数えれば答えになる
- 要は、余りが123であれば他に余り123のものがあれば、それが集計対象となるわけ
- この集計のループもうまいことできていて、最初に余り123が出た時点ではcnt[]のテーブルには何もないのでansは加算されない（cnt[123]==0）
- 2番めの123が見つかった時、すでに1つ123がcntに入っているのでans=ans+1 (ans=1)
- 3番めの123が見つかった時、すでに2つ123がcntに入っているのでans=ans+2 (ans=3)
- まるで、集計対象が見つかったら後戻ってパターンを数え上げるような動きをしている
これにより二重ループしなくとも左から右に処理を回すだけで数え上げが可能になる。頭のいい方法だ。
- コードは以下の通り
| + | 提出 #22673085 | |
abc-200-c.jpg