A. Level Statistics

問題文が長すぎます。長い上によくわからないのでサンプルを見てエスパーをしました。総プレイ数と総クリア数をモニターした結果が入力で与えられるので、それが適切かを判断せよ、って感じです。たぶん。全ての i \( ( 0 \le i \le n ) \) で、\( 0 \le p[i] - p[i-1] , 0 \le c[i] - c[i-1], c[i] - c[i-1] \le p[i] - p[i-1] \) が成り立てばYESです。(p[0], c[0]) = (0, 0) の番兵を置いておくと楽です。

B. Middle Class

平均が x 以上となる部分集合のうち、サイズが最大のものを求めれば良いです。明らかに大きい方から集合に詰めていくのがいいので、降順ソートして上から詰めていきます。

C. Circle of Monsters

最初に kill するモンスターについてはきっちり体力分の弾丸を打ち込まなければいけないことがわかります。それ以外のモンスターについては、試しにa[0] のモンスターを kill した場合について考えてみます。すると、全ての i \( 1 \le i < n \) については、きっちり max(0, a[i] - b[i-1]) 発分の弾丸を打ち込めばいいことがわかります。つまり、a[0] を最初に kill する場合に使用する弾丸の総数は、\( a[0] + \sum _ {i = 0} ^ {n-1} max(0, a[i] - b[i-1]) - max(0, a[0] - b[-1]) \) となります。ここで、b[-1] = b[n-1] とします。結局、a[i] を最初に kill する場合に使用する弾丸の総数は、\( a[i] + \sum_{i = 0}^{n-1} max(0, a[i] - b[i-1]) - max(0, a[i] - b[i-1]) \) となり、sum の部分を前計算しておけば、各 i について O(1) で処理することができます。よって、全ての i についてa[i] を最初に kill する場合に使用する弾丸の総数を計算し、その最小値を求めれば良いです。これをそのまま書いたら TLE したので、入力を scanf に変えたら通りました。うーん。よく考えたら、a[i] - max(0, a[i] - b[i-1]) が最小となるような i を見つければいいだけなので、いちいち全部計算する必要は無いのか？

D. Minimum Euler Cycle

めんどくさかったです。まずは、全ての辺を通るパスのうち、通過した頂点を順に並べたものが辞書順最小になるようなパスを構築してみます。こういうのは、簡単な構築法があるはずなんですよね〜という気持ちで頂点数の少ないグラフを実際に書いて実験してみると、頂点数 n のグラフにおいて、1213...1n2324...2n34......1 というパスが条件を満たすことがわかります。あとはこのパスで前から i 番目の数字が何であるか？という問いに答えられればいいです。めんどくさいだけなので、割愛します。

E. Divisor Paths

おもしろかったです。エスパーしてサンプルがあったときは興奮しましたが、結局通りませんでした ( ただオーバーフローしてただけでした...悲しい )。かなりエスパーして何も理解していなかったので、後で解説を見てちゃんと解きました。まず、辺がどこに張られるかを考えてみます。y が x の約数であり、x / y が素数であるような x, y の間に辺が張られるとのことなので、頂点 x から張られる辺の先の頂点 y の条件は、y が x を x の素因数で割った商であること、です。x -> y のパスは、y が x の約数であるときには、x が y になるまで素数で割っていくことで構築できます。このパスのコストは、x の約数だが、y の約数でないものの数と等しいです。さて、x と y の最短パスについて考えます。実はこれは、途中で gcd(x, y) を経由するようなパスが最短であることがわかります。x から y に移動するということは、x から素因数をいくつか取り除いて、y になるまで素数を掛ける、ということと同じです。この操作において、取り出した素数の数とかけた素数の数の合計が、パスのコストになります。すると、x と y に共通する素因数を取り除いてしまうのは無駄で、そのような操作をするパスは最短にならないことがわかります。つまり、x から gcd(x, y) になるまで、素因数を取り除き、gcd(x, y) から y になるまで素数を掛ける、というパスが最短になります。あとは、x -> gcd(x, y) の最短パスの総数と、gcd(x, y) -> y の最短パスの総数を掛け算してあげればそれが、x -> y の最短パスの総数になります。x -> gcd(x, y) の最短パスは、x から gcd(x, y) になるまで、素因数を取り除いていくことで実現されますが、取り除く素因数についてはどの順番で取り除いてもパスのコストは変わりません。なので、取り除く素因数の集合 ( x / gcd(x, y) を素因数分解すれば得られます ) の要素の並べ替えの総数がパスの数になります。これは簡単な組み合わせ計算で出すことができます。gcd(x, y) -> y については、y -> gcd(x, y) のパスと同じであると考えることによって同様に処理できます。この計算は、d の約数全てについて素因数分解したものを持っておけば、十分高速に処理できます。d の約数全てを素因数分解するのは愚直にやると間に合いませんが、d を素因数分解した結果から差分を更新していくようにしてテーブルを作成すれば間に合います。( エスパーしたときは、gcd(x, y) を通るパスではなく、lcm(x, y) を通るパスを使用していました。なぜ？結果的にはそれでも解けるのですが、lcm(x, y) を計算する際に、x*y が発生してオーバーフローしてました。うーん、ライブラリ整備が甘い。)

感想

解けて欲しいものについては、そこそこ早く解けたので良かったです。E はやばい問題設定に面食らってる時間が長くてもったいなかったです。こういうのをしっかり解けるようになりたいね。

現代の量子力学

主に精進の様子を記録する日記帳です

Educational Codeforces Round 85 (Rated for Div. 2) A~E

A. Level Statistics

B. Middle Class

C. Circle of Monsters

D. Minimum Euler Cycle

E. Divisor Paths

感想