POJ 3510 A Tale from the Dark Side of the Moon

問題

文字列が一行ずつ与えられる。一行ごとに以下の処理を行って出力せよ。

• アルファベット小文字とスペース以外は削除
• "dd"という文字列があったら"p"に変換（"ddd"という入力はないものとする）
• "ei"という文字列があったら"ie"に変換（ただし直前の文字が'c'であれば変換しない）
• "pink"という文字列があったら"floyd"に変換
• "EOF"という文字列があったらそこで処理を中断して終了

やりかた

ただやるだけではあるけど、それぞれの処理を初期の文字列に対して並行して行う必要がある。文字列を逐次的に処理すると変換後の文字列を再度変換してしまうので注意。例えば"ddink"は"pink"に変換されるが、逐次的に変換してしまうと"ddink" -> "pink" -> "floyd" になってしまう。"eiieii"なども注意。"iieiieは間違いで"正しくは"ieiiei"になる。
あとEOFは文字列の途中で出てくることがあり、その場合はそこまでを変換して出力する。

以下ソース。

void strReplace(string &str, const string &from, const string &to){
  string::size_type pos = 0;
  while((pos = str.find(from, pos)) != string::npos){
    str.replace(pos, from.length(), to);
    pos += to.length();
  }
}

int main(int argc, char **argv){
  string s;
  while(getline(cin, s)){
    int idx = s.find("EOF");
    bool final = false;
    if(idx != string::npos){
      s = s.substr(0, idx);
      final = true;
    }

    strReplace(s, "dd", "dddpddd");
    strReplace(s, "pink", "floyd");
    strReplace(s, "dddpddd", "p");

    for(int i = 1; i < s.size(); i++){
      if(s[i - 1] == 'e' && s[i] == 'i'){
	if(i == 1 || (2 <= i && s[i - 2] != 'c')){
	  s[i - 1] = 'i', s[i] = 'e'; i++;
	}
      }
    }

    for(unsigned char c = 0; c < 0xff; c++){
      if(('a' <= c && c <= 'z') || c == ' ') continue;
      string d; d += c;
      strReplace(s, d, "");
    }
    cout << s << endl;
    if(final) break;
  }
  return 0;
}

今見ると変数名にfinalとかつけてしまった。もしPOJがc++11だったらCompile Errorになってた。

POJ 1129 Channel Allocation

問題

頂点と辺の情報が与えられる。最小で何色で頂点を塗ることができるか答えよ。

やりかた

四色定理から必ず4以下になる。
色を数値で管理して、深さ優先探索でグラフを探索する。探索中に次に訪れる点に隣接している点の色で使っていない色のうち、最も値の小さい色を次に訪れる点の色にすればいい。すべての点で探索が終わったら使った色の数を数える。

以下ソース。

int color[30];
bool adj[30][30];
int n;

int ret(int idx){
  bool used[4] = {false};
  for(int i = 0; i < n; i++)
    if(adj[idx][i] && color[i] != -1)
      used[color[i]] = true;
  for(int i = 0; i < 4; i++)
    if(!used[i]) return i;
}
void dfs(int i){
  for(int j = 0; j < n; j++){
    if(!adj[i][j] || color[j] != -1) continue;
    color[j] = ret(j);
    dfs(j);
  }
  return;
}

int main(int argc, char **argv){
  while(scanf("%d", &n), n){
    FILL(color, -1);
    FILL(adj, false);
    for(int k = 0; k <n; k++){
      char s[30]; scanf("%s", s);    
      for(int i = 2; i < strlen(s); i++)
	adj[s[0] - 'A'][s[i] - 'A'] = true;
    }

    for(int i = 0; i < n; i++){
      if(color[i] != -1) continue;
      color[i] = 0;
      dfs(i);
    }

    set<int> r(color, color + n);
    if(r.size() == 1)
      printf("%d channel needed.\n", r.size());
    else
      printf("%d channels needed.\n", r.size());
  }
  return 0;
}

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

ここまで書いたが、蟻本によれば

という漸化式が成り立つのでもっと高速に計算できる。なるほど～。

POJ 2601 Simple calculations

問題

という漸化式の数列がある。が与えられるのでを求めよ。

やりかた

(たぶん嘘解法)
に対してがmonotonicalに変化するからに関して二分探索すればいいんじゃまいか(・∀・)!!
で通ってしまった。よく考えると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の方が大きいとしておく。まず右側に動くことになるが、この時連続して回動くことができる。移動後のノードは(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;
}