FreeStyleWiki

AtCoder Beginer Contest 200

このエントリーをはてなブックマークに追加

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 200 - C

  解説

解説の解説

  • わからんのではまやんさんのブログを見てみた

とりあえず、記載の通り

\( 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