SRM 648 div2
SRM648 div2の参加記
結果
ooo 4th 1072-> 1237
最近はいい感じにレートが上がっていたが、まさかdiv1に上がれるとは思わなかった。
CodeFestivalの予選に落ちたり、SRMの過去最低レートをとったりしてプロコンのモチベーションがだだ下がりだったが、CodeThanksから徐々にモチベーションを取り戻して、真面目に問題を解くようになってようやくdiv1に上がれて正直ほっとしてます。
SRMを始めた頃にはすぐに大学院に入る頃までにはdiv1に上がるだろうと軽く考えてたが結局一年ぐらいかかってしまった。
Easy KitayutaMart2
問題
kitayutaはT円持っていて、それぞれの商品は購入するごとにK*2^i円となる。kitayutaが購入した商品の数は?
解法
実際にシミュレーションコード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class KitayutaMart2 { public: int numBought(int K, int T) { int result; ll sum = K; if (sum > T)return 0; ll tmp = K; for (int i = 2; ; i++){ tmp *= 2; sum += tmp; if (sum > T){ return i - 1; } } return result; } };
焦りすぎて問題分を勘違いして再提出をしてしまった。
Medium Fragile2
問題
グラフの隣接行列が与えられるので、ある２つの頂点を消すことによって連結成分が増加するペアの数を求めよ。解法
最初に深さ優先探索を行い、連結成分の個数を求め。実際に、全部の消去するペアに対して再び深さ優先探索を行い連結成分の個数を求め増加したならば+1
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class Fragile2 { public: int V; vector<vector<int> > g; bool visit[30]; void dfs(int pos, int a, int b){ visit[pos] = true; for (int i = 0; i < g[pos].size(); i++){ if (!visit[g[pos][i]] && g[pos][i] != a && g[pos][i] != b){ dfs(g[pos][i], a, b); } } return ; } void dfs1(int pos){ visit[pos] = true; for (int i = 0; i < g[pos].size(); i++){ if (!visit[g[pos][i]]){ dfs1(g[pos][i]); } } return ; } int countPairs(vector<string> graph) { int result; result = 0; V = graph.size(); g.resize(V); for (int i = 0; i < 30; i++){ visit[i] = false; } for (int i = 0; i < graph.size(); i++){ for (int j = i + 1; j < graph.size(); j++){ if (graph[i][j] == 'Y'){ g[i].push_back(j); g[j].push_back(i); } } } int ini = 0; for (int i = 0; i < graph.size(); i++){ if (!visit[i]){ dfs1(i); ini++; } } for (int i = 0; i < graph.size(); i++){ for (int j = i + 1; j < graph.size(); j++){ int res = 0; for (int k = 0; k < 30; k++){ visit[k] = false; } for (int k = 0; k < graph.size(); k++){ if (k != i && k != j && !visit[k]){ dfs(k, i, j); res++; } if (res > ini){ result++; } } } return result; } };
単純だけどちょっと実装が面倒くさい
Hard ABC
問題
以下の条件を満たす文字列を一つ返せ・A,B,Cの３つから構成されるN文字
・S[i] < S[j](0 <= i < j <= N - 1)のペアがちょうどK個
解法
bool dp[今なん文字目か][Aの個数][Bの個数][ペアの個数]を探索済みかどうかのメモ化再帰で解いた。例えば
Aを追加したならばペアの個数は増加せず
Bを追加したならばペアの個数は(現在のペアの個数) + (Aの個数)
Cを追加したならばペアの個数は(現在のペアの個数) + (Aの個数) + (Bの個数)
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class ABC { public: bool dp[33][33][33][500]; int KK; int NN; string ans; bool ok; void memo(int pos, int a, int b, int cnt, string str){ if (ok)return ; if (pos > NN)return ; if (cnt > KK)return ; if (dp[pos][a][b][cnt] == true){ return ; } if (pos == NN && cnt == KK){ ok = true; ans = str; return; } for (int i = 0; i < 3; i++){ int sum = cnt; if (i == 0){ if (sum > KK)continue; memo(pos + 1, a + 1, b, sum, str + 'A'); } else if (i == 1){ sum += a; if (sum > KK)continue; memo(pos + 1, a, b + 1, sum, str + 'B'); } else { sum += a + b; if (sum > KK)continue; memo(pos + 1, a, b, sum , str + 'C'); } } dp[pos][a][b][cnt] = true; } string createString(int N, int K) { string result; rep(i, 33){ rep(j, 33){ rep(k, 33){ rep(l, 500){ dp[i][j][k][l] = false; } } } } result = ""; ans = ""; NN = N; KK = K; memo(0, 0, 0, 0, ""); result = ans; return result; } };
こういうDPは結構典型な気がするので、落とさず取って行きたい。
個人的には
G: 通勤電車と気分 - code thanks festival 2014 A日程（オープンコンテスト） | AtCoder
を解いてからDPの考え方がちょっとつかめた気がします。
