![D - 問題概要
問題
N個の町が一直線上に並んでおり、町iと町jの距離(i<j)はa[i]+a[i+1]+...
+a[j-1]である。それぞれの町には砂糖屋が１つずつある。ちょうどK個の
異なる砂糖屋に一度ずつ訪れる方法のうち移動距離の和がMの倍数である
ものは何通りか。
制限
N 100, M 30, K 10
部分点(30点)：N 12](https://image.slidesharecdn.com/arc020-140329083039-phpapp01/85/AtCoder-Regular-Contest-020-18-320.jpg)
![D - 部分点解法
巡回セールスマン問題にとても似ている。
? DP[今までに訪れた町の集合][今いる町][移動距離の和 mod M]
というDPテーブルを更新して行けば良い。
「今までに訪れた町の集合」は二進数で表現すると処理しやすい。
状態数：2^N * N * M
遷移数：O(N)
計算量：O(2^N * N^2 * M)](https://image.slidesharecdn.com/arc020-140329083039-phpapp01/85/AtCoder-Regular-Contest-020-19-320.jpg)
![DP[今注目している道][さっきのような二進数][移動距離の和 mod M]
というDPを考える。
「さっきのような二進数」は
?iビット目が1のとき、i番目に訪れる町が注目している道の左にある
?iビット目が0のとき、i番目に訪れる町が注目している道の右にある
ということを表している。
DPの遷移で行うことは、
?今見ている道の左の端点の町にi番目に訪れることにする(i = 1 k)
?なにもしない
の２通りである。
D - DP](https://image.slidesharecdn.com/arc020-140329083039-phpapp01/85/AtCoder-Regular-Contest-020-22-320.jpg)
AtCoder Regular Contest 020 解説
- 1. AtCoder Regular Contest 020 解説 AtCoder株式会社 2014/3/29 1
- 3. A - 問題概要 問題 整数が２つ与えられる。 どちらがより0に近いかを判定せよ。 制限 -1000 (与えられる整数) 1000
- 4. A - 解き方 1. ２つの整数を入力する。 2. それぞれの整数について絶対値を求める。 3. それらを比較して適切に条件分岐をする。 4. 結果に対応する文字列を出力する。
- 5. A - 絶対値の求め方 (方法１) 言語が用意している関数を使う。 ???? →?使っている言語について調べてみよう。 (方法２) 条件分岐を使って自分で書く。 ????例： if (A < 0) A = -A;
- 8. B問題解法 解法 ? 1番目と2番目に使う数字を決め打ちすれば目標の数列は一意に 定まる →そうしてできた数列と与えられる数列の不一致数を数える ? たとえば数列={2,3,2,1}のとき、 1番目の数字=「2」と2番目の数字=「1」とすると、 目標の数列={2,1,2,1} → この場合の不一致数は1 ? それらを全て計算した上で最小値を出力
- 9. Problem C A mod B Problem
- 10. C問題概要 問題 ? 部分的に周期性のある整数A ( 一兆桁以上 ) ←周期の数は1万以下 ? 整数B(ほとんどの場合 10^9+7) が与えられるので、AをBで割った余りを出力せよ Aの与えられ方の例: 123が2回 4が2回 56が1回繰り返された整数A→1231234456
- 11. C問題 部分点解法(20点) ? L1+L2+….+LN ≦ 10^5 ? Aiの桁数は10以下 ? 展開してもAの長さは10^6以下 したがって、実際に与えられる数を展開し、うまく mod を取ればよい。 (次スライド) ? 計算量は、桁数をNとしてO(N)
- 12. うまいmodの取り方 ある整数を読み込むときに、上の桁から今の整数を10倍して1桁 読み込むことを繰り返すと、逐次modが取れてオーバーフローしない。 動作例: 4321 % 11を求めるとき 4321 余り: 4 4321 余り: (4*10+3)%11 = 10 4321 余り: (10*10+2)%11 = 3 4321 余り: (3*10+1)%11 = 9 よって、4321を11で割った余りは9
- 13. C問題 ほぼ満点解法(99点) ? 各周期毎に高速に余りを計算する ? 「10^(周期の長さ)倍して周期の余りを足す」を繰り返せばよい ? 繰り返された数は等比数列の和で表されることに着目する↓ 121212 ?回 … = 12 + 12 × 100 + 12 × 1002 + … + 12 × 100 ??1 一般に公比r(r≠1,r≠0)のとき、 ?0 + ?1 + ?2 + ? + rn = rn+1 ? 1 r ? 1 したがって 12 1 + 100 + ? + 100n?1 = 12 × 100n ? 1 100 ? 1 の余りを計算すればよい
- 14. C問題 ほぼ満点解法(99点) ? 1/xをする操作が問題(ふつうに割ってmodを取るのはNG) →1/xと等価な整数(掛けてmodを取ったら1になる数=逆元)を求め、そ れを掛け算すればよい ? フェルマーの小定理に基づくと、 pが素数であり、xとpが互いに素であれば、x^(p-2)はxの逆元 ? 10^9+7は素数 ? 今回、xは9,99,999,….,10^10-1の値しかとらない →xとp=10^9+7は常に互いに素 ? 逆元は二分累乗法によって、log(p)で計算可能
- 15. C問題 満点解法(100点) ? Bの値によっては逆元が求まらないことがある ? ダブリング ? 例えば123123123…を求めるとき 123(1回) 123123(2回) 123123123123(4回) 123123123123123123123123(8回) … のように123が2^k回繰り返されたパーツがあれば繋ぎ合せるだけでよい (modは逐次とっておく)
- 16. C問題 満点解法(100点) ? 123が「2^n回繰り返されたもの」から「2^n+1回繰り返されたもの」を作る ? 例えば「123123」から「123123123123」をつくる → 「123123」を1000^2+1倍すればよい ? これはn=1の例だが、他のnでも同様 ? これらのパーツが作れたら、パーツを適当な順番で繋ぎ合せる ? 例えば「123123123123123(5回)」なら、 5=(101)2なので「123」と「123123123123」を繋ぎ合せる ? もともとこれが想定解法でしたが緩和しました
- 17. D問題 お菓子の国の旅行
- 18. D - 問題概要 問題 N個の町が一直線上に並んでおり、町iと町jの距離(i<j)はa[i]+a[i+1]+... +a[j-1]である。それぞれの町には砂糖屋が１つずつある。ちょうどK個の 異なる砂糖屋に一度ずつ訪れる方法のうち移動距離の和がMの倍数である ものは何通りか。 制限 N 100, M 30, K 10 部分点(30点)：N 12
- 19. D - 部分点解法 巡回セールスマン問題にとても似ている。 ? DP[今までに訪れた町の集合][今いる町][移動距離の和 mod M] というDPテーブルを更新して行けば良い。 「今までに訪れた町の集合」は二進数で表現すると処理しやすい。 状態数：2^N * N * M 遷移数：O(N) 計算量：O(2^N * N^2 * M)
- 20. 各道ごとに独立に計算したい。 → 各道に関して、通る回数はどうなっているだろうか？ D - 満点解法 1 2 3 4 5 6 7 ４回通る 2 4 3 7 5 1の順で辿ったとき
- 21. 町3と町4の間にある道を通るのは、 「2 → 4」「4 → 3」「3 → 7」「5 → 1」の移動をするとき。 つまり「３以下から４以上」または「４以上から３以下」に移動するとき。 ここで、「３以下」を1、「４以上」を0と表してみると、 1 0 1 0 0 1 となる。 この二進数において「隣り合うbitが異なる場所の個数」が「道を通る回数」 となっており、この情報さえあれば事足りることが分かる。 D - 考察 1 2 3 4 5 6 7 ４回通る 2 4 3 7 5 1の順で辿ったとき
- 22. DP[今注目している道][さっきのような二進数][移動距離の和 mod M] というDPを考える。 「さっきのような二進数」は ?iビット目が1のとき、i番目に訪れる町が注目している道の左にある ?iビット目が0のとき、i番目に訪れる町が注目している道の右にある ということを表している。 DPの遷移で行うことは、 ?今見ている道の左の端点の町にi番目に訪れることにする(i = 1 k) ?なにもしない の２通りである。 D - DP
- 23. 状態数：N * 2^K * M 遷移数：O(K) 計算量：O(N * 2^K * M * K) D - DP