![部分点解法(30点)
? W,H,Q≦ 100
? 1 ≦ ビームが飛んでくる時刻(この最大値をT
とする) ≦ 100
? DP[i][j][k]: 時刻iに、マス(j,k)にいるときの最
小の移動回数 として、DP配列を更新していく
? 各iごとにdijkstra法などを用いてDP配列を順
次更新していくと、O(WHT log WH)](https://image.slidesharecdn.com/arc044-150912132911-lva1-app6891/85/AtCoder-Regular-Contest-044-16-320.jpg)
![満点解法
? DP[i][j]: 時刻iに座標jにいるときの移動距離
の最小値 とする
? これを愚直に計算するとO((W+H)T)
? よく考えると、DP[i][j]たちとDP[i+1][j]たちは
「あまりかわらない」
– 具体的には、異なる箇所は時刻i+1に飛んでくる
ビームの本数分のみ](https://image.slidesharecdn.com/arc044-150912132911-lva1-app6891/85/AtCoder-Regular-Contest-044-18-320.jpg)
AtCoder Regular Contest 044 解説
- 2. A問題 「素数判定」
- 3. 問題概要 ? 整数N(1≦N≦10^9)が素数っぽいかどうか判 定せよ ? Nは以下のいずれかの条件を満たす時素 数っぽい – 素数である – 合成数であり、かつ1の位が2でも5でも割り切れ ず、各桁の和が3で割り切れない
- 4. 解法1 ? 愚直に計算 ? 素数判定にO( ?) ? 各桁の和を求めるのにO(log N) ? あわせてO( ?)
- 5. 解法2 ? 各桁の和とかは求めなくていい – Nの1の位が2でも5でも割り切れず、各桁の和が3 の倍数であることは、Nが2,3,5で割り切れないこ とと同値 ? 実は素数判定も要らない – 2,3,5以外のNについて、Nが素数ならNは2,3,5で 割り切れない
- 6. 解法2 ? 以上をまとめると – N=1ならNot Prime(1は素数でも合成数でもない) – それ以外でN=2,3,5ならPrime – それ以外でNが2,3,5で割り切れるならNot Prime – それ以外ならPrime ? と出力すればよい ? O(1)で解けた
- 7. B問題 「最短路問題」
- 8. 問題概要 ? 整数Nと整数列?1, ?2,…, ? ?が与えられる ? 頂点数Nですべての辺のコストが1の単純無 向グラフであって、任意のiに対して頂点1から 頂点iまでの距離が??であるようなものの個 数をmod 10^9+7で求めよ ? N ≦ 10^5
- 9. 解法 ? まず、自明に答えが0になる場合を取り除く – ?1 ≠ 0だとだめ(頂点1から頂点1への距離は0) – 0が複数あってもだめ(頂点1から頂点1以外への 距離は正)
- 10. 解法 ? 2点間に辺を張れる条件は? – その2点の、 ?1からの距離の差が1以下 – 距離の差が2以上あると、その辺を使うことで最 短距離の性質に矛盾する ? 2点間の距離が0の場合と1の場合に分けて 考える
- 11. 解法 ? 2点間の距離が0のとき辺はどう張ってもいい – 辺があろうがなかろうが最短距離は変わらない ? ?? = ?なるiが??個あるとき、距離Cの頂点の 間に辺を張る場合の数は2 ? ?(? ??1) 2 通り ? これは、N乗までの2冪をループで順にもとめ ていき、さらにそれらの掛け算で2の三角数乗 を順に求めていけばあわせてO(N)で求まる – 二分累乗ならO(Nlog N)
- 12. 解法 ? 2点間の距離が1のとき、その?1からの距離を それぞれi, i+1とし、 ?1からの距離がiであるよ うな頂点の数をt, i+1であるような頂点の数をs とする ? 距離i+1の頂点たちからは、1本以上の辺が 距離iの頂点のいずれかに張られていなけれ ばならない – 逆に、それ以外はどう張ってもよい
- 13. 解法 ? このような場合の数は(2 ? ? 1) ? 通り ? これも2冪のテーブルをO(N)で前計算してお けば、合計O(N)で求まる – 頂点数の和はNよりこの操作にはO(s)かけられる – おなじく二分累乗ならO(Nlog N) ? ということでこの問題が解けた
- 14. C問題 「ビーム」
- 15. 問題概要 ? W*Hのグリッドに高橋君がいる ? 1列全体、もしくは1行全体にQ回ビームが飛 んでくる ? 高橋君は任意時刻にすきなだけ縦横に移動 できる ? 全部よけるとき、高橋君の縦横への移動回数 の最小値は? ? W,H,Q,ビームが飛んでくる時刻 ≦ 10^5
- 16. 部分点解法(30点) ? W,H,Q≦ 100 ? 1 ≦ ビームが飛んでくる時刻(この最大値をT とする) ≦ 100 ? DP[i][j][k]: 時刻iに、マス(j,k)にいるときの最 小の移動回数 として、DP配列を更新していく ? 各iごとにdijkstra法などを用いてDP配列を順 次更新していくと、O(WHT log WH)
- 17. 満点解法 ? x座標、y座標は独立に考えられる(重要アイ デア) – ビームは一列、もしくは一行すべてに飛んできて、 高橋君の移動距離の定義もマンハッタン距離 ? x座標、y座標独立に問題を解いて、あとで足 し合わせればいい ? 以下x座標についてのみ考える
- 18. 満点解法 ? DP[i][j]: 時刻iに座標jにいるときの移動距離 の最小値 とする ? これを愚直に計算するとO((W+H)T) ? よく考えると、DP[i][j]たちとDP[i+1][j]たちは 「あまりかわらない」 – 具体的には、異なる箇所は時刻i+1に飛んでくる ビームの本数分のみ
- 21. 問題概要 ? 10^6項以下のpermutationが与えられる ? このpermutationをsuffix arrayに持つ辞書順 最小の文字列を求めよ
- 22. 解法 ? 順列?1, ?2,…, ? ?が文字列?1 ?2 … ? ?のsuffix arrayである ? ?すべての1≦i≦N-1に対し、 文字列 ? ? ? ? ? ?+1 … ? ? < ?? ?+1 ?? ?+1+1 … ? ? ? ?すべての1≦i≦N-1に対し、 ? ? ? < ?? ?+1 ま たは、?? ? = ? ? ?+1 かつ? ? ?+1 … ? ? < ? ? ?+1+1 … ? ?
- 23. 解法 ? すべての1≦i≦N-1に対し、 ? ? ? < ? ? ?+1 また は、?? ? = ? ? ?+1 かつ ? ? ?+1 … ? ? < ? ? ?+1+1 … ? ? ? ?すべての1≦i≦N-1に対し、 – ? ? ?+1 … ? ? < ? ? ?+1+1 … ? ?ならば? ? ? ≦ ? ? ?+1 – そうでないなら、 ? ? ? < ? ? ?+1
- 24. 解法 ? ? ? ?+1 … ? ? < ? ? ?+1+1 … ? ?かどうかは、suffix arrayが持っている情報 ? ということは、各iについて、 ?? ? と? ? ?+1 の満た すべき関係がわかる ? 前から順に見ていけば、文字列の各文字が 最も小さくて何であるかがすべてわかる
- 25. 解法 ? 逆に、suffix arrayを前から順に見ていき、この ような方法で各文字を決めていけば、そうし てできた文字列のsuffix arrayは元の順列に 一致することは簡単に示せる ? よって、前から貪欲に文字を決めていけば、 O(N)でこの問題が解けた