【ABC367】D - Pedometer のイメージベース解説

目的

AtCoder公式の解説を見てもテキストベースでの説明で解き方の理屈がわからなかったが、Xでポストされた画像を見て解き方の理屈がわかったので、復習用にイメージベースで解説

問題

https://atcoder.jp/contests/abc367/tasks/abc367_d
各休憩所を時計回りでMの倍数となる歩数の組み合わせの数を求める

入力例1(M=3)の答えは、

• 休憩所1から休憩所3までの3歩(2+1)
• 休憩所3から休憩所2までの9歩(4+3+2)
• 休憩所4から休憩所1までの3歩(3)
• 休憩所4から休憩所3までの6歩(3+2+1)

の4通り

解き方

1. 2周分(N*2)の累積和からMで割った余りを求める(moddedSums)
   
   ※余りが同じ区間の合計は余りに変化がないので倍数であることが確定
2. 1週分(N)の余りの出現回数を求める(moddedCounts)
   
3. 1週分(N)の検索対象を1ずつズラしてMで割った余りの出現回数を加算
   3-1. moddedSumsのi=0のmod Mの値(0)をmoddedCountsのcountから1減算(自身を組み合わせの検索対象から除外)
   
   3-2. 上記1減算後の値がMの倍数の組み合わせの数となるので、最終出力変数に加算(combinationCount)
   
   3-3. moddedSumsのi=4のmod Mの値(1)をmoddedCountsのcountに1加算(1周先を組み合わせの検索対象に追加)
   
   3-4. moddedSumsのi=1のmod Mの値(2)をmoddedCountsのcountから1減算(自身を組み合わせの検索対象から除外)
   
   3-5. 上記1減算後の値を最終出力変数に加算するが、0なので組み合わせは見つからなかった
   3-6. moddedSumsのi=5のmod Mの値(0)をmoddedCountsのcountに1加算(1周先を組み合わせの検索対象に追加)
   
   3-7. moddedSumsのi=2のmod Mの値(0)をmoddedCountsのcountから1減算(自身を組み合わせの検索対象から除外)
   
   3-8. 上記1減算後の値がMの倍数の組み合わせの数となるので、最終出力変数に加算(combinationCount)
   
   3-9. moddedSumsのi=6のmod Mの値(1)をmoddedCountsのcountに1加算(1周先を組み合わせの検索対象に追加)
   
   3-10. moddedSumsのi=3のmod Mの値(1)をmoddedCountsのcountから1減算(自身を組み合わせの検索対象から除外)
   
   3-11. 上記1減算後の値がMの倍数の組み合わせの数となるので、最終出力変数に加算(combinationCount)
   
   3-12. moddedSumsのi=7のmod Mの値(2)をmoddedCountsのcountに1加算(1周先を組み合わせの検索対象に追加)
   
   3-13. 1周分(N)検索したので、終了
4. 答えは4通り
   

コード

N, M = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

# 2周分(N*2)の累積和からMで割った余りを求める
moddedSums = [0]
N.times{|i| moddedSums << (moddedSums[-1] + A[i]) % M}
N.times{|i| moddedSums << (moddedSums[-1] + A[i]) % M}

# 1週分(N)の余りの出現回数を求める
moddedCounts = Array.new(M, 0)
N.times{|i| moddedCounts[moddedSums[i]] += 1}

# 1週分(N)の検索対象を1ずつズラしてMで割った余りの出現回数を加算
combinationCount = 0
N.times{|i|
  # 自身を組み合わせの検索対象から除外
  moddedCounts[moddedSums[i]] -= 1

  # 1減算後の組み合わせの数を最終出力変数に加算
  combinationCount += moddedCounts[moddedSums[i]]

  # 1周先を組み合わせの検索対象に追加
  moddedCounts[moddedSums[i + N]] += 1
}
puts combinationCount