No.643 Two Operations No.2
No.643 Two Operations No.2 - yukicoder
考察
xとyの比を取って、p = x/yと置くとx=yにするということはp=1にするということと同値であることが分かります。
(ただし、y=0のときはp=∞であると考えることにします。また(x, y) = (0, 0)は少し特殊なので無いものとします)
このpで与えられた各操作を考えてみると、
- 操作1:p -> 1/p
- 操作2:p -> (p+1)/(p-1)
にすることであるということが計算によって分かります。この操作を繰り返してp=1にするゲームだと思えばいいことになります。
p=1に1ステップで行ける状態を考えてみます。操作1は1を1にするだけなので考えてもしょうがないです。操作2は(p+1)/(p-1)=1となるpを求めることになりますが本来ならそのようなpは存在しません……
ですがp=∞とすると、(∞+1)/(∞-1) = ∞/∞ = 1なのでp=∞からp=1へは1ステップで行けることが分かりました。(この計算は本当はめちゃくちゃなので、元の(x,y)で計算して確かにこれが正しいことを示す必要があります)
次にp=∞に1ステップで行ける状態を考えてみます。操作1を考えると1/0=∞なので0から1ステップで行けます。操作2を考えると分母が0になるpということなのでp=1から操作2で1ステップで行けます。(本当はめちゃくちゃ)
さらにp=0に1ステップで行ける状態。操作1では1/∞=0なので∞から0へ1ステップで。操作2ではp=-1のとき分子が0になるので、-1から0へ1ステップで。
さらにp=-1に1ステップで行ける状態。操作1では明らかに-1から-1。操作2では(p+1)/(p-1)=-1を解くと、p=0。0から-1へ1ステップ。
ここで状態がもう増えなくなったので結局どういうことになっているかをグラフにまとめると以下のようになっています。
よって、与えられた(x,y)からpを求めて、それがこのグラフに乗っていればその最短距離を返す。
これ以外の点であれば、これらの操作を繰り返してもp=1に到達することはできないので-1を返します。
感想
とても難しい★2だと思いました。コンテスト中には解けませんでしたが……楽しかったです。
この考え方は、testestestさんがまとめていてくれている「射影空間へうつす」という奴に対応しているはずでそれを使うと今回の議論が正当化できるはずです……多分。
No.642 Two Operations No.1
No.642 Two Operations No.1 - yukicoder
考察
とりあえず整数を頂点、操作を辺としてグラフにしてみると以下のような感じになります。
頂点数はNで辺の数は2Nなので、N <= 10^6程度ならこのグラフで頂点1からBFSをすることで
最短距離(最小操作回数)が求められますが、今回はN <= 10^9なのでもう少し工夫しないといけないようです。
頂点iへの最短距離をdist(i)と書くことにします。
グラフをよく見てみると、奇数の頂点は1つ大きい数からしか到達できないのでi = 2k + 1とすると、dist(2k + 1) = dist(2k + 2) + 1となっていることが分かります。
問題は偶数の頂点で、この頂点には辺が2つ入ってきます。なので
dist(2k) = min(dist(k), dist(2k+1)) + 1
と書けます。何となく、小さいケースでいくつか試してみると、常にdist(k) <= dist(2k+1)が成り立っているような気がします。
実際に、頂点2kの周りとkの周りの関係を書いてみると以下のようになります。
もしここで、dist(k) > dist(2k+1)が成り立っていたとしたら最短路を逆順にたどっていくと、2k -> 2k+1 -> 2k+2までは一直線に進みます。ここでまた分岐するのですが、もしここで2k+2 -> k+1と戻る枝を使ったとすると、結局k+1から3ステップで2kに来ることになるので、dp(2k) = dp(k+1) + 3となります。(下図赤線)
一方で、k+1 -> k -> 2kと高々2stepで行くことができるので、dp(2k) <= dp(k+1) + 2であることが分かります。(下図青線)
これは矛盾しているので、2k+2 -> k+1と戻る枝を使ったことは誤りとなります。
なのでさらにさかのぼって2k -> 2k+1 -> 2k+2 -> 2k+3 -> 2k+4と行ってまた枝分かれするんですが、ここでも2k+4 -> k+2と戻る枝を使うと仮定すると矛盾が起こることが同様に分かります。
よって帰納的にこのようなことが示せてしまうので、結果的にはそもそもdist(k) > dist(2k+1)と仮定していたこと(つまり2k <- 2k+1が最短路に含まれていたと仮定したこと)が誤りであるということが言えます。よってdist(k) <= dist(2k+1)なので、「2kに行くにはkから来る枝を使う」としていいことが分かります。
上の議論によって何が言えるかというと、
- nが奇数のときは、n+1に戻ればよい
- nが偶数のときは、n/2に戻ればよい
ということなので、後はこれをn = 1になるまで繰り返せばよいということになります。2回に1回はnが半分になるので計算量的にもだいたいO(logN)なのでこれで十分間に合うということが分かります。
感想
難しい★2だと思いました。
ABC056/D - No Need
https://beta.atcoder.jp/contests/abc056/tasks/arc070_b
考察
要素の順番は関係無いので、考えやすくするためにとりあえずa_iは昇順ソートされているものだとします。
まず、「カードiが必要であること」とはどういうことかと考えてみると、条件の否定を考えて「カードiを含むある集合が存在して、その集合からiを抜くと総和がK未満になってしまう」ということになります。
このことから「カードiを除いた全ての数で[K - a_i, K)に含まれる数が作れるか」ということと同値だと分かります。もし作れるのなら、そこにカードiを加えた集合は良い集合になるのでカードiは必要だと分かるし、逆に[K - a_i, K)に含まれる数が作れないのならiを加えたところで良い集合になるものは存在しないと分かるからです。
なので、各iについて「カードiを除いた全ての数で[K - a_i, K)に含まれる数が作れるか」を調べていけばいいことになってこれを愚直に総当たり+部分和DPでやるとO(N^2 * K)になってしまいます。これでもN = K = 400までの部分点は取れそうですが、N = K = 5000の満点は無理そうなのでもう少し計算量を落とす必要があります。
まず考えられるのは「愚直に全部見ていく必要はあるのか?」ということです。もし「iが必要である⇒i+1も必要である」というような単調性が成り立っていれば、真面目に全探索する必要はなく二分探索を使えばいいのでそうなっていないかと考えたくなります。a_iが昇順ソートされているものだと思うと、区間[K - a_i, K)はiが増えるごとに広がっていくので何となくそのような単調性がありそうだなと思います。
少し考えると実際に、このような単調性を示すことができます。
もし、iが必要であるとすると、iを除いた集合で[K - a_i, K)に含まれる整数が作れます。もしそれがi+1を含まないもので作れているとすると、i+1を除いた集合でも明らかに作れて、それは[K - a_{i+1}, K)にも明らかに含まれるので良いです。
問題はi+1を使って作っている場合ですが、このとき、i+1をiに置き換えて作った整数はいくらか小さくはなりますが[K - a_{i+1}, K)に含まれていることは分かります。小さくなった分だけ区間が広がっているからです。
こうやって二分探索が使えることが分かると、計算量はO(N * K * log(N))に落とすことができます。それでも、最大ケースでは3 * 10^8程度になるっぽいのでこれは想定解じゃないのかな……と思いましたが、1つの想定解であったそうです。
実際これをやってみるとそんなに無理なく通すことができました。
そしてO(N*K)の想定解もあったようで、こちらは前の方から部分和DPをやって後ろの方から部分和DPをやると、{0, ..., i-1}で作れる整数と{i + 1, ..., N - 1}で作れる整数が分かるので、これらの結果をtwo-pointersでいい感じにやるとO(N*K)で出来るみたいな感じでした。(本当は解説にはtwo-pointersじゃなくて「累積和を使う」と書いてあるのですが、よく分かりませんでした)
ソースコード
ソースコードはテンプレートとか適当に省略しています。
二分探索
void main() { int n, k; int[] a; scan(n, k); a = readln.split.to!(int[]); a.sort(); bool check(int mid) { if (a[mid] >= k) { return true; } auto dp = new bool[](k + 1); dp[0] = 1; foreach (i ; 0 .. n) { if (i == mid) continue; foreach_reverse (j ; a[i] .. k + 1) { dp[j] |= dp[j - a[i]]; } } foreach (i ; max(0, k - a[mid]) .. k) { if (dp[i]) { return true; } } return false; } int btm = -1, top = n; while (top - btm > 1) { int mid = (top + btm) / 2; if (check(mid)) { top = mid; } else { btm = mid; } } writeln(btm + 1); }
前/後ろDP + two-pointers
void main() { int n, k; int[] a; scan(n, k); a = readln.split.to!(int[]); auto dp1 = new bool[][](n + 1, k); dp1[0][0] = 1; foreach (i ; 1 .. n + 1) { foreach (j ; 0 .. k) { dp1[i][j] = dp1[i-1][j]; if (j - a[i-1] >= 0) dp1[i][j] |= dp1[i-1][j-a[i-1]]; } } auto dp2 = new bool[][](n + 1, k); dp2[n][0] = 1; foreach_reverse (i ; 0 .. n) { foreach (j ; 0 .. k) { dp2[i][j] = dp2[i+1][j]; if (j - a[i] >= 0) dp2[i][j] |= dp2[i+1][j-a[i]]; } } int ans; foreach (i ; 0 .. n) { int mv; for (int l = 0, r = k-1; l < k; l++) { if (!dp1[i][l]) continue; for (; r >= 0; r--) { if (dp2[i+1][r] && l + r < k) { mv = max(mv, l + r); break; } } } if (mv < k - a[i]) ans++; } writeln(ans); }