SRM690 Div1 Easy "WolfCardGame"
問題
リンク無し！
訳
狼のSotheと猫のSnukeがカードゲームで遊んでいる。このゲームはちょうど100枚のカードを使う。カードには1から100の数字が書かれている。ゲームの遊び方については以下の通り。
1. 初めに、猫のSnukeが1から100の中から数字のNを選び、これをゴールとする。
2. それから、狼のSotheが100枚のカードからちょうどK枚選び、Snukeに渡す。
3. 次に、猫のSnukeが渡されたK枚のカードから何枚かカードを捨てる。
彼は渡されたカードの任意のサブセットを捨てるカードとして選ぶことができ、
それはカードをまったく捨てなくてもよいし、全てのカードを捨ててもよい。
4. 最後に、猫のSnukeは、彼がまだ持っているカードのうち、
任意のサブセットのカードを選び、そこにマイナスの記号を書く。
例えば彼が{1, 3, 4, 7}のカードを持っていたとしたら、
{-1, 3, 4, -7}などとなる。
このゲームの終わりでは、Snukeが持っているカードに書かれている数字の合計を計算する(この時、追加されたマイナスの記号を考慮する)。それがゴールであるNと等しいならば、Snukeの勝ちである。そうでなければSotheの勝ちである。
あなたには狼のSotheがゲームに勝つための手助けをしてもらいたい。今、ゲームはStep2の局面である。あなたには、Snukeが決めたint Nと、Snukeに渡すカードの枚数であるint Kが与えられる。Snukeがゲームに勝つ事ができないように、K枚のカードを選んでほしい。もし複数の答えがあるのであれば、どれを返してもよい。答えがないのであれば、空のリストを返すこと。
解法
dの倍数の数字同士で、それらを足し引きすると必ずdの倍数となる。
この性質を踏まえると、Nがdの倍数でないときは、{d * 1, d * 2, ... , d * K}のカードを選べばよいことになる。
ただし、N = 60の時だけは2, 3, 4, 5, 6の何れも倍数となり、7がdとなる。
7 * 15 = 105であり、N = 60, K = 15のときにまずいので、リストには105の代わりに1などを追加してあげる必要がある。
ソースコード
bool P[101]; class WolfCardGame { public: vector<int> createAnswer(int N, int K) { if (N == 60 && K == 15) { int data[] = {7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 1}; vector<int> ans(data, data + K); return ans; } int d = 0; for (int i = 2; i <= 7; i++) { if (N % i != 0) { d = i; break; } } vector<int> ans; for (int i = 1; i <= K; i++) { ans.push_back(d * i); } return ans; } };
SRM691 Div1 Easy " Sunnygraphs"
解法
下の記事を参考にしました。m(_ _)m
kmjp.hatenablog.jp
有効グラフで考えたときに、頂点を以下のように色分けする。
A・・・0,1どちらからも到達できる頂点 B・・・0からのみ到達できる頂点 C・・・1からのみ到達できる頂点 D・・・0,1どちらからも到達できない頂点
そしたら、0と1を繋げる方法を以下のパターンで考える
パターン１・・・B及びCの辺を、どちらも頂点Nに繋げないとする。 すると、A,Dの辺については自由に動かせる。 (初期グラフで既に0と1が繋がっている事が条件だが) パターン２・・・Bの辺を頂点Nに繋げるとする。 すると、AまたはCの辺を頂点Nに繋げる必要がでてくる。 Dの辺については自由に動かせる。 パターン３・・・Cの辺を頂点Nに繋げるとする。 すると、AまたはBの辺を頂点Nに繋げる必要がでてくる。 Dの辺については自由に動かせる。 パターン４・・・BおよびCの辺を頂点Nに繋げるとする。 すると、A,Dの辺については自由に動かせる。
パターン２でBとCの辺を頂点Nに繋げている場合があるが、これはパターン４に含まれるので排除する。
パターン３でも同様にその部分を排除する。
また、Dの辺は常に自由なのでまとめて計算できる。
それを加味してパターン分けしたのが以下である。
パターン１・・・B及びCの辺を、どちらも頂点Nに繋げないとする。 すると、Aの辺については自由に動かせる。 (初期グラフで既に0と1が繋がっている事が条件だが) パターン２・・・Bの辺を頂点Nに繋げるとする。 すると、Aの辺を頂点Nに繋げる必要がでてくる。 パターン３・・・Cの辺を頂点Nに繋げるとする。 すると、Aの辺を頂点Nに繋げる必要がでてくる。 パターン４・・・BおよびCの辺を頂点Nに繋げるとする。 すると、Aの辺については自由に動かせる。 ※Dは常に自由に動かせる。
事後
これほんとEasyなの？ん？どうなの？Medじゃないの？
ソースコード
class Sunnygraphs { public: long long count(vector<int> _a) { a = _a; n = a.size(); // 有効グラフ作成 createGreph(); // 0,1それぞれでつながる所を算出 findReach0(); findReach1(); // 0,1から到達する頂点 // 0からのみ到達する頂点 // 1からのみ到達する頂点 // 0,1から到達しない頂点 // ・・・を数える int r01 = 0; int r0 = 0; int r1 = 0; int nr = 0; for (int i = 0; i < n; i++) { if (reach0[i]) { if (reach1[i]) { r01++; } else { r0++; } } else { if (reach1[i]) { r1++; } else { nr++; } } } long long ans = 0; // パターン１ if (r01 >= 1) { ans += pow2(r01); } // パターン２ ans += (pow2(r0) - 1) * (pow2(r01) - 1); // パターン３ ans += (pow2(r1) - 1) * (pow2(r01) - 1); // パターン４ ans += (pow2(r0) - 1) * (pow2(r1) - 1) * (pow2(r01)); // 0および1から到達しない頂点は自由 ans *= (pow2(nr)); return ans; } void createGreph() { for (int i = 0; i <= n; i++) { g[i].clear(); } for (int i = 0; i < n; i++) { g[i].push_back(a[i]); } } void findReach0() { for (int i = 0; i < n; i++) { reach0[i] = false; } dfs0(0); } void dfs0(int cur) { reach0[cur] = true; for (int i = 0; i < g[cur].size(); i++) { if (reach0[g[cur][i]]) continue; dfs0(g[cur][i]); } } void findReach1() { for (int i = 0; i < n; i++) { reach1[i] = false; } dfs1(1); } void dfs1(int cur) { reach1[cur] = true; for (int i = 0; i < g[cur].size(); i++) { if (reach1[g[cur][i]]) continue; dfs1(g[cur][i]); } } long long pow2(int p) { long long res = 1; for (int i = 0; i < p; i++) { res *= 2; } return res; } };
SRM692 Div1 Easy "HardProof"
解法(一番早かった人のをカンニング)
通過する辺の重みにて、下回ってはいけない最小値ラインを決め打ちする。
↓
辺それぞれの重みから、決め打ちした最小値を差し引く。
↓
0 -> 1へ移動するために通る最大の重みの最小値
1 -> 0へ移動するために通る最大の重みの最小値
0 -> 2へ移動するために通る最大の重みの最小値
2 -> 0へ移動するために通る最大の重みの最小値
0 -> 3へ移動するために通る最大の重みの最小値
3 -> 0へ移動するために通る最大の重みの最小値
・・・
これらの最大値を取る(うーんとても分かりにくい説明だ・・)
↓
これらをそれぞれの最小値ラインで行い、その最小値をとれば答え
事後
全点最短経路問題であるため、ワーシャル-フロイドさんを使うと効率が良い。
しかしそれでも計算量はO(50^5) = 3億超と微妙である。
Systestは一応1秒切ったから、単純な計算を3億回とかならSRM的には問題ないっぽい。
ソースコード
int f[55][55]; int g[55][55]; class HardProof { public: int minimumCost(vector<int> D) { int n = sqrt(D.size()) + 0.5; // サイズ1なら0 if (n == 1) return 0; // f[i][j]にi->jへのコストを入れる for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { f[i][j] = D[i * n + j]; } } int INF = 200000; int ans = INF; // f[i][j]を最小値ラインとする for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; // 最小値ラインを加味してグラフを作成 for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { if (f[u][v] < f[i][j]) { g[u][v] = INF; } else { g[u][v] = f[u][v] - f[i][j]; } } } // 変形ワーシャル-フロイドさん for (int w = 0; w < n; w++) { for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { g[u][v] = min(g[u][v], max(g[u][w], g[w][v])); } } } // 0 -> 1へ移動するために通る最大の重みの最小値 // 1 -> 0へ移動するために通る最大の重みの最小値 // ・・・ // の最大値をとる int cand = 0; for (int u = 1; u < n; u++) { cand = max(cand, g[0][u]); cand = max(cand, g[u][0]); } // それぞれの最小値ラインで算出したもので最小値を取る ans = min(ans, cand); } } return ans; } };
SRM693 Div1 Easy "BiconnectedDiv1"
解法
w1[i]を消すとw2[i-1]とw2[i]が消せなくなり、w2[i]を消すとw1[i], w1[i+1], w2[i-1], w2[i+1]が消せなくなる。
で、w1とw2を交互に、iの小さいものから消すか？消さないかを順に考えていけば、
w1[1]->w2[1]->w1[2]->w2[2]->w1[3]->w2[3]->...
w1[i]を消すとw2[i]が消せなくなり、w2[i]を消すとw1[i+1], w2[i+1]が消せなくなる。というのだけ考えればよくなる。
これを踏まえdpる。
dp[x] := (w1とw2の辺を交互に混ぜたうえで)x-1番目の辺まで考えた時の、消した辺の最大の重み。
初期化
まだ考えていなければ重みは0なので
dp[0] = 0;
更新
w1(混ぜた辺のインデックス(base-0)が偶数のもの)の辺を考えるとき、それを消さなければ
dp[i+1] = max(dp[i+1], dp[i])
それを消したら
dp[i+2] = max(dp[i+2], dp[i] + 辺iの重み)
w2(混ぜた辺のインデックス(base-0)が奇数のもの)の辺を考えるとき、それを消さなければ
dp[i+1] = max(dp[i+1], dp[i])
それを消したら
dp[i+3] = max(dp[i+3], dp[i] + 辺iの重み)
事後
問題文が齟齬なく読めた！バグもなかった！Systestも一発で通った！わはーい！
ソースコード
int dp[222]; class BiconnectedDiv1 { public: int minimize(vector<int> w1, vector<int> w2) { // w1, w2まぜまぜ vector<int> es; for (int i = 1; i < w1.size() - 1; i++) { es.push_back(w1[i]); if (i != w1.size() - 2) es.push_back(w2[i]); } // dp初期化 int m = es.size(); for (int i = 0; i <= m + 1; i++) { dp[i] = 0; } // dp更新 for (int i = 0; i < m; i++) { // この辺は消さない dp[i + 1] = max(dp[i + 1], dp[i]); // この辺は消す int ni = i + (i % 2 == 0 ? 2 : 3); dp[ni] = max(dp[ni], dp[i] + es[i]); } // 答え算出 int all = 0; for (int i = 0; i < w1.size(); i++) { all += w1[i]; } for (int i = 0; i < w2.size(); i++) { all += w2[i]; } return all - max(dp[m + 1], dp[m + 2]); } };
SRM653 Div1 Easy "CountryGroupHard"
解法
dpる。
dp[i] := i-1番目の人までの、番号の振り方の場合の数
初期化
まだ誰にも番号を振っていないときは１パターンなので、
dp[0] = 1;
更新
i番目の人に1からi+1までの番号を振って、それぞれの場合の数を足しこんでいく
例えば、3番目(0-base)の人に2番を振れる場合、dp[2(3-2+1)]をdp[4(3+1)]に足すことになる。
結果
dp[n]が1なら"Sufficient"、それでなければ"Insufficient"
事後
うーん。。場合の数の数え上げの問題に変換できなかった。
Greedyから頭が離れず結局カンニング。
ソースコード
int dp[105]; class CountryGroupHard { public: string solve(vector<int> a) { int n = a.size(); int dp[n + 1]; // dp初期化 memset(dp, 0, sizeof(dp)); dp[0] = 1; // dp更新 for (int i = 0; i < n; i++) { for (int x = 1; x <= i + 1; x++) { bool ok = true; for (int c = i - x + 1; c <= i; c++) { if (a[c] != 0 && a[c] != x) ok = false; } if (ok) dp[i + 1] += dp[i - x + 1]; } } return (dp[n] == 1) ? "Sufficient" : "Insufficient"; } };
SRM694 Div1 Easy "TrySail"
解法
dpる。
まず全員をteam1に加入させておく。
それから、生徒ごとに着目していき、team2及びteam3に移籍させる場合を考えていく。
team2及びteam3それぞれのチーム力とすることが可能かどうか記録しておき、それを更新していく。
dp[team2/team3それぞれのチーム力] := それが可能？
事後
255は0x11111111じゃない。。0b11111111だったよ。。orz
ソースコード
bool dp[2][1 << 16]; class TrySail { public: int get(vector<int> strength) { int n = strength.size(); // 全員チーム1に加入しとく int all = 0; for (int i = 0; i < n; i++) { all ^= strength[i]; } // dp初期化 for (int i = 0; i < 2; i++) { for (int b = 0; b < (1 << 16); b++) { dp[i][b] = false; } } int cur = 0; int next = 1; dp[cur][0] = true; // dp更新 for (int i = 0; i < n; i++) { // next初期化 for (int b = 0; b < (1 << 16); b++) { dp[next][b] = false; } // 加入していく for (int b = 0; b < (1 << 16); b++) { if (!dp[cur][b]) continue; // チーム1に残留 dp[next][b] = true; // チーム2に移籍 dp[next][b ^ strength[i]] = true; // チーム3に移籍 dp[next][b ^ (strength[i] << 8)] = true; } // cur next交代 cur = 1 - cur; next = 1 - next; } // 答え算出 int answer = 0; for (int b = 0; b < (1 << 16); b++) { if (!dp[cur][b]) continue; int t2 = b & 0b11111111; int t3 = (b >> 8) & 0b11111111; int t1 = all ^ t2 ^ t3; answer = max(answer, t1 + t2 + t3); } return answer; } };
SRM695 Div1 Easy "BearPasswordLexic"
解法
最終的に使用するconstantの長さとその数について、実は一意に定まる。
以下を見て欲しい。
constantの長さ | 1 2 3 4 数 | 11 8 5 2 ↓ constants 4 を1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 | 7 5 3 1 ↓ constants 4 をもう1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 | 3 2 1 0 ↓ constants 3 を1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 | 0 0 0 0 ってことは、 constant 4 を 2回 constant 3 を 1回 使うんだね！☆（ゝω・）vｷｬﾋﾟ
で、辞書順に最小にしなければならないので、まず a を使うべきであろう。
そして、aを使う時はconstantの長さが長いほど良いので、最大のものを使うようにする。
次は b を使わなければならない。
そして、bを使う時はconstantの長さが短いほど良いので、最小のものを使うようにする。
constant 4 を 2回 constant 3 を 1回
だと、答えは"aaaabbbaaaa"となる。
ソースコード
class BearPasswordLexic { public: string findPassword(vector<int> x) { int n = x.size(); // ここで、ｘ[0]=nでなければ失敗 if (x[0] != n) return ""; // 使用するconstantとその数を計算する int constants[55]; memset(constants, 0, sizeof(constants)); for (int k = 0; k < n; k++) { for (int i = n - 1; i >= 0; i--) { if (x[i] != 0) { constants[i]++; for (int j = i; j >= 0; j--) { x[j] -= i - j + 1; } break; } } } // ここで、全て0になっていなければ失敗 for (int i = 0; i < n; i++) { if (x[i] != 0) return ""; } // aからスタート string answer = ""; bool curA = true; while (true) { if (curA) { // aだったら一番大きいconstantを使用する int id = -1; for (int i = n - 1; i >= 0; i--) { if (constants[i] != 0) { id = i; constants[i]--; break; } } if (id == -1) return answer; for (int i = 0; i <= id; i++) { answer += "a"; } } else { // bだったら一番小さいconstantを使用する int id = -1; for (int i = 0; i < n; i++) { if (constants[i] != 0) { id = i; constants[i]--; break; } } if (id == -1) return answer; for (int i = 0; i <= id; i++) { answer += "b"; } } // ab入れ替え curA = !curA; } } };
