POJ 2499 Binary Tree

問題

(1, 1)という値を根に持つ完全二分木があり、各ノード(仮に(a, b)とする)からは左に(a + b, b)という値を持つ子、右に(a, a + b)という値を持つ子が伸びている。
(x, y)というノードから親を辿りながら根まで行くときに左側に移動する回数と右側に移動する回数をそれぞれ答えよ。

やり方

xの方が大きいとしておく。まず右側に動くことになるが、この時連続して回動くことができる。移動後のノードは(x % y, y)になり今度は左側に動くことになる。これもいま右側に動いたのとやることは一緒。これをどちらかが0になるまで繰り返す。yの方が大きいときでもやることは同じ。
これは結局ユークリッドの互除法をやっていることになる。ただし、この方法では最後に(1,0)か(0,1)という状態で終わってしまうので(1,1)にするためには最後に移動した方向の回数を一つ引かなくてなならない。

最大公約数を求める処理の回数を数えているわけなので、これを繰り返すと(1, 1)にいたるということは(x, y)の最大公約数は(1, 1)の最大公約数に同じということになる。ゆえにx,yは互いに素ということが根にいたるための条件。

以下ソース。

int main(int argc, char **argv){
  int t;
  scanf("%d", &t);
  for(int i = 1; i <= t; i++){
    int a, b, l = 0, r = 0;
    scanf("%d %d", &a, &b);

    int idx = 0;
    while(a * b){
      if(idx++ % 2 == 0){
	l += a / b;
	a %= b;
	if(a == 0) l--;
      }else{
	r += b / a;
	b %= a;
	if(b == 0) r--;
      }
    }
    printf("Scenario #%d:\n", i);
    printf("%d %d\n\n", l, r);
  }
  return 0;
}

POJ 2613 Choose and divide

問題

二項係数同士の除算C(p,q)/C(r,s)を行い、小数点第五位までを出力せよ。p,q,r,sは10000未満で、答えは常に1e7を超えないとしてよい。

やりかた

素直にやると精度が落ちて誤差死する。なので優先度付キューを2つ用意して式の分母と分子の数字をそれぞれ入れていき、入れ終わったらそれぞれ大きい方から取り出して割るという風にして精度が落ちるのを防いだ。

以下ソース。

int main(int argc, char **argv){
  double p, q, r, s;
  while(scanf("%lf %lf %lf %lf", &p, &q, &r, &s) != EOF){
    priority_queue<int> nume, deno;
    for(int i = p; i >= 1; i--) nume.push(i);
    for(int i = s; i >= 1; i--) nume.push(i);
    for(int i = r - s; i >= 1; i--) nume.push(i);

    for(int i = q; i >= 1; i--) deno.push(i);
    for(int i = p - q; i >= 1; i--) deno.push(i);
    for(int i = r; i >= 1; i--) deno.push(i);

    double ans = (double)1.0;
    while(!nume.empty()){
      ans *= (double)nume.top();
      ans /= (double)deno.top();
      nume.pop(); deno.pop();
    }
    printf("%.5lf\n", ans);
  }
  return 0;
}

POJ 1450 Gridland

問題

デカルト座標上にnxmのグリッドがある。グリッドの格子点では上下左右の格子点に加え対角線方向のグリッドにも移動できる。このnxmの格子点について巡回セールスマン問題を解け。

やりかた

巡回セールスマン問題なのでnxm回の辺の移動がある。なので問題は8方向の移動回数である。これは少し実験するとわかるが、n,mの少なくとも一方が偶数であれば上下左右の移動のみで完結でき、そうでなければ一回だけ対角線方向の移動を入れることで完結できる。

以下ソース。

int main(int argc, char **argv){
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    int H, W;
    scanf("%d %d", &H, &W);
    printf("Scenario #%d:\n", i);
    printf("%.2lf\n\n", H * W + (H * W % 2 ? sqrt((double)2) - 1 : 0));
  }
  return 0;
}

POJ 2248 Addition Chains

問題

要素が一つだけの数列a(a[0] = 1)からはじめて、数列a中の任意の2つの要素の和を取り、それが最終項より大きい場合に最終項の後ろにくっつけるという操作を繰り返して、入力として与えられるnをつくりたい。
操作回数が最小であるときの、最終的な数列を出力せよ。複数パターンある場合はどれか一つで良い。

やりかた

なにかうまい方法があるだろうと思ったが、調べるとshortest addition chain（最短加法鎖）問題といってNP完全に属する問題のようだ。
Addition chain - Wikipedia
A003313 - OEIS

ただ今回は入力が小さいので全探索でも通る。
ノードが数列になっている多分木（探索のイメージ）を、ある深さ以上は調べないという枝刈りを入れて探索したら通すことができた。

BFSのほうが直感的だったので、最初はvectorに入れた数列を状態としてBFSで頑張ったけど何度やってもTLEした。探索しているノードのみ数列を持つDFSに切り替えたら一瞬だった。

以下ソース。

int n;
int arr[12];
vector<int> ans[110];

void rec(int idx){
  int last = arr[idx];
  if(last > 100 || idx > 9) return;
  if(ans[last].size() > idx + 1){
    ans[last].resize(idx + 1);
    for(int i = 0; i < idx + 1; i++) ans[last][i] = arr[i];
  }

  for(int i = 0; i <= idx; i++){
    arr[idx + 1] = arr[idx] + arr[i];
    rec(idx + 1);
  }
  return;
}

int main(int argc, char **argv){
  fill(ans, ans + 101, vector<int>(100, 0));
  arr[0] = 1;
  rec(0);
  while(cin >> n, n){
    for(int i = 0; i < ans[n].size(); i++) 
      cout << ans[n][i] << " ";
    cout << endl;
  }
  return 0;
}

POJ 2348 Euclid's Game

問題

2つの自然数が与えられ、この自然数についてStanとOllieがゲームを行う。プレーヤは大きい方の数から小さい方の数の倍数を引いて相手プレーヤに渡すことができる。ただし、大きい方から小さい方の倍数を引いて残った数は0以上にならなければいけない。最初にどちらかの数を0にしたプレーヤが勝ちとする。Stanからプレーを始めたとして両者が最適にプレーする時、必勝なのはどちらか。

やりかた

ちょっと前にやって放置していた問題。さっきぼんやり考えていたらできた。

大きい方から引くことのできる小さい方の数の倍数の数は になる。つまり、大きい方から回だけ小さい数を引くことができるということ。その後数の大小は入れ替わる。
大きい方から小さい方の倍数を引く操作はの石がある山から任意の個数の石を取る操作と考えることができるので、このゲームは複数の山から石を取るゲームで、取る山に順序が有るバージョンとも考えられる。
このゲームはあるターンで複数の石を含む山に当たったときに、その山より一つ後の山が後手から始まる場合自分が必敗なら今の山を一つ残して後手に渡すと必勝形に変えられる。そうでなければ今の山は全部取ってしまい、次の山を後手から始めさせればいい。この考えで行くと、結局最初に複数の山に当たるプレーヤが必敗の状態を覆せるので必勝ということになる。

以下ソース。

int main(int argc, char **argv){
  int a, b;
  while(cin >> a >> b, a){
    if(a < b) swap(a, b);
    int turn = 0;
    while(b){
      if(a % b == 0 || a / b >= 2) break;
      a %= b;
      swap(a, b);
      turn++;
    }
    cout << (turn % 2 ? "Ollie wins" : "Stan wins") << endl;
  }
  return 0;
}

POJ 1917 Automatic Poetry

問題

"s1<s2>s3<s4>s5" という形式の文字列が与えられる。もう一つ "s..." という形式の文字列が与えられる。元の文字列からカッコを取り除いた文字列と、もう一つの文字列を "ss4s3s2s5" という形式に直したものを出力せよ。

やりかた

Javaであれば正規表現を使えるので楽。といってもC++でも難しいことはない。

以下ソース。

int main(int argc, char **argv){
  int N;
  cin >> N;
  cin.ignore();
  while(N--){
    string s, t;
    getline(cin, s);
    getline(cin, t);
    
    int idx = 0;
    string a[5];
    for(int i = 0; i < s.length(); i++){
      if(s[i] == '<' || s[i] == '>') idx++; //カッコが来るごとに文字は分かれる
      else a[idx] += s[i];
    }
    cout << a[0] << a[1] << a[2] << a[3] << a[4] << endl;
    for(int i = 0; i < t.length(); i++){
      if(t[i] == '.'){
	cout << a[3] << a[2] << a[1] << a[4] << endl;
	break;
      }else cout << t[i];
    }
  }
  return 0;
}

POJ 1384 Piggy-Bank

問題

複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうどE-Fになるように硬貨を取り出したときの価値の和を最小化せよ。硬貨は各種類とも無尽蔵にあるとしていい。

やりかた

dp[i]:=（重みの和がiであるときの価値の最小値）でDP。硬貨jの重みをw[j]、価値をv[j]とするとdp[i + w[j]] = min(dp[i + w[j]], dp[i] + v[j])で更新できる。

以下ソース。

int dp[10002];
int v[501], w[501];
int main(int argc, char **argv){
  int T; cin >> T;
  while(T--){
    int A, B; scanf("%d %d", &A, &B);
    B -= A;
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d %d", v + i, w + i);

    FILL(dp, INF);
    dp[0] = 0;
    for(int i = 0; i < B; i++){
      for(int j = 0; j < n; j++){
	int nxt = min(i + w[j], 10001);
	dp[nxt] = min(dp[nxt], dp[i] + v[j]);
      }
    }
    if(dp[B] != INF)
      printf("The minimum amount of money in the piggy-bank is %d.\n", dp[B]);
    else 
      printf("This is impossible.\n");
  }
  return 0;
}