ページ最後のほうにAC解法まとめとソースコードへのリンクがあります。
問題
昨日のコンテスト。
当初は $x=0,y=0$。
順次、以下のいずれかの操作を行う。
- 操作1: $(x,y)→(x+1,y)$
- 操作2: $(x,y)→(x,y+1)$
- 操作3: $(x,y)→(x+y,y)$
- 操作4: $(x,y)→(x,x+y)$
130回以内の操作で$x$を指定された数にする。
$1≦N≦10^{18}$。
考察
$10^{18}$だからほぼ64ビット。代わりに条件が
- 操作1: $x→x+1$
- 操作2: $x→2x$
だったとしても、最悪128回に近い操作回数が必要になる。本題の制約はかなり厳しく、最適解に近いものが求められる。
まずは数をできるだけ少ない回数で増加させる方法から考える。これはやはりフィボナッチ数列。
操作1, 4, 3, 4, 3, 4, …と繰返すと、
$(0,0)→(1,0)→(1,1)→(2,1)→(2,3)→(5,3)→(5,8)→…$
操作2, 3, 4, 3, 4, 3, …と繰返すと、
$(0,0)→(0,1)→(1,1)→(1,2)→(3,2)→(3,5)→(8,5)→…$
となる。
$N$がフィボナッチ数の場合はこれで解け、明らかにこれが最速ルート。
あとは$N$がフィボナッチ数でない場合、どうやってこの高速ルートに乗せていくか。
解法
フィボナッチ数限定
フィボナッチ数の一般項は
fib(n)
= \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\}
であり、
\frac{1+\sqrt{5}}{2}=1.68...,
\frac{1-\sqrt{5}}{2}=-0.618
であるので
\phi=\frac{1+\sqrt{5}}{2}
とおくと、nが大きくなるとフィボナッチ数は公比φの等比級数に近づく。
なので最後のyをy=x/φとして、逆算する。xもyも整数であるので、まるめが必要。
$ 6765/\phi = 4180.9999338… → 4181$
$ 4181/\phi = 2584.0001069… → 2584$
let y = |x| {
let cl = x as f64;
( x / ((5.0_f64.sqrt()+1.)/2.) ).round() as i64
};
(x, y) = (N, N/φ) を完成形として、(x+y, y)あるいは(x,x+y)から「逆操作」して(x, y)に変換することを繰り返す。a > bなら(a, b)が(a-b, b)、a<bなら(a, b-a)になる。
これはユークリッドの互除法と同じ操作。ただし除算のかわりに一回ずつ減算を行う。便宜的に「互減法」と呼んでおく。
以下、ほとんどが「逆操作」の話。
N = 21だと N/φ = 12.978… → 13。
(21, 13) → (8, 13) → (8, 5) → (3, 5)
→ (3, 2) → (1, 2) → (1, 1) → (1, 0)
最後にxを-1すれば(0,0)となるこれを逆回しすれば解答となる。
N = 34だと N/φ = 21.013… → 21。
(34, 21) → (13, 21) → (13, 8) → (5, 8) → (5, 3)
→ (2, 3) → (2, 1) → (1, 1) → (1, 0)
これでよい。
素直に実装
(x, y) = (x, y/φ)として、とりあえず回してみる。
N = 101だと N/φ = 62.421… → 20
(101, 62) → (39, 62) → (39, 23) → (16, 23) → (16, 7)
→ (9, 7) → (2, 7) → (2, 5) → (2, 3) → (2, 1) → (1, 1) → (1, 0)
NとN/φが互いに素であれば、「互減法」で自然に(1,0)に辿り着く。
$(9, 7) → (2, 7) → (2, 5) → (2, 3) → (2, 1)$のあたり、若干効率が悪そう。
N = 100だと N/φ = 61.803… → 62
(100, 62) → (38, 62) → (38, 24) → (14, 24) → (14, 10)
→ (4, 10) → (4, 6) → (4, 2) → (2, 2) → (2, 0)
NとN/φが互いに素でなければ、1ではなく最大公約数に到達する。十分小さければよいのだが。
(1000000000000000000, 618033988749894784)
(381966011250105216, 618033988749894784)
(381966011250105216, 236067977499789568)
...
(14464, 21504)
(14464, 7040)
(7424, 7040)
(384, 7040)
(384, 6656)
(384, 6272)
...
(384, 1280)
(384, 896)
(384, 512)
(384, 128)
(256, 128)
(128, 128)
(128, 0)
効率が悪いうえに128という怪しい数になった。これはおそらくi64をf64に変換して計算したために情報量と精度が保てなくなったため。1,000,000,000,000,000,000/φの本当の値は618,033,988,749,894,848と9の間にあり、f64を使用して計算した値とは60程度の隔たりがある。130回以内という制約を考えると非常に問題。
x/φを求めるのに128bit整数を導入
x:y(=x/φ)=y:x-y ⇔ x(x-y) = y^2 ⇔ y=\frac{{\sqrt{5x^2}-x}}{2}
である。(yについての二次方程式)この平方根が1未満の誤差で求められればよい。
元のxが64bit整数であるから、128bit整数の導入が必須。Rustだとi128が標準使用。C++でもGCCとかBoostにあったような。
let cl = |x: i64| {
let x = x as i128;
( ((5*x*x).sqrt()-x)/2 ) as i64
};
最初と最後に調整
(x, y) = (N, N/φ)で開始し、a回の操作で(GCD(=g), 0)となれば、合計a+g回。これが130回以下であれば、それが正解。
130回を超えるようなら、最後にxを+1することにして(N-1, (N-1)/φ)から開始してみる。そして条件を満たすまでNを減らしていく。悪くない。
復元すると、$(0,0)→(1,0)→…→(x_0,0)→…→(N-i,y)→(N-i+1,y)→…→(N, y)$
これで提出。コンテスト終わっちゃったけど。
凄い惜しいような。どういうテストケースだ。
解説をみる
ここで解説をみる。
フィボナッチ数列に沿った考え方は悪くない。ひっかかったのはここ。
各iについて，高々1回だけ操作1 or 2を行うことを考えてみます。
それが正しいアルゴリズムであればよいが、直観では理解できない。
ACとれなかったテストケースは操作1→3→4を繰り返して生成?
AC解法
「互減法」で「効率が悪い」のは(7, 2) → (5, 2) → (3, 2) のように減算が片方に連続して行われるとき。これは２つの数の比が黄金比から離れると発生する。
したがって、(N, N/φ)から「互減法」を行い、途中で現れた２つの数の比が黄金比から離れたときに、黄金比に近くなるようにxまたはyを減算すればよい。
具体的には x > yの場合(x, y) → (z, y) (z=x-y)とする際、先に定義したクロージャを用いてzとcl(y)を比較し、z > cl(y) であればzを減算する、といったように。
少し試して分かったが、減算するのは「可能なら延期する」のがよい。「逆操作」でなく操作の方で考えるとxかyに+1するのが早い方がよいということに相当する。早く加算した方が長い目で見て早く大きくなるので大雑把には理解できる。
探索も行っておらず、アルゴリズムとしては理想的と考える。公式回答も貪欲法とのことなのでどちらも同等の計算時間であろう。
AC解法の考え方まとめ
- 「フィボナッチ数列の増加速度」で増加させる。すなわち、操作3と4が交互になるべく長く続くようにする。
- (x, y)の2つの数の比が黄金比φに近づくように、適宜操作1と2で調節する。
- これを実現させるために(N, N/φ)から出発して逆方向に解く。
- N/φを厳密に計算するには64bitを超える精度の型を必要とする。
(付)フィボナッチ数列とユークリッド互除法の関係 \\ todo!()
フィボナッチ数はユークリッド互除法について「効率が悪い」
この問題との関連
#後記
競プロも8ヶ月、Rustに乗り換えて3ヶ月。
Qiitaに個別の解法を中心に投稿するのはどうなのかと思って控えていたのだが、
先日キャンペーンもやっていたことだし、遠慮なく投稿してよいサイトのようだ。
お役に立てそうなアイデアがまたあれば書かせていただきます。