2017-01-16

POJ 2601 Simple calculations

POJ 二分探索

問題

$a_i = (a_{i-1} + a_{i+1})/2 - c_i$ という漸化式の数列がある。 $a_0,a_{n+1},c_1,..c_n$ が与えられるので $a_1$ を求めよ。

やりかた

(たぶん嘘解法)
$a_1$ に対して $a_{n+1}$ がmonotonicalに変化するから $a_1$ に関して二分探索すればいいんじゃまいか(・∀・)!!
で通ってしまった。よく考えるとmonotonicalじゃないような。
実験すると一般項がわかるのでそれでやるのがいいと思う。

以下ソース。

//嘘解法っぽい
int n;
double b, a[3010];
double c[3010];
int main(int argc, char **argv){
  scanf("%d", &n);
  scanf("%lf", &a[0]);
  scanf("%lf", &b);
  for(int i = 1; i <= n; i++)
    scanf("%lf", c + i);
  
  double ub = 1001, lb = -1001;
  for(int i = 0; i < 100; i++){
   a[1] = (ub + lb) / 2;
   for(int i = 2; i <= n + 1; i++)
     a[i] = 2.0 * a[i - 1] - a[i - 2] + 2.0 * c[i - 1];
   if(b > a[n + 1]) lb = a[1];
   else ub = a[1];
  }
  printf("%.2lf\n", a[1]);
  return 0;
}

2017-01-16

POJ 2505 A multiplication game

POJ ゲーム深さ優先探索

問題

StanとOllieが掛け算ゲームをして遊ぶ。数字を1から始めて毎ターン2から9までの好きな数字をかけていく。数字が与えられた数n以上になった時、そのときのプレーヤが勝ちとする。Stanからプレーを始めて交互に行う。両者が最適にプレーする時、必勝はどちらか答えよ。

やりかた

ゲームの木の探索。

今の数字から行くことのできる数字が全て相手に必勝形であれば自分はどうやっても必敗（後手必勝形）
今の数字から行くことのできる数字に一つでも相手が必敗になる数字があれば自分はそこに行けば勝てるので必勝（先手必勝形）

というルールでゲーム木を探索すればいい。
メモ化しないと時間が厳しかったので20000000未満の数字に限ってメモ化した。

以下ソース。

const int MAXN = 20000000;

long long N;
char memo[MAXN];
bool rec(long long p){
  if(p >= N) return false;
  if(p < MAXN && memo[p] != -1) return memo[p];
  bool a = true;
  for(int i = 2; i <= 9; i++) a &= rec(p * i);
  if(p < MAXN) memo[p] = !a;
  return !a;
}

int main(int argc, char **argv){
  while(cin >> N){
    memset(memo, -1, sizeof(memo));
    cout << (rec(1) ? "Stan" : "Ollie") << " wins." << endl;
  }
  return 0;
}

2017-01-15

POJ 2499 Binary Tree

POJ

問題

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

やり方

xの方が大きいとしておく。まず右側に動くことになるが、この時連続して $\lfloor x / y \rfloor$ 回動くことができる。移動後のノードは(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;
}

2017-01-14

POJ 2613 Choose and divide

POJ 小数を扱う

問題

二項係数同士の除算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;
}

2017-01-12

POJ 1450 Gridland

POJ

問題

デカルト座標上に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;
}

2017-01-12

POJ 2248 Addition Chains

POJ 深さ優先探索

問題

要素が一つだけの数列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;
}

2017-01-11

POJ 2348 Euclid's Game

POJ ゲーム

問題

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

やりかた

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

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

以下ソース。

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;
}