Codeforces Round #366 (Div. 2)
A. Hulk
問題文
解法
問題文の通りに書くだけ。
感想
究極のやるだけ。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 100000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; int n; string s[2] = {"I hate ", "I love "}; int main(){ cin >> n; rep(i,n){ if(i == n-1){ if(n%2){ cout << s[0] << "it" << endl; } else{ cout << s[1] << "it" << endl; } break; } cout << s[i%2] << "that "; } }
B. Spider Man
問題文
解法
自明なこととして、同じサイズの円が二つ以上あったらそれらは無視してよい。（勝つ運命にあるほうが相手と同じ動きをすればよい）
奇数個で構成される円は片方が適当に分割しても、もう一方が残った円のうち大きいほうを少ないほうの円ともう一つの円に分割することで奇数個の円を残すことができるので、結局は1の円と同じであり、無視してよい。
偶数個で構成される円は片方が半分に割ることで1ターン分稼げるので、偶数個の円が来るたびに勝者が変わる。
よって、解ける。
感想
典型っちゃ典型なのかもしれない。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 100000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; int n; int ans = 2; int main(){ cin >> n; rep(i,n){ int a; scanf("%d",&a); if(a%2 == 0){ if(ans == 2) ans = 1; else ans = 2; } printf("%d\n",ans); } }
C. Thor
問題文
解法
実装するだけ。
queueを使うと楽。
感想
C問題にしてはかなり簡単な気がする。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 100000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; int n, q; int counter = 0; int addcnt = 0; queue<int> ask; queue<int> que[300000]; int main(){ scanf("%d%d",&n,&q); int ans = 0; rep(i,q){ int ty, x; scanf("%d%d",&ty,&x); x--; if(ty == 1){ que[x].push(addcnt); addcnt++; ask.push(x); ans++; } else if(ty == 2){ ans -= que[x].size(); while(!que[x].empty()) que[x].pop(); } else{ x++; if(counter < x){ int cnt = x-counter; for(int j = counter; j < x; j++){ if(que[ask.front()].size() != 0 && que[ask.front()].front() == j){ que[ask.front()].pop(); ans--; } ask.pop(); } counter = x; } } printf("%d\n",ans); } }
D. Ant Man
問題文
解法
巡回セールスマンっぽいが、もちろんサイズ的にそんなわけはない。
dp[今いる場所][右隣に移動する回数]というようなdpをもってやれば解ける。
しかし、ｽﾀｰﾄ位置とゴール位置によって往復するかどうかが一部変化するので実装がややこしい。
感想
全く解法がわからず、editorialとか他の人のコードを読んで理解した。
コードを読み込みすぎた結果、ほとんど覚えてしまったので自分で実装したと言えるのかは怪しい。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const long long int INF = 100000000000000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; int n, s, e; ll x[5000], a[5000], b[5000], c[5000], d[5000]; ll dp[5010][5010]; int main(){ scanf("%d%d%d",&n,&s,&e); s--; e--; rep(i,n) scanf("%d",x+i); rep(i,n) scanf("%d",a+i); rep(i,n) scanf("%d",b+i); rep(i,n) scanf("%d",c+i); rep(i,n) scanf("%d",d+i); rep(i,5010) rep(j,5010) dp[i][j] = INF; if(s == 0){ dp[0][0] = d[0]; } else if(e == 0){ dp[0][1] = b[0]; } else{ dp[0][1] = b[0]+d[0]; } for(int i = 1; i < n; i++) rep(j,n){ if(dp[i-1][j] == INF) continue; ll dis = x[i]-x[i-1]; int k = j; if(e < i) k--; if(s < i) k++; ll val = dp[i-1][j]+dis*(k+j); if(j == 0 && k == 0) continue; if(k < 0) continue; if(i == s){ dp[i][j] = min(dp[i][j],val+d[i]); if(j > 0)dp[i][j-1] = min(dp[i][j-1],val+c[i]); } else if(i == e){ dp[i][j+1] = min(dp[i][j+1],val+b[i]); if(k > 0) dp[i][j] = min(dp[i][j],val+a[i]); } else{ if(j > 0) dp[i][j] = min(dp[i][j],val+b[i]+c[i]); if(k > 0) dp[i][j] = min(dp[i][j],val+a[i]+d[i]); if(j > 0 && k > 0) dp[i][j-1] = min(dp[i][j-1],val+a[i]+c[i]); dp[i][j+1] = min(dp[i][j+1],val+b[i]+d[i]); } } cout << dp[n-1][0] << endl; }
E. Black Widow
問題文
解法
括弧に閉じられている論理式を頂点をみなし、絶対値が同じ数を含んでいる頂点同紙に辺を張ると、問題文より、一つの頂点からは最大でも二本しか辺が張られないため、パスもしくは閉路のみが残る。
パスや閉路についてはそれぞれ独立にdpを用いることで真偽それぞれの場合の数を求めることができるので、あとはそれらをまとめるdpをすればよい。
感想
前に諦めてeditorialを読んで理解はしたものの、実装辛そうだったから敬遠していたが、実装できてよかった。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) #define PI 3.1415926535897932384626433832795028841971 #define INF 100000000 #define EPS 1e-10 #define MOD 1000000007 using namespace std; typedef long long ll; typedef pair<int,int> P; int n,m; vector<int> v[100001]; vector<int> id[100001]; bool saw[100001]; bool used[100001]; int same[100001]; ll ans[2][2]; int ho = 0, ge = 1; int hoho = 0, gege = 1; ll dp[2][2][2][2]; void func(int x){ //cout << dp[0][gege][0][0] << " " << dp[0][gege][0][1] << " " << dp[0][gege][1][0] << " " << dp[0][gege][1][1] << endl; if(saw[x]){ ll ret[2]; rep(i,2) ret[i] = 0; rep(i,2) rep(j,2) rep(k,2){ ret[j^(i|k)] += dp[i][gege][j][k]; } ans[ho][0] = (ans[ge][0]*ret[0]+ans[ge][1]*ret[1])%MOD; ans[ho][1] = (ans[ge][0]*ret[1]+ans[ge][1]*ret[0])%MOD; swap(ho,ge); return; } saw[x] = true; if(v[x].size() == 1){ ll check = 0; ll ret[2]; rep(i,2) ret[i] = 0; rep(i,2) rep(j,2) check += dp[0][gege][i][j]; if(check == 2){ if(same[v[x][0]]){ ans[ho][0] = (ans[ge][0]*2)%MOD; ans[ho][1] = (ans[ge][1]*2)%MOD; } else{ ans[ho][0] = (ans[ge][1]*2)%MOD; ans[ho][1] = (ans[ge][0]*2)%MOD; } swap(ho,ge); return; } rep(i,2) rep(j,2){ ret[i^j] += dp[0][gege][i][j]; } ans[ho][0] = (ans[ge][0]*ret[0]+ans[ge][1]*ret[1])%MOD; ans[ho][1] = (ans[ge][0]*ret[1]+ans[ge][1]*ret[0])%MOD; swap(ho,ge); return; } int vv; rep(i,v[x].size()){ if(used[v[x][i]]) continue; vv = v[x][i]; } used[vv] = true; if(id[vv].size() == 1){ ll ret[2]; rep(j,2) ret[j] = 0; rep(i,2) rep(j,2) rep(k,2){ ret[i^(j|k)] += dp[0][gege][i][j]; } ans[ho][0] = (ans[ge][0]*ret[0]+ans[ge][1]*ret[1])%MOD; ans[ho][1] = (ans[ge][0]*ret[1]+ans[ge][1]*ret[0])%MOD; swap(ho,ge); return; } rep(i,2) rep(j,2) rep(k,2) dp[i][hoho][j][k] = 0; rep(i,2){ rep(j,2){ rep(k,2){ rep(l,2){ if(same[vv]){ dp[i][hoho][j^(k|l)][l] += dp[i][gege][j][k]; } else{ dp[i][hoho][j^(k|l)][l^1] += dp[i][gege][j][k]; } } } } } rep(i,2) rep(j,2) rep(k,2) dp[i][hoho][j][k] %= MOD; swap(hoho,gege); rep(j,id[vv].size()){ if(id[vv][j] == x) continue; func(id[vv][j]); } } int main(){ cin >> n >> m; for(int i = 1; i <= m; i++) same[i] = INF; ans[ge][0] = 1; ans[ge][1] = 0; rep(i,n){ int x; scanf("%d",&x); int a; rep(j,x){ scanf("%d",&a); if(same[abs(a)] == INF){ if(a > 0) same[abs(a)] = 2; else same[abs(a)] = -2; } else{ if(same[abs(a)]*a > 0){ same[abs(a)] = 1; } else{ same[abs(a)] = 0; } } v[i].push_back(abs(a)); id[abs(a)].push_back(i); } } for(int i = 1; i <= m; i++){ if(id[i].size() == 0){ ans[ge][0] = (ans[ge][0]*2)%MOD; } } rep(i,n){ if(v[i].size() > 1) continue; if(saw[i]) continue; used[v[i][0]] = true; saw[i] = true; if(id[v[i][0]].size() == 1){ ans[ho][0] = (ans[ge][0]+ans[ge][1])%MOD; ans[ho][1] = (ans[ge][0]+ans[ge][1])%MOD; swap(ho,ge); continue; } rep(j,2) rep(k,2) rep(l,2) rep(u,2) dp[j][k][l][u] = 0; dp[0][gege][1][same[v[i][0]]] = 1; dp[0][gege][0][!same[v[i][0]]] = 1; rep(j,id[v[i][0]].size()){ if(id[v[i][0]][j] == i) continue; func(id[v[i][0]][j]); } } rep(i,n){ if(saw[i]) continue; int ok = 0; rep(j,v[i].size()){ if(id[v[i][j]].size() != 2){ ok++; } } if(ok == 0) continue; used[v[i][0]] = true; used[v[i][1]] = true; if(ok == 2){ ans[ho][0] = (ans[ge][0]+ans[ge][1]*3)%MOD; ans[ho][1] = (ans[ge][0]*3+ans[ge][1])%MOD; swap(ho,ge); saw[i] = true; continue; } rep(j,2) rep(k,2) rep(l,2) dp[j][gege][k][l] = 0; dp[0][gege][0][1] = 1; dp[0][gege][0][0] = 1; rep(j,2){ if(id[v[i][j]].size() == 2){ used[v[i][j]] = false; } } func(i); } rep(i,n){ if(saw[i]) continue; rep(j,id[v[i][0]].size()){ if(id[v[i][0]][j] != i){ saw[id[v[i][0]][j]] = true; } } used[v[i][0]] = true; if(v[i][0] == v[i][1]){ if(same[v[i][0]]){ ans[ho][0] = (ans[ge][0]+ans[ge][1])%MOD; ans[ho][1] = (ans[ge][0]+ans[ge][1])%MOD; } else{ ans[ho][0] = (ans[ge][1]*2)%MOD; ans[ho][1] = (ans[ge][0]*2)%MOD; } swap(ho,ge); continue; } rep(j,2) rep(k,2) rep(l,2) dp[j][gege][k][l] = 0; dp[1][gege][0][same[v[i][0]]] = 1; dp[0][gege][0][!same[v[i][0]]] = 1; func(i); } cout << ans[ge][1] << endl; }
