POJ 1855 Mint
問題
数種類の長さの棒がある。各種類とも棒は無尽蔵にあるとして良い。棒をつなぎ合わせて4本足の机を作る。各足は同じ種類の木を使い、4本の足の長さが揃うように作る時、決められた高さ以下で作れる最高の高さと、決められた高さ以上で作れる最小の高さを求めよ。
やりかた
ある4種類を選んだ時、その4種類の長さの公倍数のうち、決められた高さ以下で最高になるものと、高さ以上で最低になるものを計算する。すべての4種類のパターンについてこの計算を行い、最高値と最小値を求める。
長さの種類数がが50以下なので4重ループで通る。
以下ソース。
inline ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a % b); } inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; } int e[51]; int main(int argc, char **argv){ int N, M; while(cin >> N >> M, N + M){ for(int i = 0; i < N; i++) cin >> e[i]; sort(e, e + N); int v[4]; while(M--){ ll T; cin >> T; ll miv = 0, mav = LLINF; for(int a = 0; a < N; a++){ for(int b = a + 1; b < N; b++){ for(int c = b + 1; c < N; c++){ for(int d = c + 1; d < N; d++){ v[0] = e[a], v[1] = e[b], v[2] = e[c], v[3] = e[d]; ll g = v[0]; for(int j = 0; j < 4; j++) g = lcm(g, v[j]); miv = max(miv, T / g * g); mav = min(mav, (T + g - 1) / g * g); } } } } cout << miv << " " << mav << endl; } } return 0; }
POJ 1905 Expanding Rods
問題
長さLの鉄線をn度で熱すると長さがL*(1+n*C)に変化する。Cは膨張係数である。この鉄線を向かい合わせの壁に取り付けて熱すると膨張して弧を描くようにしなる。熱したときの鉄線の中心部の縦方向への変位を求めよ。
やりかた
弧になったときの弧長をL'、中心角をθとし、半径をxとすると答えはで求められる。弧長L'はと計算でき、扇形の半径ともともとの鉄線の長さLとはという関係がある。これらからと変形する。ここからθを求めるには二分探索を使う。
θが求まればあとは代入して計算するだけ。
精度が少し厳しいのでいつもより多めにループした。
以下ソース。
int main(int argc, char **argv){ double l, n, c; while(cin >> l >> n >> c){ if(l < 0 && n < 0 && c < 0) break; double ub = acos(( double)-1), lb = 0; for(int i = 0; i < 10000; i++){ double mid = (ub + lb) * 0.5; double x = sin(0.5 * mid) / mid; double y = 0.5 / (1.0 + n * c); if(x > y) lb = mid; else ub = mid; } cout.precision(3); cout.setf(ios::fixed); cout << ((1.0 - cos(0.5 * ub)) * l * (1.0 + n * c) / ub) << endl; } return 0; }
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; }
ここまで書いたが、蟻本によれば
という漸化式が成り立つのでもっと高速に計算できる。なるほど~。