SRM699 Div1 Easy "OthersXor"
解法
N匹の狼がいて、何匹か飴を１つ持っている。ここで、それぞれの狼に「あなたを除く他の狼たちの飴を合計するとそれは奇数？偶数？」と聞く。狼たちは正直に答えるが、黙秘権を行使する狼もいる。この時、飴の合計の最小はいくつだ？
というような問題に置き換えられる。
「奇数です」と答えた狼がいなかったとすると、全員の狼が飴を持っていない場合で整合性がとれるため、飴の数は0でよい。
では、「奇数です」と答えた狼がいた場合はどうか？
まず、「奇数です」と答えた狼同士、もしくは「偶数です」と答えた狼同士、それら全員飴を持っているか、誰も持っていないかでなければならない。なぜなら、持っている狼と持っていない狼の合計値の差が１になってしまうため、偶奇がズレてしまうからである。なので、「奇数です」と答えた狼全員に持たせるか、「偶数です」と答えた狼全員に持たせるか、小さいほうをとればよい。
事後
難しいけど偶奇を考えるのは面白いなぁ
ソースコード
class OthersXor { public: long long minSum(vector<int> x) { int n = x.size(); long long ans = 0; // それぞれのビット位置で回す for (int mask = 1; mask < 1 << 30; mask <<= 1) { // 奇数・偶数・黙秘の数を数え上げる int odd = 0; int even = 0; int unknown = 0; for (int i = 0; i < n; i++) { if (x[i] == -1) { unknown++; } else { if ((x[i] & mask) != 0) { odd++; } else { even++; } } } if (odd != 0) { // 奇数と答えた狼がいた場合 const int INF = 50; int use_odd = INF; // 奇数組全員に持たせる場合 if (odd % 2 == 0) { use_odd = odd; } else if (unknown != 0) { use_odd = odd + 1; } // 偶数組全員に持たせる場合 int use_even = INF; if (even % 2 != 0) { use_even = even; } else if (unknown != 0) { use_even = even + 1; } // 奇数偶数小さいほうをとる int use_num = min(use_odd, use_even); if (use_num == INF) { return -1; } ans += (long long)mask * use_num; } } return ans; } };
SRM673 Div1 Easy " BearCavalry"
解法
とりあえず、一番目の戦士がそれぞれの馬を使った時を試してみる。
残った戦士を降順に、残った馬を昇順にソートしておく。
あとはSample0のもので説明していく
戦士0(5)は馬1(40)を使うぜ！つまり戦闘力は200だぜ！ 残った戦士と馬はこんな感じだ！ 戦士 8 8 4 ←降順にソート 馬 19 20 25 ←昇順にソート ここで、戦士0(8)は馬0~1まで使えるぜ！ つまり、パターンは2だぜ！ 戦士1(8)は馬0~1まで使えるぜ！ でももう馬は１つ乗られちゃってるぜ！ だから、パターンは1だぜ！ 戦士2(4)は馬0~2まで使えるぜ！ でももう馬は２つ乗られちゃってるぜ！ だから、パターンは1だぜ！ 結果、パターンは2 * 1 * 1で2だぜ！
事後
ポインツは150ぐらい。
解くスピードを上げたいなぁ
ソースコード
const int MOD = 1000000007; class BearCavalry { public: int countAssignments(vector<int> warriors, vector<int> horses) { int n = warriors.size(); // 最初の戦士を除いたもの vector<int> w; for (int i = 1; i < n; i++) { w.push_back(warriors[i]); } // 戦士を降順にソート sort(w.begin(), w.end(), greater<int>()); // 馬を昇順にソート sort(horses.begin(), horses.end()); int ans = 0; // 0 ~ n - 1までの馬を使用する for (int i = 0; i < n; i++) { int lim = warriors[0] * horses[i]; // 使用した馬を除いたもの vector<int> h; for (int j = 0; j < n; j++) { if (i == j) continue; h.push_back(horses[j]); } ans += solve(w, h, lim); if (ans >= MOD) ans -= MOD; } return ans; } int solve(vector<int> w, vector<int> h, int lim) { // printf("lim...%d\r\n", lim); int n = w.size(); long long cnt = 1; for (int wi = 0; wi < n; wi++) { int h_max = lim / w[wi] + (lim % w[wi] == 0 ? 0 : 1); int hi = 0; for (; hi < n; hi++) { if (h_max <= h[hi]) break; } int canUseNum = max(0, hi - wi); // printf(" %d(%d) %d %d\r\n", wi, w[wi], hi, canUseNum); cnt *= canUseNum; cnt %= MOD; } return cnt; } };
SRM672 Div1 Easy "Procrastination"
事後
ソースが簡潔でいいですなぁ
ソースコード
class Procrastination { public: long long findFinalAssignee(long long n) { // nより小さい最大の素数と // n以上の最小の素数を求める long long lp = n - 1; long long rp = n; while (!isPrime(lp)) lp--; while (!isPrime(rp)) rp++; // lp < x <= rp のすべての約数を求める set<long long> s; for (long long x = lp + 1; x <= rp; x++) { for (long long d = 2; d * d <= x; d++) { if (x % d == 0) { s.insert(d); s.insert(x / d); } } } // シミュレートしていく for (auto f : s) { if (n % f == 0) { n++; } else if (n % f == 1) { n--; } } return n; } // 素数か？ bool isPrime(long long n) { for (long long d = 2; d * d <= n; d++) { if (n % d == 0) return false; } return true; } };
SRM674 Div1 Easy "VampireTree"
解法
まず木グラフの特性より、辺の数はn - 1なので、そうなっているか確認。（インプットのnumは辺を２回ずつ数え上げているから、(n - 1) * 2 = num[i]の合計値なのか確認）
木グラフになっていたら、あとはどう繋げればグラフの最大長が最大になるかだが・・・
どうもいろいろ試してみたところ、辺を２以上持つ頂点は、貪欲に直列につないでしまって問題ない。
そこに、辺を１だけ持つ頂点を補完するように繋いでいくことが必ずできる。
なぜかは理解してないけど、木グラフはそうゆう特性を持っているんだろうな～。
事後
問題文がTrue Ancestor（真の祖先）をやたらと強調するのは罠だったんですね！
ソースコード
class VampireTree { public: int maxDistance(vector<int> num) { int n = num.size(); int sum = 0; int more2 = 0; for (int i = 0; i < n; i++) { sum += num[i]; if (num[i] >= 2) { more2++; } } if ((n - 1) * 2 != sum) return -1; return more2 + 1; } };
SRM675 Div1 Easy "TreeAndPathLength3"
考えた解法
0と1をとりあえず繋げる。
他の頂点は0または1にだけ繋げることを考えると、長さ3のシンプルパスの数は0に繋げた頂点の数 * 1に繋げた頂点の数になる。
9991とかの大きめの素数はこれだけだと丁度にならないので、0に繋げた頂点のどれかに直列に繋げて補完する。
例えばs = 19のとき、0に3つ、1に5つ繋げて3 * 5 = 15 残り4。あとは0に繋がっている頂点に直列に２つ繋げて3 + 1 = 4追加する。
イメージは以下のような感じ
事後
ソースコード
class TreeAndPathLength3 { public: vector<int> construct(int s) { // とりあえず0と1を繋げる vector<int> ans; ans.push_back(0); ans.push_back(1); for (int on0 = 1; on0 <= 200; on0++) { for (int on1 = 1; on1 <= 200; on1++) { int rem = s - on0 * on1; if (rem == 0 || (on0 <= rem && rem - on0 + 1 <= 500 - (on0 + on1 + 2))) { int cur = 2; // 1に繋げまくる for (int i = 0; i < on1; i++) { ans.push_back(1); ans.push_back(cur++); } // 0に繋げまくる for (int i = 0; i < on0; i++) { ans.push_back(0); ans.push_back(cur++); } // 残りを直列に繋げまくる rem = rem - on0 + 1; cur--; for (int i = 0; i < rem; i++) { ans.push_back(cur); ans.push_back(++cur); } return ans; } } } return ans; } };
SRM676 Div1 Easy "WaterTank"
解法
outputの秒間流量を決め打って、溢れる溢れないを判定。それをにぶたん。
事後
誤差について理解できてないのでこういう問題怖い
ソースコード
int C; vector<int> T; vector<int> X; int N; class WaterTank { public: double minOutputRate(vector<int> t, vector<int> x, int c) { T = t; X = x; C = c; N = t.size(); double L = 0.0; double R = 1e9; for (int i = 0; i < 50; i++) { double m = (L + R) / 2; if (solve(m)) { R = m; } else { L = m; } } return L; } bool solve(double output) { double S = 0.0; for (int i = 0; i < N; i++) { double inc = (double)X[i] * T[i]; double dec = output * T[i]; S = max(0.0, S + inc - dec); if (S > C) { return false; } } return true; } };
SRM677 Div1 Easy "DoubleOrOneEasy"
解法
青いボタンを何回使ったかで全探索するとよい。
青いボタンをn回使ったとすると、aは2^n * aとなり、あとは、赤いボタンをnewA - 2^n * a 回だけ押せばよいことになる（この回数をxと置く）
bの方も同じように2^n * bとなり、赤いボタンはnewB - 2^n * b 回だけ押せばよいことになる（この回数をyと置く）
この時、x = yとなっていれば、赤いボタンと青いボタンを同じ回数だけ押したときにnewA, newBとなるため、問題の条件をクリアする。
で、青いボタン⇒赤いボタンと順番をまとめてしまうと押す数が最小回数とならない。
例えばnewA = 2^3 * a + 9となった場合。順番をまとめると青いボタン３回・赤いボタン９回で１２回押すことになるが、赤いボタンをまず１回押しておいて、それから青いボタンを３回押す。（これにより赤いボタンを８回押した効果が得られる）それから赤いボタンを１回押せば、最小で済む。つまり、2^3 * a + 9 を 2^3 * a + 2^3 + 2^0ととらえると、青いボタン３回・赤いボタン２回となって５回で済む。また例えば、newA = 2^4 * a + 15となった場合、2^4 * a + 15 を 2^4 * a + 2^3 + 2^2 + 2^1 + 2^0ととらえると、青いボタン４回・赤いボタン４回となる。赤いボタンの効果を青いボタンで上手いこと増幅してあげるようにボタンを押すとよい。
ソースコード
class DoubleOrOneEasy { public: int minimalSteps(int a, int b, int newA, int newB) { long long pow2 = pow(2, 30); for (int blue = 30; blue >= 0; blue--) { long long x = static_cast<long long>(newA) - a * pow2; if (x >= 0) { long long y = static_cast<long long>(newB) - b * pow2; if (x == y) { int red = 0; while (pow2 != 0) { red += x / pow2; x %= pow2; pow2 /= 2; } return blue + red; } } pow2 /= 2; } return -1; } };
