Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2147-f0b8637e
この記事にトラックバックする(FC2ブログユーザー)

SRM522 DIV1 MEDIUM - CorrectMultiplication / DIV2 HARD - CorrectMultiplicationTwo (この記事を編集する[管理者用])

Source

TopCoder SRM522 DIV1 MEDIUM (450pt)
TopCoder SRM522 DIV2 HARD (900pt)
Problem Statement (DIV1)
Problem Statement (DIV2)

問題概要

正整数a, b, cが与えられる.
A, B, Cは正整数でA * B = Cが成り立つとき,|A-a|+|B-b|+|C-c|の最小値を求める問題.
DIV1ではa, b, cは10^9以下.
DIV2ではa, b, cは10^6以下.

解法

対称性よりaはbより小さいとする.
答えのAはあんまり大きく成り得ないので,Aがsqrt(10^9)+α程度まで全部調べる.
Bはc/Aの周辺を少しだけ調べれば良い.
Aが大きくならないとか,Bが周辺だけでいいとかは,そうじゃなかったらどうなるかを考えると駄目なことがわかりやすい.(と思う)

C++によるスパゲッティなソースコード (DIV1用)
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll ab(ll x){ if(x<0) return -x; return x; }
class CorrectMultiplication {
public:
ll getMinimum(ll a, ll b, ll c) {
  ll i,j,k;
  ll A, B, C;
  ll Bt;
  ll res = 1000000000000000000LL, tmp;

  if(a > b) k = a, a = b, b = k;

  REP(A,1,100000){
    Bt = c / A;
    REP(B, Bt-5, Bt+6){
      if(B <= 0) continue;
      C = A*B;
      tmp = ab(A-a) + ab(B-b) + ab(C-c);
      if(res > tmp) res = tmp;
    }
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2147-f0b8637e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。