SRM666 Div1 Easy "WalkOverATree"
解法
一番深い葉ノードへ直進して（復路を戻ることはしない！）歩き終わるのが一番効率的であろう。
これは１の頂点につき１ステップかかる。
残りの枝道はどうあがいても１つの頂点につき２ステップかかる。
ソースコード
vector<int> G[55]; class WalkOverATree { public: int maxNodesVisited(vector<int> parent, int L) { int n = parent.size() + 1; // グラフ初期化 for (int i = 0; i < n; i++) { G[i].clear(); } for (int v = 1; v < n; v++) { int u = parent[v - 1]; G[v].push_back(u); G[u].push_back(v); } // 深さ取得 int depth = dfs(-1, 0); int ans = 1; // まずは直進！ int use = min(L, depth); ans += use; // そして往復！ L -= use; ans += L / 2; ans = min(ans, n); return ans; } // 一番深い葉ノードへの距離を測る int dfs(int p, int c) { int res = 0; for (int i = 0; i < G[c].size(); i++) { if (G[c][i] == p) { continue; } res = max(res, dfs(c, G[c][i]) + 1); } return res; } };
SRM667 Div1 Easy "OrderOfOperations"
解法
dpる。
dp[bit] := メモリの使用状態がbitとするときの、最小時間
dp初期化
メモリを全く使用しない場合、つまりプログラムを動かさないときの時間は0であるため、
dp[0] = 0;
dp更新
現在考えている命令が使用するメモリをnum、現在考えているメモリを状態をbitとすると、
命令を実行するときにかかる時間はcost = num xor (bit & num)となる。
dp[bit | num] = min(dp[bit | num], dp[bit] + cost^2)
dp答え
全ての命令を実行したときの使用メモリの状態をansBitとすると
dp[ansBit]
事後
貪欲でいっちまったぁぁ
ソースコード
const int INF = 500; int num[55]; int dp[1 << 20]; class OrderOfOperations { public: int minTime(vector<string> s) { int n = s.size(); int m = s[0].size(); // num初期化 for (int i = 0; i < n; i++) { int t = 0; for (int j = 0; j < m; j++) { if (s[i][j] == '1') t++; if (j != m - 1) t <<= 1; } num[i] = t; } // dp初期化 for (int b = 0; b < 1 << m; b++) { dp[b] = INF; } dp[0] = 0; for (int b = 0; b < 1 << m; b++) { if (dp[b] == INF) continue; for (int i = 0; i < n; i++) { int nb = b | num[i]; int newM = __builtin_popcount(num[i] ^ (b & num[i])); dp[nb] = min(dp[nb], dp[b] + newM * newM); } } int ansBit = 0; for (int i = 0; i < n; i++) { ansBit |= num[i]; } return dp[ansBit]; } };
SRM668 Div1 Easy "PaintTheRoom"
解法
まず、K = 1ならば必ず"Paint"となる。
K >= 2であれば、R、C、どちらかが偶数であれば"Paint"となり、どちらも奇数であれば"Cannot paint"となる。
なぜどちらも奇数であれば"Cannot paint"であるかというと、まずR = C = 1であればSampleの通り自明である。
R >= 3 または C >= 3の場合について証明してみる。
教室のマス目が白黒で市松模様だったとする。白マスの数がW、黒マスの数がBとする。ちょうどK回ずつ塗らないといけないとなると、白マスの数をW * K回、黒マスの数をB * K回塗らないといけない。ここで、W != B かつ K >= 2なので、W * KとB * Kの差は2以上である。
移動方法が上下左右という事は、マス目は白→黒→白→黒→・・・と塗っていくことになり、塗ったマスで白マスの数と黒マスの数の差が2以上となることはありえない。
これより、R Cどちらも奇数の時、全てのマス目をK回塗る方法はないことになる。
ソースコード
class PaintTheRoom { public: string canPaintEvenly(int R, int C, int K) { bool isEven = (R * C) % 2 == 0; if (isEven || K == 1) { return "Paint"; } else { return "Cannot paint"; } } };
SRM669 Div1 Easy "SubdividedSlimes"
解法
スライムをn回斬ると決めたとき、最終的なミニスライムの大きさがなるべく均一になるように斬ると最もポイントが高くなる。
例えば、スライムの大きさが10、3回斬るとする。その時、ミニスライムは4つになっているが、これが均一になるとよいので、{3, 3, 2, 2}とするとよい。
根拠としては、最後のミニスライムの大きさがそれぞれa, b, c, dだとすると、ポイントはab + ac + ad + bc + bd + cdとなる。これは、a,b,c,dそれぞれが自分以外の要素と掛けたものの総和のため、・・・あれ？
・・ごめん分からない・・・
ソースコード
class SubdividedSlimes { public: int needCut(int S, int M) { for (int K = 1; K < S; K++) { int rem = S; int sum = 0; int d = S / (K + 1); int a = S % (K + 1); for (int i = 0; i < K; i++) { int m = d + (i < a ? 1 : 0); rem -= m; sum += m * rem; } if (sum >= M) return K; } return -1; } };
SRM670 Div1 Easy "Bracket107"
解法
まず、文字列の長さをnとしたときに、LCSがn - 1なcorrect bracket sequenceは必ずある。
根拠は以下の通り
★任意の(を、それより前の位置にある)の前に持ってくることができる
s=( ( ) ( ) )
^
t=( ( ( ) ) )
^
★例外として((()))なやつは、任意の)を(の後に持ってくることができる
s=( ( ( ) ) )
^
t=( ) ( ( ) )
^
よって、任意の文字１つを、任意の場所に移動させてLCSをn-1とした文字列を探索し、correct bracket sequenceであるものを数え上げればよい。
ソースコード
class Bracket107 { public: int yetanother(string s) { int n = s.size(); set<string> ansSet; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // i番目の文字をj番目に移動 string t = s; char c = t[i]; t.erase(i, 1); string cc(1, c); t.insert(j, cc); // 同じ文字列になってしまったら無視 if (s == t) continue; // correct bracket sequenceかな？ int open = 0; for (int k = 0; k < n; k++) { if (t[k] == '(') { open++; } else { open--; } if (open < 0) break; } // correct bracket sequenceならばsetに追加 if (open == 0) ansSet.insert(t); } } return ansSet.size(); } };
SRM671 Div1 Easy "BearCries"
解法
dpる。
dp[i][j][k] := i-1番目までの文字を考えた時に、 既にアンダーバーが付与しており、ペアが組まれていないセミコロンがj個あり アンダーバーが付与しておらず、ペアが組まれていないセミコロンがk個あった時の場合の数
dp初期化
何も考えていないとき、ペアが組まれていないセミコロンの数は0なので、
dp[0][0][0] = 0;
dp更新
i番目の文字がセミコロンだった時、
右目として使う（既にアンダーバーが付与しており、ペアが組まれていないセミコロンとペアを組む）事にすると、
dp[i][j - 1][k] += dp[i][j][k] * j;
左目として使う事にすると
dp[i][j][k + 1] += dp[i][j][k];
i番目の文字がアンダーバーだった場合、
新たな口として使う（アンダーバーが付与していない、ペアが組まれていないセミコロンの口となる）事にすると、
dp[i][j + 1][k - 1] += dp[i][j][k] * k;
口を長くするために使う（アンダーバーが付与している、ペアが組まれていないセミコロンの口となる）事にすると、
dp[i][j][k] += dp[i][j][k] * j;
dp答え
n - 1までの文字を考えたときに、全てのセミコロンはペアを組まれている必要があるので、
dp[n][0][0]
ソースコード
const int MOD = 1000000007; long long dp[202][202][202]; class BearCries { public: int count(string message) { int n = message.size(); // dp初期化 memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1; // dp更新 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { long long val = dp[i][j][k]; if (message[i] == ';') { // 閉じよう if (j > 0) { add(dp[i + 1][j - 1][k], val * j); } // 開けよう add(dp[i + 1][j][k + 1], val); } else { // 閉じれない奴につけよう if (k > 0) { add(dp[i + 1][j + 1][k - 1], val * k); } // 既に閉じれる奴につけよう if (j > 0) { add(dp[i + 1][j][k], val * j); } } } } } // 答え算出 return dp[n][0][0]; } void add(long long& tar, long long val) { tar += val; tar %= MOD; } };
SRM700 Div1 Easy "FindingFriend"
解法
roomSize = 3
leaders = {1, 4, 6, 10}
■所在不明者2, 3はどの部屋？？
leaderが1の部屋に入っているだろう。
答え = 1
■所在不明者5はどの部屋？？
leaderが1, 4のどれかの部屋に入っているだろう
しかし、leaderが1の部屋は2, 3が入っているだろうから人数パンパンである。
↓
leaderが4の部屋に入っているだろう
答え = 1
■所在不明者7, 8, 9はどの部屋？？
leaderが1, 4, 6のどれかの部屋に入っているだろう
しかし、leaderが1の部屋は2, 3が入っているだろうから人数パンパンである。
↓
leaderが4, 6の部屋に入っているだろう
答え = 2
■所在不明者11, 12はどの部屋？？
leaderが1, 4, 6, 10のどれかの部屋に入っているだろう
しかし、leaderが1, 4, 6の部屋は2, 3, 5, 7, 8, 9が入っているだろうから人数パンパンである。
↓
leaderが10の部屋に入っているだろう
答え = 1
ソースコード
class FindingFriend { public: int find(int roomSize, vector<int> leaders, int friendPlace) { int roomCount = leaders.size(); // リーダーじゃないのか？ for (int i = 0; i < roomCount; i++) { if (leaders[i] == friendPlace) return 1; } // 順位が高い順にリーダーを並べ替える sort(leaders.begin(), leaders.end()); int emptyCount = 0; // 定員が空いている部屋の数 int rem = 0; // 定員の空き for (int i = 0; i < roomCount - 1; i++) { emptyCount++; rem += roomSize; if (friendPlace < leaders[i + 1]) return emptyCount; rem -= leaders[i + 1] - leaders[i]; // 部屋がパンパンか？ if (rem == 0) emptyCount = 0; } return emptyCount + 1; } };
