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; }
POJ 2348 Euclid's Game
問題
2つの自然数が与えられ、この自然数についてStanとOllieがゲームを行う。プレーヤは大きい方の数から小さい方の数の倍数を引いて相手プレーヤに渡すことができる。ただし、大きい方から小さい方の倍数を引いて残った数は0以上にならなければいけない。最初にどちらかの数を0にしたプレーヤが勝ちとする。Stanからプレーを始めたとして両者が最適にプレーする時、必勝なのはどちらか。
やりかた
ちょっと前にやって放置していた問題。さっきぼんやり考えていたらできた。
大きい方から引くことのできる小さい方の数の倍数の数は になる。つまり、大きい方から
回だけ小さい数を引くことができるということ。その後数の大小は入れ替わる。
大きい方から小さい方の倍数を引く操作はの石がある山から任意の個数の石を取る操作と考えることができるので、このゲームは複数の山から石を取るゲームで、取る山に順序が有るバージョンとも考えられる。
このゲームはあるターンで複数の石を含む山に当たったときに、その山より一つ後の山が後手から始まる場合自分が必敗なら今の山を一つ残して後手に渡すと必勝形に変えられる。そうでなければ今の山は全部取ってしまい、次の山を後手から始めさせればいい。この考えで行くと、結局最初に複数の山に当たるプレーヤが必敗の状態を覆せるので必勝ということになる。
以下ソース。
int main(int argc, char **argv){ int a, b; while(cin >> a >> b, a){ if(a < b) swap(a, b); int turn = 0; while(b){ if(a % b == 0 || a / b >= 2) break; a %= b; swap(a, b); turn++; } cout << (turn % 2 ? "Ollie wins" : "Stan wins") << endl; } return 0; }
POJ 1917 Automatic Poetry
問題
"s1<s2>s3<s4>s5" という形式の文字列が与えられる。もう一つ "s..." という形式の文字列が与えられる。元の文字列からカッコを取り除いた文字列と、もう一つの文字列を "ss4s3s2s5" という形式に直したものを出力せよ。
やりかた
Javaであれば正規表現を使えるので楽。といってもC++でも難しいことはない。
以下ソース。
int main(int argc, char **argv){ int N; cin >> N; cin.ignore(); while(N--){ string s, t; getline(cin, s); getline(cin, t); int idx = 0; string a[5]; for(int i = 0; i < s.length(); i++){ if(s[i] == '<' || s[i] == '>') idx++; //カッコが来るごとに文字は分かれる else a[idx] += s[i]; } cout << a[0] << a[1] << a[2] << a[3] << a[4] << endl; for(int i = 0; i < t.length(); i++){ if(t[i] == '.'){ cout << a[3] << a[2] << a[1] << a[4] << endl; break; }else cout << t[i]; } } return 0; }
POJ 1384 Piggy-Bank
問題
複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうどE-Fになるように硬貨を取り出したときの価値の和を最小化せよ。硬貨は各種類とも無尽蔵にあるとしていい。
やりかた
dp[i]:=（重みの和がiであるときの価値の最小値）でDP。硬貨jの重みをw[j]、価値をv[j]とするとdp[i + w[j]] = min(dp[i + w[j]], dp[i] + v[j])で更新できる。
以下ソース。
int dp[10002]; int v[501], w[501]; int main(int argc, char **argv){ int T; cin >> T; while(T--){ int A, B; scanf("%d %d", &A, &B); B -= A; int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d %d", v + i, w + i); FILL(dp, INF); dp[0] = 0; for(int i = 0; i < B; i++){ for(int j = 0; j < n; j++){ int nxt = min(i + w[j], 10001); dp[nxt] = min(dp[nxt], dp[i] + v[j]); } } if(dp[B] != INF) printf("The minimum amount of money in the piggy-bank is %d.\n", dp[B]); else printf("This is impossible.\n"); } return 0; }
POJ 1606 Jugs
問題
ビーカーAとBの容量Ca、Cbが与えられる。ビーカーに水を入れる操作を行って、どちらかのビーカーに入っている水がNになるようにしたい。行ってよい操作は以下の6種類である。
- Aいっぱいに水を入れる
- Bいっぱいに水を入れる
- Aを空にする
- Bを空にする
- Aの水をBに入れる（Aが空になるかBが満杯になるまで）
- Bの水をAに入れる（Bが空になるかAが満杯になるまで）
かならず達成できるような入力が与えられるので達成するまでの操作を出力せよ。達成方法が複数ある場合は任意の1パターンを出力せよ。
やりかた
AとBのビーカーの水の量を状態として持たせたメモ化再帰で十分通った。
以下ソース。
int ca, cb, n; bool memo[1001][1001]; deque<int> ans; void rec(int a, int b, deque<int> t /* 操作の履歴 */){ if(a == n || b == n){ ans = t; return; } if(!ans.empty() || memo[a][b]) return; memo[a][b] = true; if(a != ca){ t.push_back(0); rec(ca, b, t); // fill A t.pop_back(); } if(b != cb){ t.push_back(1); rec(a, cb, t); // fill B t.pop_back(); } if(a != 0){ t.push_back(2); rec(0, b, t); // empty A t.pop_back(); t.push_back(4); int chg = min(a, cb - b); rec(a - chg, b + chg, t); //pour A B t.pop_back(); } if(b != 0){ t.push_back(3); rec(a, 0, t); // empty B t.pop_back(); t.push_back(5); int chg = min(b, ca - a); rec(a + chg, b, t); //pour B A t.pop_back(); } return; } string str[] = { "fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A", }; int main(int argc, char **argv){ while(cin >> ca >> cb >> n){ FILL(memo, false); ans.clear(); rec(0, 0, deque<int>()); deque<int>::iterator it = ans.begin(); for(; it != ans.end(); it++) cout << str[*it] << endl; cout << "success" << endl; } return 0; }
POJ 1107 W's Cipher
問題
アルファベットとアンダーバーからなる文字種を[a-i]、[j-r]、[s-zと_]の3グループに分ける。
文字置換による文章の暗号化を行いたい。暗号化の方法は平文の文字を一つずつ見ていき、その文字がグループiに属する時、その文字の右側を見ていって、グループiに所属するki個目の文字で置換する。
暗号文が与えられるので平文を出力せよ。
やりかた
暗号化と逆の方法をとる。その文字がグループiに属する時、その文字の左側を見ていって、グループiに所属するki個目の文字で置換すれば平文が求まる。
以下ソース。
int gr(char c){ if('a' <= c && c <= 'i') return 0; if('j' <= c && c <= 'r') return 1; else return 2; } int k[3]; int main(int argc, char **argv){ string s; while(cin >> k[0] >> k[1] >> k[2], k[0] + k[1] + k[2]){ cin >> s; string t = s; for(int i = 0; i < s.size(); i++){ int idx = i, skip = 0; while(1){ idx--; idx = (idx + s.size()) % s.size(); skip += (gr(s[i]) == gr(s[idx])); if(skip == k[gr(s[i])]){ t[i] = s[idx]; break; } } } cout << t << endl; } return 0; }
Get up! 明日のSUPER ST@R!
