![満点解法に向けて
? segment-tree が管理している区間全体に数
字が増減された場合、増減の前後で GCD が
変わることがある。
? 例: 区間が [36,43,1,71] を管理している時に、
区間全体が 7 増えると GCD(42,49,7,77)=7 と
なって 1 ではなくなっている。
? 増減クエリに対して不変な要素がないか考え
る。](https://image.slidesharecdn.com/arc017-140212032605-phpapp01/85/AtCoder-Regular-Contest-017-26-320.jpg)
More Related Content
What's hot (20)
Similar to AtCoder Regular Contest 017 (20)
More from AtCoder Inc. (20)
Recently uploaded (10)
AtCoder Regular Contest 017
- 1. AtCoder Regular Contest 017 解説
- 3. A - 問題概要 問題? 整数 N が与えられる。? N が素数かどうかを判定せよ。? ? 制限? 17 ≦ N ≦ 1,000,000
- 4. A - 正解に必要な要素 ? アルゴリズム? ?素数の定義? ?素数の判定法? 1 とその数自身でしか割り切れない 2 以上の正の整数 ※問題文に書かれています N を割り切るような数を探してみて、 実装? それが 1 と N だけなら素数！ ?標準入出力? ?ループ? ?→実装で分からないことがある場合は? ??「標準入出力」などで調べてみよう
- 5. A - 解き方 1. N を標準入力から入力する。 2. 2 から N-1 までのすべての整数について、? N を割り切ることができるかを調べる。? →多くの言語では % 演算子で調べることができる 3. いちども割り切れなければ N は素数 → YES? そうでなければ N は素数ではない → NO? をそれぞれ標準出力に出力する。
- 6. B問題 解像度が低い。
- 7. B - 問題概要 問題? 業績を表す N 要素の整数列 A が与えられる。? そのうちの連続した K 個で、常に上昇しているもの は何個あるか？ 制限? 1 ≦ K ≦ N ≦ 300,000? 1 ≦ Ai ≦ 300,000 (1 ≦ i ≦ N)
- 8. B - 注意点(1/2) K = 1 のとき、「常に上昇している」とは？? →問題文の記述からは、あまり明らかではない…… 直感的には? たとえば (100) は上昇しているようには見えないが…… ありうる解釈(今回正しいのはこっち)? 常に上昇とは 1 ≦ i < (Xの長さ) について Xi < Xi+1 ? と考えれば、(100) も「常に上昇している」ととれる? →そもそも i がとれないから OK
- 9. B - 注意点(2/2) プログラミングコンテストの問題文では、こういった 「数学的な」解釈をすることが多い? （特に今回のように K = 1 などの端っこのケース） 少しでも「あれ？」と題意に疑問を持ったら……? 質問しましょう。積極的に質問すると良いです。? (求めている返答が返ってくればよいですし、仮に「問題文をよく読んでくださ い」なんて返されてしまったとしても損することはありません。ジャッジ側の仕 事が増えるだけですが、そんなことを参加者は気にしなくてもよいので、疑問が あればためらわずにガンガン質問を送りましょう。)
- 10. B - 解き方(1/3) 素直にループを書いて数えると？? ?→もちろん答えは出るけど、時間は大丈夫？ 今回は N が 300,000 まであって、間に合わない！? ?具体的には約 N(N-K) 個ぐらいの要素を見る? ?最大で 200 億を超える個数になる！? ?とてもじゃないけど 2 秒では難しい
- 11. B - 解き方(2/3) 入出力例についていた図を観察してみよう? (N = 10, K = 3) ! ! 最初の 5 要素が常に上昇していて、K = 3 なので? その部分が 3 回分カウントされている！? 後半についても、4 要素の上昇部分が 2 回分カウントされている
- 12. B - 解き方(3/3) 元の A を、常に上昇している列たちに分解する！ 次に、分解したそれぞれの部分について? その部分が K 以上の長さであれば答えにカウント！ 10 40 50 80 90 30 20 40 90 95 10 40 50 80 90 30 20 40 90 95 長さ 5? 長さ 1? 長さ 4? → 3 回分カウント → カウントしない → 2 回分カウント
- 13. C問題 無駄なものが嫌いな人
- 14. C - 問題概要 問題? N 個の荷物と、それぞれの大きさ w が与えられる。? 大きさ X のナップサックに、ぴったり荷物を詰める 方法は何通りあるか？ 制限? 1 ≦ N ≦ 32? 1 ≦ wi ≦ 50,000,000 (1 ≦ i ≦ N)? 1 ≦ X ≦ 1,000,000,000
- 16. C - 制限に注目 今回の制限では ?ナップサックや荷物がとても大きい が、そのかわりに ?荷物の個数(N)がとても小さい（重要） とはいえ、全探索は間に合わない? (232 通りの詰め方はとても时间内に探索しきれない)
- 17. C - 解き方(1/3) N が半分(16ぐらい)なら全探索できるのに……? ? つまり、? 荷物を前半グループと後半グループの半々に分けて、 それぞれのグループ内の組み合わせで作れる大きさな ら全探索ができる！ その後で、ふたつのグループの結果を? うまくまとめられないだろうか？
- 18. C - 解き方(2/3) 前半の荷物を組み合わせて、大きさ p にする方法? が A 通りあるとすると…… 後半の荷物を組み合わせて、大きさ X-p にする方法? が B 通りあったとしたら →ちょうど大きさを X にする方法が? ?A×B 通り見つかったことになる
- 19. C - 解き方(3/3) 前半でつくる大きさ p を全部試すとして? このとき対応する? 「後半で大きさ X-p を作る方法」が何通りあるか? がすぐに分かればよい。 → 後半の全探索の結果を作れる大きさの順にソート しておけば二分探索で大きさ X-p を作る方法が何通り あるか高速に求められる！? これは「半分全列挙」等の名前で言及されることの多いアルゴリズム
- 20. D 問題 解説 城下 慎也 (phidnight)
- 21. 問題概要 ? ? 個の数列が与えられる。 ? 次のクエリを ? 個処理する。 ?連続する区間の数字の GCD を出す。 ?連続する区間の数字を増減させる ※ここでは、GCD は最大公約数のこと ? 30 点分の部分点では増減クエリの幅が1
- 22. 部分点解法 ? 普通に 1 個ずつ区間を取って GCD を計算し ていると間に合わない。 ? 実は、いくつかの数の GCD はどのような順番 で部分の GCD を計算しても必ず同じ最終結 果が返ってくる。 ? あらかじめ広い区間の GCD を知っておけば 効率的に計算できる。 ? segment-tree を用いると効果的。
- 23. 部分点解法(例) ? 例えば下のように区間を決めた場合について 考えてみる。 ? 左から 3 つ目を起点として右に進んだ 5 つの 数 16,32,120,84,54 の GCD を計算してみる。 2 4 6 4 8 16 20 16 12 32 120 18 84 54 36
- 24. 部分点解法(例) ? 矢印で示した 3 つの数 16,12,54 の GCD は元 の 5 つの数の GCD と一致する。 ? GCD(16,32,120,84,54)=GCD(16,12,54)=2 2 4 6 4 8 16 20 16 12 32 120 18 84 54 36
- 25. 部分点解法 ? segment-tree に、その区間に含まれる要素の GCD を保存しておけば、連続する区間の GCD を O(log ?) で計算することができる。 ? 増減クエリは幅 1 なので、この更新によって GCD が更新される場所も O(log ?) →全体で O(? log ?) で計算でき、30 点が得 られる。
- 26. 満点解法に向けて ? segment-tree が管理している区間全体に数 字が増減された場合、増減の前後で GCD が 変わることがある。 ? 例: 区間が [36,43,1,71] を管理している時に、 区間全体が 7 増えると GCD(42,49,7,77)=7 と なって 1 ではなくなっている。 ? 増減クエリに対して不変な要素がないか考え る。
- 27. 満点解法に向けて ? 全体に数が加算されても、それぞれの数の 差は一定である。(36 と 43 の両方に 6 を足し ても差は 7 のままである) ? よって区間内の隣り合う 2 項の差は不変。 ? 実は、区間に含まれる要素のうち、隣り合うも のの差すべてと代表元 1 個の GCD は区間の GCD と等しくなる。 GCD(? ? , ? ?+1 , … , ? ? ) =GCD(? ? , ? ?+1 ? ? ? , … , ? ? ? ? ??1 ) ということ。
- 28. 両者が一致することの証明 ?=GCD(? ? , ? ?+1 , … , ? ? ) ?=GCD(? ? , ? ?+1 ? ? ? , … , ? ? ? ? ??1 ) とする。 ? ? ≤ ? ≤ ? となるどの ? についても ? ? = ??と 表すことができる。(? は正整数) ? ? ? が ? の倍数なのでそれらの差も ? の倍数 である。よって ? は ? の倍数である。 ? ? ≤ ? であることはこのことより分かる。
- 29. 両者が一致することの証明 ? ? の性質より ? ≤ ? ≤ ? ? 1 となるどの ? につ いても、 ? ?+1 ? ? ? = ? ? ? となる正の整数 ? ? が存在する。 ? また、? ? = ?? (? は正の整数) も成立する。 ? このとき、 ? ≤ ? ≤ ? となるどの ? についても、 ??1 ? ? = ? ? + ?=? (? ?+1 ? ? ? ) ??1 ?=? = ?(? + ? ? ) となるから、 ? は ? の 倍数である。 ? よって ? ≥ ? も成立し、 ? = ? が成立する。
- 30. 満点解法 ? よって、segment-tree に、管理する区間に含 まれる、隣り合う差の GCD と左端の要素を保 存しておき、質問クエリに対して、それぞれの 区間ごとに区間内の隣り合う差の GCD をまと め、それらの隙間の部分と左端の要素をまと めれば質問に答えることができる。これは O(log ?) である。 ? 増減クエリに対して、隣り合う差の GCD は、 区間に一部またがる場合のみ更新される。 ? この方法だと O(log ?) で更新できる。
- 31. 満点解法 ? 左端の要素 ? ? に関する情報について、増減 クエリそのまま個々の要素に実行すると時間 がかかる。 ? 区間和として、質問クエリに対し遅延評価を するとこの問題を解決できる。 ? 全体で O(? log ?) となり満点が得られる。
- 32. 補足 ? 今回の問題に、「初期状態およびクエリ実施 後にすべての数が 1 以上 109 以下となる」と ありますが、遅延評価用にとっている区間の 中身が 32 bit 整数に収まるとは限りません。 ? 初期状態で ?1 = ?2 = 1 として ? 9 × 108 1 2→ ?9 × 108 1 1→ ?9 × 108 2 2 というのが 3 回以上繰り返された場合など。 ? 2 の補数表記の性質上、実は考慮しなくても うまくいく場合があるみたいです。