POJ 1753 Flip Game
問題
4x4のオセロの盤面が与えられる。盤上の石を一つひっくり返すと4近傍の石もひっくり返るとする。すべての石が同じ色になるために必要なひっくり返す動作の最小回数を求めよ。どうひっくり返しても達成できない場合は"Impossible"を出力せよ。
やりかた
同じ石を2回以上ひっくり返す必要はないので16個の石をそれぞれひっくり返すかどうかのパターンを全列挙して調べれば十分間に合う。
以下ソース。
void flip(int &T, int idx){ T ^= 1 << idx; if(idx + 4 < 16) T ^= 1 << (idx + 4); if(idx - 4 >= 0) T ^= 1 << (idx - 4); if(idx % 4 != 0) T ^= 1 << (idx - 1); if(idx % 4 != 3) T ^= 1 << (idx + 1); } int main(int argc, char **argv){ int S = 0; for(int i = 0; i < 4; i++){ string s; cin >> s; for(int j = 0; j < 4; j++) if(s[j] == 'w') S |= (1 << (4 * i + j)); } int ans = INF; for(int M = 0; M < 1 << 16; M++){ int T = S, cnt = 0; for(int i = 0; i < 16; i++){ if(!(M >> i & 1)) continue; cnt++; flip(T, i); } if(T == 0 || (1 << 16) - 1 == T) ans = min(ans, cnt); } if(ans == INF) cout << "Impossible" << endl; else cout << ans << endl; return 0; }
POJ 3869 Headshot
問題
リボルバー式の拳銃があり、シリンダー内の弾の装填の情報が与えられる。ロシアンルーレットで遊ぶとして、どの薬室からスタートしたかわからないが相手の手番では発砲しなかった。次の番はあなたで、そのまま打つか、シリンダーをランダムに回転させてから打つか選ぶことができる。どちらが発砲しない可能性が高いか答えよ。
やりかた
やるだけ
打つ前にランダムに回転させると、発砲しない確率は(0の数)/(薬室の数)になる。一方そのまま打つ場合では、相手が打ったあとなので銃身の薬室はこの時点で0という状況下である。その次の薬室が1なら発砲してしまうし、0なら発砲しない。なので発砲しない確率は(00という並びの個数/0の個数)になる。この大小を比べる。
以下ソース。
int main(int argc, char **argv){ string s; while(cin >> s){ int zero = count(ALL(s), '0'); int condition = 0, situation = 0; for(int i = 0; i < s.size(); i++){ if(s[i] == '0'){ condition++; if(s[(i + 1) % s.size()] == '0') situation++; } } if(zero * condition > situation * s.size()) cout << "ROTATE" << endl; else if(zero * condition < situation * s.size()) cout << "SHOOT" << endl; else cout << "EQUAL" << endl; } return 0; }
POJ 2626 Chess
問題
チェス大会のチーム編成を考えたい。各チェスプレーヤについて、白チームとして戦った場合の強さと黒チームとして戦った場合の強さの2つが与えられる。30人以上のプレーヤの強さが与えられる。これらプレーヤから選抜で白チーム15人、黒チーム15人の編成を行うとき、強さの総和を最大化せよ。ただし、一人が両チームに所属することはできない。
やりかた
DP。
dp[i][w][b]:=(i人目まで見たときに白チームにw人、黒チームにb人選抜したときの最大値)で動的計画法。
以下ソース。
int dp[1010][16][16]; vector<pair<int, int> > p; int rec(int idx, int w, int b){ if(idx == p.size()){ if(w == 15 && b == 15) return 0; else return -INF; } if(dp[idx][w][b] != -1) return dp[idx][w][b]; int ret = -INF; ret = max(ret, rec(idx + 1, w, b)); if(w < 15) ret = max(ret, rec(idx + 1, w + 1, b) + p[idx].first); if(b < 15) ret = max(ret, rec(idx + 1, w, b + 1) + p[idx].second); return dp[idx][w][b] = ret; } int main(int argc, char **argv){ int a, b; while(cin >> a >> b) p.push_back(make_pair(a, b)); FILL(dp, -1); cout << rec(0, 0, 0) << endl; return 0; }
POJ 2253 Frogger
問題
x,y座標が幾つか与えられる。0番目の点から1番目の点に向かって、直接、もしくはその他の点を経由しながら移動する。点から点へのジャンプにかかるコストは点と点のユークリッド距離で表される。移動中にかかる最長のコストを最小化せよ。
やりかた
二分探索で候補となるコストを定めて、そのコストで移動可能かチェックした。チェックの仕方は、候補となるコスト以下のジャンプ(辺)をすべて列挙し、その辺の移動で0番目から1番目に移動できるか調べる方法をとった。
以下汚いソース。
struct path{ int from, to; double d; path(){} path(int from, int to, double d) : from(from), to(to), d(d) {} bool operator<(const path &r)const{ return d < r.d; } }; int main(int argc, char **argv){ int N; int idx = 0; while(scanf("%d", &N), N){ int x[200], y[200]; for(int i = 0; i < N; i++) cin >> x[i] >> y[i]; vector<path> pa; for(int i = 0; i < N; i++) for(int j = i; j < N; j++) pa.push_back(path(i, j, sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])))); sort(ALL(pa)); double ub = 1e10, lb = 0.0; for(int i = 0; i < 100; i++){ double mid = (ub + lb) * 0.5; bool d[200][200]; FILL(d, false); for(int i = 0; i < pa.size(); i++) if(mid >= pa[i].d + EPS) d[pa[i].from][pa[i].to] = d[pa[i].to][pa[i].from] = true; queue<int> Q; Q.push(0); vector<bool> vis(N, false); vis[0] = true; bool reach = false; while(!Q.empty()){ int p = Q.front(); Q.pop(); if(p == 1){ reach = true; break; } for(int i = 0; i < N; i++){ if(d[p][i] && !vis[i]){ Q.push(i); vis[i] = true; } } } if(reach) ub = mid; else lb = mid; } printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++idx, ub); } return 0; }
POJ 2033 Alphacode
問題
アルファベット大文字からなる平文に対し、A=1、B=2、…、Z=26と置き換える暗号化を行う。この暗号文は一意に復号化できない可能性がある。暗号文が与えられるので何通りの復号化があるか求めよ。
やりかた
DP。
dp[i]:=(i桁目までの復号化パターン数)とすると、今見ている桁だけ使った置換と、一つ前の桁も使った置換がありうるのでそれらの和になる。
dp[i + 1] = dp[i] + dp[i - 1]
ただし、今見ている桁が0の場合と、一つ前の桁が0の場合は例外なので注意。
以下ソース。
int main(int argc, char **argv){ string s; while(cin >> s){ if(s == "0") break; ll dp[1000000]; FILL(dp, 0); dp[0] = 1; for(int i = 0; i < s.size(); i++){ //今見ている桁だけ使った置換 if(s[i] != '0') dp[i + 1] += dp[i]; //一つ前の桁も使った置換が可能な場合 if(i - 1 >= 0 && (s[i - 1] - '0' != 0) && (s[i] - '0') + 10 * (s[i - 1] - '0') <= 26) dp[i + 1] += dp[i - 1]; } cout << dp[s.size()] << endl; } return 0; }
POJ 2121 Inglish-Number Translator
問題
アルファベット表記された数字を英数字に変換して表示せよ。
やりかた
数字をthousand未満、thousandの桁、millionの桁に分けて各桁を英数字に直して、桁の数字をかけて足し合わせた。
以下ソース。
int main(int argc, char **argv){ map<string, int> p; p["negative"] = -1; p["zero"] = 0; p["one"] = 1; p["two"] = 2; p["three"] = 3; p["four"] = 4; p["five"] = 5; p["six"] = 6; p["seven"] = 7; p["eight"] = 8; p["nine"] = 9; p["ten"] = 10; p["eleven"] = 11; p["twelve"] = 12; p["thirteen"] = 13; p["fourteen"] = 14; p["fifteen"] = 15; p["sixteen"] = 16; p["seventeen"] = 17; p["eighteen"] = 18; p["nineteen"] = 19; p["twenty"] = 20; p["thirty"] = 30; p["forty"] = 40; p["fifty"] = 50; p["sixty"] = 60; p["seventy"] = 70; p["eighty"] = 80; p["ninety"] = 90; p["hundred"] = 100; p["thousand"] = 1000; p["million"] = 1000000; char c[400]; while(gets(c)){ string s(c); if(s.empty()) break; stringstream ss(s); vector<string> v; while(ss >> s) v.push_back(s); reverse(ALL(v)); //桁ごとに入力を割り振る vector<string> num[4]; int digit = 0; for(int i = 0; i < v.size(); i++){ if(v[i] == "hundred" && digit < 1) digit = 1; else if(v[i] == "thousand" && digit < 2) digit = 2; else if(v[i] == "million" && digit < 3) digit = 3; else num[digit].push_back(v[i]); } //各桁について数字を計算 int ans = 0; int sign = 1; for(int i = 0; i < 4; i++){ int base = 1, val = 0; for(int j = 0; j < num[i].size(); j++){ if(p[num[i][j]] == -1) sign = -1; else if(p[num[i][j]] < 100){ val += base * p[num[i][j]]; }else{ base = p[num[i][j]]; } } if(i == 0) ans += val; if(i == 1) ans += 100 * val; if(i == 2) ans += 1000 * val; if(i == 3) ans += 1000000 * val; } cout << sign * ans << endl; } return 0; }
POJ 1265 Area
問題
ロボットが2次元座標上で原点から出発して左回りに動いて再び原点に戻ってくる。動作は格子点から格子点への直線運動の繰り返しで行われ、毎回の移動量dx, dyが入力として与えられる。この一周の動作で囲われた領域の内部にある格子点の総数、動作した直線上の格子点の総数、領域の面積を求めよ。なおロボットは過去に自分が通過した線を交差したり、接触するような動作はしない。
やりかた
ある直線動作(線分)の上にある格子点数はgcd(dx, dy)+1で求まる。なので一連の動作全体ではとなる。
領域は多角形になるので多角形の面積は頂点の座標(位置ベクトル)が分かればで求まる。(ただしi=M-1のときi+1は0にする)
辺上の格子点数と領域の面積がわかれば、領域内の格子点数についてはピックの定理からすぐ求まる。
以下ソース。
int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);} int main(int argc, char **argv){ int N; scanf("%d", &N); for(int t = 1; t <= N; t++){ int x[101], y[101]; int M; scanf("%d", &M); for(int i = 0; i < M; i++) scanf("%d %d", &x[i], &y[i]); int E = 0; double A = 0.0; for(int i = 0; i < M; i++) E += gcd(abs(x[i]), abs(y[i])); for(int i = 1; i < M; i++) x[i] += x[i - 1], y[i] += y[i - 1];//方向ベクトルから位置ベクトルに変換 for(int i = 0; i < M; i++) A += 0.5 * (x[i] * y[(i + 1) % M] - y[i] * x[(i + 1) % M]); A = fabs(A); printf("Scenario #%d:\n", t); printf("%d %d %.1f\n\n", (int)(A + 1 - 0.5 * E), E, A); } return 0; }