POJ 1505 Copying Books

問題

要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。ただし複数の分割方法がある場合には、分割したはじめの数列の和のほうからなるべく小さくなるようにという方針で分割せよ。

やりかた

分割した数列中の和の最大値をXとすると、Xを大きくすると分割数kは小さくなる。なので二分探索で最適な和は計算することができる。
ただしこの問題は頭の方から小さく分割しろという条件が面倒。これには、数列を後ろの方から条件を満たしつつ、貪欲に大きく分割した後、余った分割数分、今度は数列の頭の方から細かく分割していくことで実現できる。

例えば2ケース目の
5 4
100 100 100 100 100
という入力では最小の最大和は200と求まるので、後ろのからひとまず
100 / 100 100 / 100 100
と分割する。分割数が1つ余っているので、今度は頭の方から分割できるところを見つけ次第余った数だけ分割すると答えになる。
100 / 100 / 100 / 100 100

以下ソース。

int m, k;
vector<ll> page;

int C(ll v){
  ll sum = 0;
  int cnt = 0;
  for(int i = m - 1; i >= 0; i--){
    if(v < page[i]) return INF;
    if(sum + page[i] <= v){
      sum += page[i];
    }else{
      cnt++;
      sum = page[i];
    }
  }
  return cnt;
}

int main(int argc, char **argv){
  int n;
  cin >> n;
  while(n--){
    cin >> m >> k;
    page.resize(m);

    ll ub = 0LL, lb = 0LL, div;
    for(int i = 0; i < m; i++){ 
      cin >> page[i];
      ub += page[i];
    }
    
    while(lb < ub){
      ll mid = (ub + lb) / 2;
      div = C(mid);
      if(div + 1 <= k) ub = mid;
      else lb = mid + 1;
    }
    reverse(ALL(page));
    ll sum = 0, rem = k - C(ub) - 1;
    vector<int> a;
    //cout << ub << " " << C(ub) << endl;
    for(int i = 0; i < page.size(); i++){
      if(sum + page[i] > ub){
	sum = 0;
	a.push_back(-1);
      }
      sum += page[i];
      a.push_back(page[i]);
    }
    reverse(ALL(a));
    vector<int> b;
    for(int i = 0; i < a.size(); i++){
      b.push_back(a[i]);
      if(i < a.size() - 1){
	if(rem && (a[i] != -1 && a[i + 1] != -1)){
	  rem--;
	  b.push_back(-1);
	}
      }
    }
    for(int i = 0; i < b.size(); i++)
      if(b[i] == -1) cout << "/ ";
      else cout << b[i] << " ";
    cout << endl;
  }
  return 0;
}

POJ 1985 Cow Marathon

問題

無向木の情報が与えられる。同じ辺を2度辿らないように頂点間を移動する時、もっとも距離の遠い2点間の距離を求めよ。

やりかた

無向木の直径を求める問題に他ならない。直径の求め方は、てきとうな頂点から深さ優先探索を始めて最遠の頂点uを求める。つづいてその最遠の頂点uから始めて、最遠の頂点vを求める。するとu-vの頂点間が最遠の距離になっている。

以下ソース。

struct edge{
  int to, cost;
};

vector<edge> g[40001];
int dist[40001];

void dfs(int cur, int prev, int cost){
  dist[cur] = cost;
  for(int i = 0; i < g[cur].size(); i++)
    if(g[cur][i].to != prev) 
      dfs(g[cur][i].to, cur, cost + g[cur][i].cost);
}

int main(int argc, char **argv){
  int V, E;
  scanf("%d %d", &V, &E);

  for(int i = 0; i < E; i++){
    int s, t, c; char dir;
    scanf("%d %d %d %c", &s, &t, &c, &dir);
    g[s - 1].push_back((edge){t - 1, c});
    g[t - 1].push_back((edge){s - 1, c});
  }

  fill(dist, dist + V, 0);
  dfs(0, -1, 0);;

  int u = max_element(dist, dist + V) - dist;
  fill(dist, dist + V, 0);
  dfs(u, -1, 0);
  printf("%d\n", *max_element(dist, dist + V));
  return 0;
}

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