SRM701 Div1 Easy "PartisanGame"
解法
りんごさんのソースコードを参考にしましたm(_ _)m
石取りゲームにありがちなdpをする。(現在の状態から遷移できる状態の中で、勝てるものがあれば勝ち というやつ)
だが、石の数が半端ないのでもう一工夫必要となる。
現在の状態から遷移できる状態はAlice側とBob側合わせても高々10パターンと少ないことを利用する。10パターンそれぞれ勝てる・勝てないの状態しかもっていないので、状態は2^10のバリエーションがあることになる。つまり、dpの状態は最大でも2^10の周期でループすることになる。よって、2^10までdpして、それ以上はループしていることを利用して算出するようにすればよい。
ソースコード
// dp[0][i]:= Aliceの番で石の数がi個あるとき、Aliceは勝てるか? // dp[1][i]:= Bobの番で石の数がi個あるとき、Bobは勝てるか? int dp[2][1234567]; class PartisanGame { public: string getWinner(int n, vector<int> a, vector<int> b) { // 2^10までdp for (int i = 0; i < 1234567; i++) { // Alice? dp[0][i] = false; for (int j = 0; j < a.size(); j++) { int x = a[j]; if (x <= i && !dp[1][i - x]) dp[0][i] = true; } // Bob? dp[1][i] = false; for (int j = 0; j < b.size(); j++) { int x = b[j]; if (x <= i && !dp[0][i - x]) dp[1][i] = true; } } // 周期を算出 int q = 1050000; // 2^10以上! int p = q - 1; for (;; p--) { if (check(p, q)) break; } int cycle = p - q; // 答え算出 if (n > p) n = (n - p) % cycle + p; return dp[0][n] ? "Alice" : "Bob"; } // pとqは同じ状態か? bool check(int p, int q) { for (int i = 0; i <= 1; i++) { for (int j = 0; j < 5; j++) { if (dp[i][p + j] != dp[i][q + j]) return false; } } return true; } };
SRM660 Div1 Easy "Coversta"
解法
コチラを参考にしました。m(_ _)m
kmjp.hatenablog.jp
セル(i, j)に置いた時のスコアを出して、それが大きい順にセルをソートしておく。
1個目の基地を任意の位置に置いた時の、2個目の基地のベストな置き場所を考える。
ベストな置き方は、「セルが重複するような置き方の中でスコアが最大なもの」と「セルが重複しないような置き方の中でスコアが最大なもの」の、これら2つの大きいほうである。
セルが重複するパターンは、x.size()をNとするとN * (N - 1)個しかない。スコアの大きい順にセルを見ていったとき、N * (N - 1) + 1見れば、その中に「セルが重複しないような置き方の中でスコアが最大なもの」が必ず含まれているはず。だから、2個目の基地の置き方を探索するときは、N * (N - 1) + 1回行えば十分である。
ソースコード
class Coversta { public: int place(vector<string> A, vector<int> Y, vector<int> X) { int R = A.size(); int C = A[0].size(); int N = X.size(); // スコアだしてリストに詰める vector<pair<int, int> > cells; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { int s = 0; for (int k = 0; k < N; k++) { int y = i + Y[k]; int x = j + X[k]; if (0 <= y && y < R && 0 <= x && x < C) { s += A[y][x] - '0'; } } cells.push_back(make_pair(s, i * C + j)); } } // スコア順にソート sort(cells.begin(), cells.end(), greater<pair<int, int> >()); int best = 0; // a for (int ay = 0; ay < R; ay++) for (int ax = 0; ax < C; ax++) { int scoreA = 0; set<pair<int, int> > s; for (int i = 0; i < N; i++) { int y = ay + Y[i]; int x = ax + X[i]; if (0 <= y && y < R && 0 <= x && x < C) { scoreA += A[y][x] - '0'; s.insert(make_pair(y, x)); } } // b int checkN = N * (N - 1) + 1; for (int bi = 0; bi < checkN && bi < cells.size(); bi++) { int scoreB = 0; int by = cells[bi].second / C; int bx = cells[bi].second % C; for (int i = 0; i < N; i++) { int y = by + Y[i]; int x = bx + X[i]; if (0 <= y && y < R && 0 <= x && x < C && s.find(make_pair(y, x)) == s.end()) { scoreB += A[y][x] - '0'; } } best = max(best, scoreA + scoreB); } } return best; } };
SRM661 Div1 Easy "MissingLCM"
解法
N + 1 ~ Mの中に、1 ~ Nの素因数を全て持っている必要がある。
例えばN = 10であれば、1 ~ 10に2^3, 3^2, 5^1, 7^1の素因数がある。
それぞれ11(N + 1)以上で、どの数であればその素因数を持つかを見ていくと、
2^3は2^3 * 2 = 16が持つ
3^2は3^2 * 2 = 18が持つ
5^1は5^1 * 3 = 15が持つ
7^1は7^2 * 2 = 14が持つ
となり、11 ~ 18で1 ~ 10の素因数を全て持つこととなる。
ソースコード
bool P[1000010]; class MissingLCM { public: int getMin(int N) { long long ans = 2; for (int i = 0; i <= N; i++) { P[i] = true; } P[0] = P[1] = false; for (int p = 2; p <= N; p++) { if (!P[p]) continue; for (int i = p + p; i <= N; i += p) { P[i] = false; } // 素数だ! // 1~Nはこの素数をどれだけ持つ? long long x = 1; while (x * p <= N) { x *= p; } // それはいくつ以上の数字で超える?(ただしNより大きいもので) long long y = x; while (y <= N) { y += x; } // これの最大値をとってく ans = max(ans, y); } return (int)ans; } };
SRM662 Div1 Easy "FoxesOfTheRoundTable"
解法
以下の通りです。orz
mayokoex.hatenablog.com
事後
D=1~1000まで全探索すればいいや。
↓
実装に手間取る
↓
ふぅ・・・なんとか時間ぎりぎりにコミット
↓
WA
↓
SRM662でググる
↓
Greedyかよ!!
ソースコード
class FoxesOfTheRoundTable { public: vector<int> minimalDifference(vector<int> _h) { int n = _h.size(); // ソートする int h[55]; int hi[55]; for (int i = 0; i < n; i++) { h[i] = _h[i]; hi[i] = i; } while (true) { bool update = false; for (int i = 0; i < n - 1; i++) { if (h[i] > h[i + 1]) { swap(h[i], h[i + 1]); swap(hi[i], hi[i + 1]); update = true; } } if (!update) break; } // 行き vector<int> ans; for (int i = 0; i < n; i += 2) { ans.push_back(hi[i]); } // 帰り int start = n % 2 == 0 ? n - 1 : n - 2; for (int i = start; i > 0; i -= 2) { ans.push_back(hi[i]); } return ans; } };
SRM663 Div1 Easy "ABBADiv1"
解法
最終的にinitialが反転しないで終わったのか、反転して終わったのかを決め打つ。
■反転しないで終わった時の条件
target = 左側の文字列 + initial + 右側の文字列 とすると、 ・左側と右側の文字列で、含まれる'B'の数が一致する事 ・左側の文字列の最初が'A'でないこと
■反転して終わった時の条件
target = 左側の文字列 + initial(反転) + 右側の文字列 とすると、 ・左側と右側の文字列で、含まれる'B'の数が左側の方が1つ多い事 ・左側の文字列の最初が'A'でないこと
事後
ヒントなしで解けたけど、なんか回りくどい方法・・
反対に考えてtarget->initialにできるか?を考えるとよかったポイ
ソースコード
class ABBADiv1 { public: string canObtain(string initial, string target) { int n = initial.size(); int m = target.size(); // 順 for (int i = 0; i <= m - n; i++) { bool match = true; for (int j = 0; j < n; j++) { if (target[i + j] != initial[j]) match = false; } if (!match) continue; int lb = 0; for (int j = 0; j < i; j++) { if (target[j] == 'B') lb++; } int rb = 0; for (int j = i + n; j < m; j++) { if (target[j] == 'B') rb++; } if (lb != rb) continue; if (i != 0 && target[0] == 'A') continue; return "Possible"; } // 逆 reverse(initial.begin(), initial.end()); for (int i = 0; i <= m - n; i++) { bool match = true; for (int j = 0; j < n; j++) { if (target[i + j] != initial[j]) match = false; } if (!match) continue; int lb = 0; for (int j = 0; j < i; j++) { if (target[j] == 'B') lb++; } int rb = 0; for (int j = i + n; j < m; j++) { if (target[j] == 'B') rb++; } if (lb != rb + 1) continue; if (target[0] == 'A') continue; return "Possible"; } // 無理ぃ return "Impossible"; } };
SRM665 Div1 Easy "LuckySum"
解法
以下、参考にさせていただきました。m(_ _)m
kmjp.hatenablog.jp
事後
実装がちょっと難しくなると頭が混乱するのなんとかして
ソースコード
const long long INF = 123456789012345LL; long long dp[20][2][3]; int sums[20]; class LuckySum { public: long long construct(string note) { int n = note.size(); // sums初期化 for (int i = 0; i < n; i++) sums[n - i - 1] = note[i] == '?' ? -1 : note[i] - '0'; // dp初期化 for (int d = 0; d <= n; d++) for (int c = 0; c < 2; c++) for (int e = 0; e < 3; e++) dp[d][c][e] = INF; dp[0][0][0] = 0; // dp更新 int ds[] = {7, 4, 0}; long long p_10 = 1; for (int d = 0; d < n; d++) { for (int c = 0; c < 2; c++) for (int e = 0; e < 3; e++) { if (dp[d][c][e] == INF) continue; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { int a = ds[i]; int b = ds[j]; int s = a + b + c; int dight = s % 10; int carry = s / 10; int end = (a == 0 ? 1 : 0) + (b == 0 ? 1 : 0); // 未完了のlackyNumberの数より使用するLackyNumberの数の方が多ければやらない if (2 - e < 2 - end) continue; // 最初の桁であり、endが1以上であればやらない if (d == 0 && end >= 1) continue; // sumsと合っていなければやらない if (sums[d] != -1 && sums[d] != dight) continue; // endが2であり、最後の桁でない、または繰り上がりがなければやらない if (end == 2 && (d != n - 1 || c == 0)) continue; dp[d + 1][carry][end] = min(dp[d + 1][carry][end], dp[d][c][e] + dight * p_10); } } p_10 *= 10; } // dp答え long long ans = INF; for (int e = 0; e < 3; e++) { ans = min(ans, dp[n][0][e]); } return ans == INF ? -1 : ans; } };
SRM664 Div1 Easy "BearPlays"
解法
例のごとく他人だより。以下、参考にさせていただきました。m(_ _)m
mayokoex.hatenablog.com
事後
あ^~あるはずのない周期性に賭けてしまったんじゃ^~
ソースコード
class BearPlays { public: int pileSize(int A, int B, int K) { long long a = A; long long b = B; long long s = a + b; int m = pow_mod(2, K, s); long long mi = min(a, b); long long res = mi * m % s; long long ans = min(res, s - res); return (int)ans; } // a ^ b % mod 繰り返し2乗法! long long pow_mod(long long a, long long b, long long mod) { long long r = 1; while (b > 0) { if ((b & 1) != 0) { r *= a; r %= mod; } a *= a; a %= mod; b >>= 1; } return r; } };