![部分点（50点）N 100, Ai 100
? DP[i][j] = i番目の数字がjである場合の数
? というDPをします。
? 直前の数字が今の数字以下であればいいので、漸化
式は以下のようになります。
? DP[i+1][j] = sum(DP[i][0] DP[i][j])
? Aiが-1でないときは、DP[i][Ai]だけを残して、それ
以外を全て0にします。](https://image.slidesharecdn.com/arc023-140517083014-phpapp01/85/AtCoder-Regular-Contest-023-15-320.jpg)
![DPの高速化
? 先ほどのDPの遷移の式は、
? DP[i+1][j] = sum(DP[i][0] DP[i][j])
? でした。
? 区間の和を高速に求められれば良さそうです。](https://image.slidesharecdn.com/arc023-140517083014-phpapp01/85/AtCoder-Regular-Contest-023-18-320.jpg)
![? 累積和を使いましょう。
? sum[i] = 0 iまでの和
? というものを全てのiに関してあらかじめ求めておく
ことで、l rの区間の和を「sum[r]-sum[l-1]」とい
うようにしてO(1)で求めることが出来ます。
? 今回の問題では左端が常に0なので、sum[i]がその
まま求めたいものになっています。
部分点（80点）N 2000, Ai 2000](https://image.slidesharecdn.com/arc023-140517083014-phpapp01/85/AtCoder-Regular-Contest-023-19-320.jpg)
![問題概要
? 数列A={a1,a2,…,an}がある (n≦10万)
? クエリが与えられる。クエリの内容は、
「xが与えられるから、GCD(As,As+1,…,At)=xとなる区間[s,t]
の数を求める」
? クエリはたくさん与えられる(≦10万回)](https://image.slidesharecdn.com/arc023-140517083014-phpapp01/85/AtCoder-Regular-Contest-023-33-320.jpg)
![考察
? 区間を決めることを考える
tを固定してsをt→1と動かすとき、[s,t]のGCDは単調減少
? 単調減少の仕方は、因数が1つずつ除かれる感じ
? 10^9以下で、因数が一番多いのは2^29で29個
? tを固定してsをt→1と動かす方法において、現れるGCDの数
はlog(At)以下](https://image.slidesharecdn.com/arc023-140517083014-phpapp01/85/AtCoder-Regular-Contest-023-34-320.jpg)
![解法
? クエリを考えず、全てのGCDとそれを含む区間数を予め計算する
? 左から順番にtを決めていく。今まで現れたGCDの値とその出現回
数を保持した配列をMとすると、考察からMの大きさは常に30個
(GCD=1を含める)以下
? Mを利用して[?,t]をまとめて計算して答え用の配列に格納しとく
? 後処理として、Mの各要素に対してtとのGCDを取り、配列M’を
計算し、M=M’として処理を続けていく
? Mと答えの保持に平衡二分木の連想配列を用いると、
O(N log max(Ai) log N + |X| log N)](https://image.slidesharecdn.com/arc023-140517083014-phpapp01/85/AtCoder-Regular-Contest-023-35-320.jpg)
AtCoder Regular Contest 023 解説
- 1. AtCoder Regular Contest 023 解説 AtCoder株式会社 2014/5/17 1
- 2. A問題 経過日数
- 4. 解法 ? 適当な日付からある日付までの経過日数を計算できれば、 それらの引き算で任意の2つの日付間の経過日数が計算できる ? したがって、それを計算する ? ? はxが正なら、小数点切捨てと等価なことに注意 (intにキャストするなり何なりで実現できる)
- 5. B問題 謎の人物X
- 6. 問題概要 ? R Cのマス目の左上のマスから、ちょうどD回「隣 のマスに移動」することで行けるマスに書いてある 数字のうち、最も大きいものを求めよ。 ? 部分点（60点）：R,C 100, D 200 ? 満点：R,C 1000, D 2000
- 7. 部分点（60点）R,C 100, D 200 ? 「i 回移動した時に行けるマス」をシミュレーショ ンしてみる。 ? 「i 回移動した時に行けるマス」は、「i-1 回移動し た時に行けるマス」が隣にあるようなマス。
- 8. シミュレーション o 0回移動 o o 1回移動 o o o o 2回移動 o o o o o 3回移動 o o o o o o 4回移動 o o o o o o 5回移動
- 9. 部分点（60点）R,C 100, D 200 ? あとは、「D回移動した時に行けるマス」のうち、 書いてある数字が最大のものを求めれば良い。 ? 計算量はO(マスの個数 D)くらいなので、この部分 点では時間内に答えを求めることが出来ます。
- 10. 満点 R,C 1000, D 2000 ? 「D回移動した時に行けるマス」について考察して みる。 ? マス(i,j)に行くことが出来る条件は、 ?i+j D (遠すぎると行けない) ?i+jとDの偶奇が一致している ? の２つとなっています。 ? ２つめの条件について少し説明します。 o o o o o 3回移動
- 11. ? 図のようにマスを市松模様に塗ってみます。 ? 一回の移動では、 ?白いマスからは黒いマスにしか ?黒いマスからは白いマスにしか 移動することが出来ません。 ? この構造から、偶奇性が生み出されていて、先ほどの ような条件が成り立ちます。 i+jとDの偶奇について o o o o o
- 12. 満点 R,C 1000, D 2000 ? 各マスについて条件をチェックし、条件を満たすマ スのうち、書かれている数字が最大であるものを求 めれば良い。 ? 計算量はO(マスの個数)くらいなので満点を取るこ とが出来ます。
- 13. C問題 タコヤ木
- 14. 問題概要 ? (広義)単調増加な数列の一部が与えられるので、元 の数列としてありうるものは何通りか求めよ。 ? 部分点（50点）：N 100, Ai 100 ? 部分点（80点）：N 2000, Ai 2000 ? 満点：N 2000, Ai 10^9
- 15. 部分点（50点）N 100, Ai 100 ? DP[i][j] = i番目の数字がjである場合の数 ? というDPをします。 ? 直前の数字が今の数字以下であればいいので、漸化 式は以下のようになります。 ? DP[i+1][j] = sum(DP[i][0] DP[i][j]) ? Aiが-1でないときは、DP[i][Ai]だけを残して、それ 以外を全て0にします。
- 16. 部分点（50点）N 100, Ai 100 ? 状態数：O(N max(Ai)) ? 遷移数：O(max(Ai)) ? 計算量：O(N max(Ai)^2) ? となり、この部分点を取ることが出来ます。
- 17. 部分点（80点）N 2000, Ai 2000 ? ２通りの方針があります。 ? まずは先ほどのDPを高速化する方針から。。
- 18. DPの高速化 ? 先ほどのDPの遷移の式は、 ? DP[i+1][j] = sum(DP[i][0] DP[i][j]) ? でした。 ? 区間の和を高速に求められれば良さそうです。
- 19. ? 累積和を使いましょう。 ? sum[i] = 0 iまでの和 ? というものを全てのiに関してあらかじめ求めておく ことで、l rの区間の和を「sum[r]-sum[l-1]」とい うようにしてO(1)で求めることが出来ます。 ? 今回の問題では左端が常に0なので、sum[i]がその まま求めたいものになっています。 部分点（80点）N 2000, Ai 2000
- 20. ? 状態数：O(N max(Ai)) ? 遷移数：O(1) ? 計算量：O(N max(Ai)) ? となり、この部分点を取ることが出来ます。 部分点（80点）N 2000, Ai 2000
- 21. ? その２の解法です。 ? 少し数学的な考察をします。 ? -1が連続している部分ごとに分けると、それぞれを 独立に計算しても良くなります。 ? 例えば「2 -1 -1 9 -1 9」なら「2 -1 -1 9」と 「9 -1 9」に分けて考えます。 部分点（80点）N 2000, Ai 2000
- 22. ? X,(-1がY個並ぶ),Z ? となっている部分を計算する方法を考えます。 ? 各項間での増加量に注目します。 ? 項の間はY+1箇所あり、それらに合計Z-Xの非負の 整数を割り振っていると言い換えることが出来ま す。 ? もう少し簡潔に言い換えると??? 部分点（80点）N 2000, Ai 2000
- 23. ? 長さLの非負整数からなる数列であって、 合計がSとなるものの個数 ? を求めることが出来れば良いです。 ? 「1 -1 3」を例にして言い換えると、 ? 「長さ2で合計が2の数列」の個数を求める問題 ? （答えは「0 2」「1 1」「2 0」の３通り） 部分点（80点）N 2000, Ai 2000
- 24. ? 長さLの非負整数からなる数列であって、 合計がSとなるものの個数 ? →数学とかでよくある、重複組み合わせの問題 ? 「S個の o とL-1個の ? を並べる方法の個数」と同じ ? LHS = S+L-1CS 部分点（80点）N 2000, Ai 2000
- 25. ? ここまでくれば、あとは組み合わせを計算できれば 良い。 ? パスカルの三角形を作ろう。 ? i段目のj番目の数字が iCj になっています。 部分点（80点）N 2000, Ai 2000 1 11 121 1331 14641 パスカルの三角形
- 26. ? まとめると、 ? X -1 -1 ... -1 Y という部分に分割する ? それぞれの部分に対し、重複組み合わせを求める ? 重複組み合わせをパスカルの三角形を用いて求める ? パスカルの三角形を構成するところに最も時間がか かり、O(max(Ai)^2)くらいなので、この部分点を 得ることが出来ます。 部分点（80点）N 2000, Ai 2000
- 27. 満点 N 2000, Ai 10^9 ? 組み合わせを高速に求めたい。 ? 組み合わせは、以下のように求められます。 ? nCr = (n-r+1 nの積)/(1 rの積) ? これをどのように計算すれば良いでしょうか。
- 28. 満点 N 2000, Ai 10^9 ? nCr = (n-r+1 nの積)/(1 rの積) ? (n-r+1 nの積)と(1 rの積)は素直にかけ算をすれば 良いだけです。 ? しかし、割り算はそうは行きません。 ? X/Y (mod p) (pは素数) の求め方が問題です。
- 29. X/Y (mod p) (pは素数) の求め方 ? mod pのpが素数の場合は、逆元が存在します。 ? 「Yの逆元」とは「Yをかけると1になる数」のこと で、「1/Y」や「Y^-1」などと表します。 ? フェルマーの定理「X^(p-1) 1 (mod p)」を用い ると、Yの逆元は「Y^p-2」として計算することが 出来ます。（(Y^(p-2)) * Y 1 (mod p)なので） ? つまり、X/Y X*(Y^(p-2)) と計算できます。
- 30. X/Y (mod p) (pは素数) の求め方 ? あとは、Y^(p-2)を高速に計算できれば解決です。 ? 冪乗法を用います。(繰り返し二乗法とも) ? A^B = A^(B/2)*A^(B%2) という漸化式を使ってべ き乗を計算する手法です。 ? 肩に乗っている数字が半分ずつに減っていくので、 計算量はO(log p)となります。 ? 再帰関数として実装すると良いでしょう。
- 31. 満点 N 2000, Ai 10^9 ? 80点の２つめの部分点解法を、mod pでの割り算 をO(log p)くらいで計算するテクニックを用いて高 速化することによって、満点を得られるようになり ました！
- 32. D問題 GCD区間
- 33. 問題概要 ? 数列A={a1,a2,…,an}がある (n≦10万) ? クエリが与えられる。クエリの内容は、 「xが与えられるから、GCD(As,As+1,…,At)=xとなる区間[s,t] の数を求める」 ? クエリはたくさん与えられる(≦10万回)
- 34. 考察 ? 区間を決めることを考える tを固定してsをt→1と動かすとき、[s,t]のGCDは単調減少 ? 単調減少の仕方は、因数が1つずつ除かれる感じ ? 10^9以下で、因数が一番多いのは2^29で29個 ? tを固定してsをt→1と動かす方法において、現れるGCDの数 はlog(At)以下
- 35. 解法 ? クエリを考えず、全てのGCDとそれを含む区間数を予め計算する ? 左から順番にtを決めていく。今まで現れたGCDの値とその出現回 数を保持した配列をMとすると、考察からMの大きさは常に30個 (GCD=1を含める)以下 ? Mを利用して[?,t]をまとめて計算して答え用の配列に格納しとく ? 後処理として、Mの各要素に対してtとのGCDを取り、配列M’を 計算し、M=M’として処理を続けていく ? Mと答えの保持に平衡二分木の連想配列を用いると、 O(N log max(Ai) log N + |X| log N)
- 36. 他の解法 ? 区間のGCDを予め高速に計算できるようにしておく (*) ? 今度はsを固定してtを伸ばすことを考える ? GCDは単調減少かつ、変化はO(logAs)回 ? 変化点見つけるのまで二分探索するとうれしくない ? 1個の変化点を見つけるためにO(log N)回反復 ? O( N log max(Ai) log N×{(*)の方法の計算量} ) ←とても重い ? (*)の部分にセグメントツリーを用いるとおそらくTLE ? 二分探索ではなく、平方分割を用いて、「進めてみて変化がないな ら√Nずつtを進めていく」方法も間に合うはず ? その他、スパーステーブルを用いて平方分割と同様できるだけ大き な2^k(1,2,4,…)ずつ進めていく方法もある