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]

ファイルを添付する

fileizumi_A-naive.cpp 1488件 [詳細] fileizumi_A.cpp 1449件 [詳細] fileA.cpp 1208件 [詳細] filemikurube_A.c 1515件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileizumi_A-naive.cpp 1488件 [詳細] fileizumi_A.cpp 1449件 [詳細] fileA.cpp 1208件 [詳細] filemikurube_A.c 1515件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (4575d)