狠狠撸

狠狠撸Share a Scribd company logo

天下一プログラマーコンテスト2015 予選B 解説

?
?
A
AtCoder Inc.

天下一プログラマーコンテスト2015 予選B 解説

1 of 11
Download to read offline
天下一プログラマーコンテスト2015 予選B E問題 解説 2015/8/22 1
?AtCoder Inc. All rights reserved. 2 E問題 天下一演算 1. 問題概要 2. アルゴリズム 2015/8/22 2
E問題 問題概要 ? N個の整数が与えられる ? すべての整数に10を掛ける操作を何回か行う ? それぞれの整数に1を足す操作を何回か行う ? すべての整数をMの倍数にするのに必要な最小の 操作の回数を求めよ ? 制約 1 ≦ N ≦ 105, 1 ≦ M ≦ 105 2015/8/22 3
E問題 アルゴリズム ? 整数xにi回10を掛けた後、何回1を足せばMの倍数 になるかをFi(x)と表すことにする ? N=1の場合を考える – M = 7, A = [1]の場合 – F0(1)=6, F1(1)=4, F2(1)=5, F3(1)=1, F4(1)=3, F5(1)=2, F6(1)=6 – Fi+1(x) = Fi(x)×10 % M – 周期性？ 2015/8/22 4
E問題 アルゴリズム ? iが小さいところで周期的にならない例 – M = 12, A = [1]の場合 – F0(1)=11, F1(1)=2, F2(1)=8, F3(1)=8, … ? どの程度で周期に入るか？ – gcd(a×10i, M) = gcd(a×10i+1, M)なら、それ以降は周期的 に変化する – O(log M) – この問題の制約では16回10を掛ければ良い – 最初に周期に入るまで愚直に計算しておく 2015/8/22 5
E問題 アルゴリズム ? 周期の長さ – 周期の長さはφ(M)を割り切る – φ：オイラーのφ関数 – １～Nの整数でNと互いに素なものの個数をφ(N)と書く ? Mと10が互いに素の場合 – オイラーの定理より、10φ(M) ≡ 1 (mod M) – したがってAi×10φ(M) ≡ Ai (mod M) 2015/8/22 6
E問題 アルゴリズム ? Mと10が互いに素でない場合 – gcd(a×10i, M) = gcd(a×10i+1, M)となる最小のiをK、このと きのgcdをGとすると、10φ(M/G) ≡ 1 (mod M/G) – 両辺に10K/Gを掛けて整理すると10K+φ(M/G) ≡ 10K (mod M) – GとM/Gは互いに素なのでφ(G)φ(M/G) = φ(M) – したがって10K+φ(M) ≡ 10K(10φ(M/G))φ(G) ≡ 10K (mod M) – よってAi×10K+φ(M) ≡ Ai ×10K (mod M) ? 以下ではAi×10φ(M) ≡ Ai (mod M)となるとして考える – 最初に16回以上10を掛ければ良い – Ai×10Kを新たなAiと見なす 2015/8/22 7
E問題 アルゴリズム ? N≧1の場合を考える – 周期ごとに分けると高速に計算できる – 周期の長さをLとして、X’i,j = Fi(10j×α)と、各10j×αに対応 するAの要素の数Yjを考える – Si = Σj X’i,jYj (i,j：0～L-1)を求めたい – ここでXj = X’0,jとして、X’i+1,j = X’i,j+1であることを利用すると、 Si = Σj Xj+iYjと書ける – これは多項式乗算に帰着されて、FFT (O(L log L))や、 Karatsuba法 (O(Llog23)≒O(L1.585))で解ける 2015/8/22 8
E問題 アルゴリズム ? 入力例１ – X = {6,4,5,1,3,2}, Y = {1,1,1,0,0,0} – f(x) = 6+4x+5x2+x3+3x4+2x5, g(x) = x5+x4+x3 とする – f(x)g(x) = 6x3+10x4+15x5+10x6+9x7+6x8+5x9+2x10 – f(x)g(x)のxiの項の係数をh(i)とすると Si = h(i-1)+h(i+L-1)に なっている 2015/8/22 9
E問題 アルゴリズム ? 全ての周期を足し合わせる – 周期の長さごとに足しておく – それぞれをφ(M)まで足し合わせる – 計算量はO(M√M)だが実際には十分高速で、多項式乗算 がボトルネックとなる ? これで10を掛ける回数を決めたときに、何回1を足 す必要があるか分かるようになった – 10を掛ける回数はφ(M) + log M以下でよい 2015/8/22 10
E問題 アルゴリズム ? まとめ – 周期に入るまで愚直に10を掛ける O(N log M) – 多項式乗算に帰着させてFFTやKaratsuba法で計算する O(M log M) or O(Mlog23) – 全ての周期を足し合わせる O(M√M) – 10を掛けた回数ごとに何回1を足すか調べる O(M) 2015/8/22 11

More Related Content

天下一プログラマーコンテスト2015 予選B 解説

  • 2. ?AtCoder Inc. All rights reserved. 2 E問題 天下一演算 1. 問題概要 2. アルゴリズム 2015/8/22 2
  • 3. E問題 問題概要 ? N個の整数が与えられる ? すべての整数に10を掛ける操作を何回か行う ? それぞれの整数に1を足す操作を何回か行う ? すべての整数をMの倍数にするのに必要な最小の 操作の回数を求めよ ? 制約 1 ≦ N ≦ 105, 1 ≦ M ≦ 105 2015/8/22 3
  • 4. E問題 アルゴリズム ? 整数xにi回10を掛けた後、何回1を足せばMの倍数 になるかをFi(x)と表すことにする ? N=1の場合を考える – M = 7, A = [1]の場合 – F0(1)=6, F1(1)=4, F2(1)=5, F3(1)=1, F4(1)=3, F5(1)=2, F6(1)=6 – Fi+1(x) = Fi(x)×10 % M – 周期性？ 2015/8/22 4
  • 5. E問題 アルゴリズム ? iが小さいところで周期的にならない例 – M = 12, A = [1]の場合 – F0(1)=11, F1(1)=2, F2(1)=8, F3(1)=8, … ? どの程度で周期に入るか？ – gcd(a×10i, M) = gcd(a×10i+1, M)なら、それ以降は周期的 に変化する – O(log M) – この問題の制約では16回10を掛ければ良い – 最初に周期に入るまで愚直に計算しておく 2015/8/22 5
  • 6. E問題 アルゴリズム ? 周期の長さ – 周期の長さはφ(M)を割り切る – φ：オイラーのφ関数 – １～Nの整数でNと互いに素なものの個数をφ(N)と書く ? Mと10が互いに素の場合 – オイラーの定理より、10φ(M) ≡ 1 (mod M) – したがってAi×10φ(M) ≡ Ai (mod M) 2015/8/22 6
  • 7. E問題 アルゴリズム ? Mと10が互いに素でない場合 – gcd(a×10i, M) = gcd(a×10i+1, M)となる最小のiをK、このと きのgcdをGとすると、10φ(M/G) ≡ 1 (mod M/G) – 両辺に10K/Gを掛けて整理すると10K+φ(M/G) ≡ 10K (mod M) – GとM/Gは互いに素なのでφ(G)φ(M/G) = φ(M) – したがって10K+φ(M) ≡ 10K(10φ(M/G))φ(G) ≡ 10K (mod M) – よってAi×10K+φ(M) ≡ Ai ×10K (mod M) ? 以下ではAi×10φ(M) ≡ Ai (mod M)となるとして考える – 最初に16回以上10を掛ければ良い – Ai×10Kを新たなAiと見なす 2015/8/22 7
  • 8. E問題 アルゴリズム ? N≧1の場合を考える – 周期ごとに分けると高速に計算できる – 周期の長さをLとして、X’i,j = Fi(10j×α)と、各10j×αに対応 するAの要素の数Yjを考える – Si = Σj X’i,jYj (i,j：0～L-1)を求めたい – ここでXj = X’0,jとして、X’i+1,j = X’i,j+1であることを利用すると、 Si = Σj Xj+iYjと書ける – これは多項式乗算に帰着されて、FFT (O(L log L))や、 Karatsuba法 (O(Llog23)≒O(L1.585))で解ける 2015/8/22 8
  • 9. E問題 アルゴリズム ? 入力例１ – X = {6,4,5,1,3,2}, Y = {1,1,1,0,0,0} – f(x) = 6+4x+5x2+x3+3x4+2x5, g(x) = x5+x4+x3 とする – f(x)g(x) = 6x3+10x4+15x5+10x6+9x7+6x8+5x9+2x10 – f(x)g(x)のxiの項の係数をh(i)とすると Si = h(i-1)+h(i+L-1)に なっている 2015/8/22 9
  • 10. E問題 アルゴリズム ? 全ての周期を足し合わせる – 周期の長さごとに足しておく – それぞれをφ(M)まで足し合わせる – 計算量はO(M√M)だが実際には十分高速で、多項式乗算 がボトルネックとなる ? これで10を掛ける回数を決めたときに、何回1を足 す必要があるか分かるようになった – 10を掛ける回数はφ(M) + log M以下でよい 2015/8/22 10
  • 11. E問題 アルゴリズム ? まとめ – 周期に入るまで愚直に10を掛ける O(N log M) – 多項式乗算に帰着させてFFTやKaratsuba法で計算する O(M log M) or O(Mlog23) – 全ての周期を足し合わせる O(M√M) – 10を掛けた回数ごとに何回1を足すか調べる O(M) 2015/8/22 11