SRM 677 div1 easy:DiameterOfRandomTree
SRM 677 に参加しました。easy かなり苦しかったけど通してレートが少し上がりました。最近 easy が解けなくてレート下がってたし, システムテスト通った時めっちゃ興奮しました。やっぱいいですね。
問題
整数の組 (a, b) および (newA, newB) が与えられる。
(a, b) に対して, 以下の 2 通りの変換をすることが出来る。
- (a, b) -> (a+1, b+1)
- (a, b) -> (2a, 2b)
これらの変換を駆使して, (a, b) の組を (newA, newB) にすることが出来るような, 最変換回数を求めよ。
解法
本番自分が書いた頭の悪い方法と, 他の人がやってためっちゃ頭の良い方法の 2 通りを紹介します。
まず自分の解法。
(a, b) -> (2a, sb) という変換をすると, b-a の値が 2 倍になることに注目します。
ということは, ndiff = newA-newB, diff = a-b とすると, ndiff は diff の, 2 のべき乗倍になっているはずです。
ということで, 2 倍にする変換は何回行うことになるのかは, 一意に決まります。
例えば,
(a, b) = (1, 2)
(newA, newB) = (10, 18)
とすると, diff = 1, ndiff = 8 なので, 2 倍の変換は 3 回行うことになります。
あとは, 「どのタイミングで 2 倍の変換を行うのが最適か」というのを考えればよいです。
考えやすくするために, (a, b) を変換していって (newA, newB) にすると考えるのではなく, (newA, newB) を変換していって (a, b) にすると考えます。変換は,
(newA, newB) -> (newA-1, newB-1)
(newA, newB) -> (newA/2, newB/2) (ただし両方共偶数の時のみ)
すると, 「なるべく早めに半分にする変換をたくさんやるべき」という結論が得られます。さっきの例で言うと,
(10, 18) はともに偶数だから (5, 9) にして, 次は両方共奇数だから 1 引いて (4, 8) にする, そこからはともに偶数だからどんどん 2 で割ってって (1, 2) にして終了, という感じです。これをコードで実装すればよいですが, なんでこれで良いかを考える必要があります。
まず回数的には, 2 で割れるときになるべく割っていくほうが 1 引く変換を行う回数が少なくなります。これはサンプルの (100, 1000) を (202, 2002) にする時, まず (202, 2002) を 2 で割ってから 1 引く変換をするほうが有利なことと同じです。
で, あと考えないといけないのは, この戦略で変換していくと, この変換方法で失敗する((newA, newB) の組を (a, b) にすることが出来ない)時, 他のどのような方法を用いても失敗する, ということです。これが成り立っていないと, 「回数は多くなっちゃうけどとある別の変換方法で試したらちゃんと (a, b) の組ができるから OK」になる可能性があります。
例えば, 実は (3, 4) -> (17, 25) という変換は, 上記のアルゴリズムでは不可能です。実際やってみると,
(17, 25) -> (16, 24) -> (8, 12) -> (4, 6) -> (2, 3)
となりますが, 2 < 3, 3 < 4 より, 少なくともこの方法では (3, 4) から (17, 25) には出来ません。この時, 他の方法でも (17, 25) にすることは出来ないのかは考える必要があります。
上に示したように, 「2 で割る」という操作をする回数は一定です。
「(a, b) にすることが出来ない」というのは, 2 で割る変換を一定回数行った後に (newA, newB) の値を見ると, それが newA < a または newB < b になっている, ということです。こうなっていなければ, newB - newA == b-a となっていることが保証されているので, 1 引く変換を繰り返せば OK です。
なるべく早く 2 で割る変換を行うと, 変換された数の組は, できるだけ数を大きくしたものになります。上の例では, (17, 25) -> ... -> (14, 22) -> (7, 11) というように 2 で割る変換を遅らせると, 一番最初に 2 で割った後の値は (8, 12) よりも小さい (7, 11) になっています。これでは最終的に出来る (newA, newB) の組が newA < a または newB < b となる可能性が増えるだけで, 良いことは何もありません。
以上により, 「なるべく早めに半分にする変換をたくさんやるべき」という戦略が正しいです。
あ, diff = 0 の場合を忘れてました。この場合も, 上記の「なるべく早めに半分にする変換をたくさんやるべき」という戦略が正しいです。ただし, 2 で割る操作を終了する条件は, newA / 2 < a となる時です。
実装も非常に心配になりますが, 祈りながら書けば AC します(チャンレジフェーズの時は気が気でなくてまったくチャレンジする気になれなかった)。
const ll INF = 1ll<<55; class DoubleOrOneEasy { public: int minimalSteps(int a, int b, int newA, int newB) { if (a > b) { swap(a, b); swap(newA, newB); } int diff = b-a, ndiff = newB-newA; if (diff == 0) { if (ndiff!=0) return -1; if (a > newA) return -1; int ans = 0; while (1) { if (newA/2 < a) break; if (newA%2==0) { newA /= 2; ans++; } else { newA--; ans++; } } ans += newA-a; return ans; } else { if (ndiff%diff) return -1; int div = ndiff/diff; int cnt = -1; for (int i = 0; i <= 30; i++) { if (div == (1<<i)) { cnt = i; } } if (cnt==-1) return -1; int tmp = cnt, plus = 0; while (tmp) { if (newA%2==0 && newB%2==0) { newA /= 2; newB /= 2; tmp--; } else { newA--; newB--; plus++; } } if (newA < a || newB < b) return -1; return cnt+newA-a+plus; } } };
はい, 次は頭の良い方法です。実装も短いし考察も簡潔です。
一連の変換を f(x) とすると, 結局のところ f(x) = x*2^i + j
という変換を a, b の両者に施していることになります。
すると, 変換回数は, まず 2 倍にする回数で i 回です。+1 する回数は j というわけではありません。j のうち 2^i 未満の成分の足し算は, 2 倍する間に挟みこめばこなすことができるので, +1 をする回数は, j/(2^i) + (j の i bit 目までの bit が立っている個数) で求めることが出来ます。ということで, 2 倍する回数 i について全探索して最小回数を求めましょう。
const ll INF = 1ll<<55; int solve(ll a, ll b, ll na, ll nb) { ll ans = INF; for (int i = 0; i < 32; i++) { if (na - (a<<i) == nb - (b<<i)) { ll j = na-(a<<i); if (j < 0) continue; ll tmp = i + (j>>i) + __builtin_popcount(j&((1<<i)-1)); ans = min(ans, tmp); } } if (ans==INF) return -1; return (int)ans; } class DoubleOrOneEasy { public: int minimalSteps(int a, int b, int newA, int newB) { return solve(a, b, newA, newB); } };
