Unit Fraction Partition 解説
- 問題名：Unit Fraction Partition (PKU)
- 出典：Problem C, ACM/ICPC Japan Domestic, 2004-07-02
- 難易度：☆☆
- 問題の種類：探索
- 解法：枝刈り探索
- 解答ソースコード：
- 1980-deq_1.cpp（有理数として扱う）
- 1980-deq_2a.cpp（double型で扱う（PKUはTLE））
- 1980-deq_2b.cpp（double型で扱う（PKUを通る））
- プログラムプロムナードの解説：2004年12月号『国内予選を突破せよ』（湯浅太一）
アルゴリズムの概略
単位分数という数論的な問題かと思いきや，n <= 7 の単純な探索問題です。 さらに，問題で与えられているように
- 分割は n 個以下の単位分数の和である。
- 分割に含まれる単位分数の分母の積は a 以下である。
という二つの枝刈り条件が既に示されています。
この問題は上記の枝刈り条件を含めたアルゴリズムを率直に書いて， 他の自明な枝刈り条件（右辺の和が左辺を超えればその探索は打ち切る）を入れれば解けます。
探索なので，再帰関数に渡すのは「残りのステップ数」，「現在の状況」，「過去の経路情報」になります。 この問題の場合，「現在の状況」は選んだ分母の値に当たります。 単位分数を足していく順序の違いは無視される（1/6 + 1/2 と 1/2 + 1/6 を区別しない）ので， 昇順（1/1, 1/2, 1/3, ...）か降順（1/a, 1/a-1, ...）のどちらかで調べる必要があります （例えば昇順では，1/2を使った場合，次は1/3からではなく1/2から調べる必要があることに注意）。 つまり，再帰関数の中で「どこから調べればいいか」を表す情報が必要なので，今回は「現在の状況」がそれに当たるわけです。
「過去の経路情報」としては，例えば 1/3 + 1/6 まで探索している場合，その二つの値を渡してもよいのですが， 毎回それらの値を足していると計算が遅くなるので足し合わせた値 1/3 + 1/6 = 1/2 に関する情報を渡してやればOKです。 1/2の情報を表すのには，分子と分母を別々のint型として渡す「有理数として扱う」方法と， 計算結果の0.5という値をdouble型として渡す「浮動小数として扱う」方法があります。 ここではどちらを使っても解けるのですが，後の「アルゴリズムの実装」でそれぞれ説明しましょう。
なお，この問題のPKUのTLE (Time Limit Exceeded) が微妙な値になっていて， ここに載せているアルゴリズムでは細かなチューニングをしないと時間切れになって正解になりません。 もともと国内予選は従来TLEがない（手元のPCで実行する）ので1秒くらい多く時間がかかってもOKなのですが， この問題のTLEは1000msなので200msくらい実行時間が変わるとAcceptedになったりTLEになったりします。 int型の演算は速いので通りやすいですが，double型の割り算などは遅いので気をつけましょう。 他の枝刈り条件をつける方がスマートですが...
アルゴリズムの計算量
枝刈り探索の問題は計算量を正確に求めることが困難です。 基本は try and error で感覚を掴むしかないように思えます。
アルゴリズムの実装
有理数として扱う方法
この方法では「そこまでの合計」を有理数として扱う，つまり分子と分母は別々のint型引数として渡します。 また，「分割に含まれる単位分数の分母の積は a 以下である」という条件があるので， 1/3 + 1/6 は 1/3 + 1/6 = 6/(3*6) + 3/(6*3) = 9/18 という通分した値を渡してあげると， 分母が自動的に「単位分数の分母の積」になるので扱いやすくなります。 左辺（p/q）と右辺（単位分数の和）の比較も同様に通分すれば行えますね。
紙で書けばすぐ分かると思うのですが，一応式を載せておくと，元の式が（ここでは便宜上等式として書いておきます）
だとすると（p/q = 問題に与えられている，total/product = 今までの単位分数の和，1.0/i = 新しく追加しようとしている単位分数）， 通分すれば
となるので後は分子を比較するだけです。
浮動小数として扱う方法
浮動小数（double型）として扱うと計算誤差が出るので，計算誤差に対処するコーディングが必要です。 基本的な点として，浮動小数同士では == 演算子による比較ができないということが挙げられます。 そこで，厳密な値は違っていても，計算誤差程度の違いであれば同一とみなすという処理が必要で， 具体的には
#define EPS (1e-8) #define EQ(a,b) ((a) - EPS < (b) && (b) < (a) + EPS)
という風に「非常に小さい数」ε（イプシロン）を定義します（ここではε = 10-8）。 この値は問題ごとに異なる精度です。
また，単純な a < b というような比較でも問題が起きることがあります。 つまり，a == b とみなしたい状態でも a < b が真になることがあります。 そのような場合には a < b - EPS といった感じで比較を行う必要があります。
$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $