2004/Contest/愛媛大会

Problem A : The Balance †

問題概要 †

解法 †

d が大きければ DP だろうけど、探索で十分。二次元探索 (x, y の両方) するのが不安な人は、x か y のどちらかだけからもう片方の可能性が 3 通り求まるので一次元探索も可能。 (三廻部; Nov 25, 2004)

別解（本当はこちらが正統派） †

おもりが 2 種類しかないのでユークリッドの互除法を利用する．最初に次の 3 通りに場合分けする．ここに薬は常に右側にのせることにする．同じ重さのおもりを両側の皿にのせる行為はまったく意味がない点に注意すること．

• 左側の皿に 2 種類のおもりがのせられる場合．
• 左側の皿に a[mg] のおもり，右側の皿に b[mg] のおもりがのせられる場合．
• 左側の皿に b[mg] のおもり，右側の皿に a[mg] のおもりがのせられる場合．

これらの場合を数式で表現すると，順に ax+by=d，ax+b(-y)=d，a(-x)+by=d となる．これらのそれぞれについて次の手順で x と y の値の組を計算する．ax'+by'=g を満たす x' と y' の組は容易に計算できる（ここに g は a と b の最大公約数）．その両辺を d/g 倍すればとりあえず aX+bY=d を満たす X と Y の組が 1 つ求まる．あとは X，Y をうまく調節して題意を満たすようにする．

ちなみにこの解法だと，最大公約数を求めた後はループがまったく必要ないので計算量は O(log n) ですむ．ここに n は a と b の大きいほう．［泉，27 Nov 2004］

注意 †

場合分けをする際に ax+by=d となる場合を忘れがちなので注意すること．

議論・その他 †

• とてつもなくわかりにくいコードになってしまった．コードの長さを気にしなければもっとわかりやすく書けるはず．［泉，28 Nov 2004］

ファイルを添付する †

izumi_A-naive.cpp

izumi_A.cpp

A.cpp

mikurube_A.c