読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 3233 Matrix Power Series

問題

nxnの行列Aが与えられる。S=A+A^2+A^3+...+A^kを計算し、各要素をmで割ったあまりを求めよ。

やりかた

行列の累乗は繰り返し二乗でできるとしても単純にやったら確実にTLEする。なのでうまく分割統治しつつメモ化しておくことで通すことができる。

数列を左右に二分割する。すると
A + A^2 + A^3 + A^4 + A^5 + A^6 + A^7 + A^8 = A(E + A + A^2 + A^3) + A^4(E + A + A^2 + A^3)
となり、(E + A + A^2 + A^3)という構造が左右に現れる。この構造はさらにE(E + A) + A^2(E + A)と分割できる。これを繰り返して、要素数が一つ(=E)になるまで分割してから統合していくことで計算ができる。分割後の要素数に対するメモ化を行うことで無駄な計算を省く。

最初何度もTLEしたので、要素数が奇数の場合でも左右の分割数を同じにしてメモ化に引っかかりやすくしてみたり、行列の計算結果を戻り値で返さずにグローバル変数に入れて参照する、などしてようやく2100MS程度で通せた。。

以下きたないソース。

typedef vector<int> vec;
typedef vector<vec> mat;

mat add_res;

int MOD;

inline mat identity(int n){
  mat E(n, vec(n, 0));
  for(int i = 0; i < n; i++) E[i][i] = 1;
  return E;
}

inline void add(const mat &A, const mat &B){
  int N = A.size(), M = A[0].size();
  for(int n = 0; n < N; n++)
    for(int m = 0; m < M; m++)
      add_res[n][m] = ((A[n][m] + B[n][m]) % MOD);
}

inline mat mult(const mat &A, const mat &B){
  int N = A.size(), M = B.size(), L = B[0].size();
  mat C(N, vec(L, 0));
  for(int n = 0; n < N; n++)
    for(int l = 0; l < L; l++)
      for(int m = 0; m < M; m++)
	C[n][l] = ((C[n][l] + A[n][m] * B[m][l]) % MOD);
  return C;
}

inline mat pow(const mat &A, int p){
  mat R = identity(A.size());
  mat B = A;
  while(p){
    if(p & 1) R = mult(R, B);
    B = mult(B, B);
    p >>= 1;
  }
  return R;
}

map<int, mat> memo;

mat rec(const mat &A, int w){
  if(w == 1) return identity(A.size());
  if(memo.count(w)) return memo[w];

  mat L = rec(A, w / 2);
  mat R = L;
  mat B = pow(A, w / 2);
  R = mult(B, R);
  
  add(L, R);

  //要素数が奇数の場合は(0,1,..,w/2-1)(w/2,...,w-2), w という分割にする
  //ここでは最後のw番目の行列A^(w-1)の計算を個別に行っている
  if(w % 2) add(add_res, pow(A, w - 1));
  return memo[w] = add_res;
}

int main(int argc, char **argv){
  int n, k, m;
  scanf("%d %d %d", &n, &k, &m);
  MOD = m;
  mat A = identity(n);
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      scanf("%ld", &A[i][j]);
  
  add_res = identity(n);

  mat ans = rec(A, k);
  ans = mult(A, ans);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      printf("%ld ", ans[i][j] % MOD);
    }
    printf("\n");
  }
  return 0;
}

ここまで書いたが、蟻本によれば
 
\left(
\begin{array}{c}
A^k \\
\hline
S^k
\end{array}
\right)
=
\left(
\begin{array}{c|c}
A & 0 \\
\hline
I & I
\end{array}
\right)
\left(
\begin{array}{c}
A^{k-1} \\
\hline
S^{k-1}
\end{array}
\right)
という漸化式が成り立つのでもっと高速に計算できる。なるほど~。

POJ 2601 Simple calculations

問題

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

POJ 2505 A multiplication game

問題

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

POJ 2499 Binary Tree

問題

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

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;
}
しょげないでよBaby 眠れば治る