A
日本語を読む
紛失
B
グイッと実装.stringstreamは便利
#include <bits/stdc++.h> using namespace std; // 頭が整理されてないまま書いた糞コード int main(){ string S; int a,b,c,d; while( cin >> S && S != "#" ){ cin >> a >> b >> c >> d; for(int i = 0 ; i < S.size() ; i++){ if( S[i] == '/' ) S[i] = ' '; } vector<string> to; stringstream ss(S); string t; while( ss >> t ){ string a; for( auto c : t ){ if( '0' <= c && c <= '9' ){ a += string(c-'0',' '); }else{ a += c; } } to.push_back(a); } swap(to[a-1][b-1],to[c-1][d-1]); string ans; for( auto l : to ){ string a = ""; for(int i = 0 ; i < l.size() ; ){ if( l[i] == 'b' ) a += 'b', i++; else{ int j = i; while( j < l.size() and l[j] == ' ' ) j++; a += '0'+j-i; i = j; } } ans += a + "/"; } cout << ans.substr(0,ans.size()-1) << endl; } }
C
座圧してセルの内外判定する気が起きなかったので平面走査
#include <bits/stdc++.h> using namespace std; // 計算量は O(N+窓の周長) int main(){ int N; while( cin >> N && N){ map<int,vector< pair<int,int> > > seg; for(int i = 0 ; i < 50000 ; i++) seg[i] = {}; //(1) 窓の入力 & x軸に平行な線分のみをy座標毎に列挙 int px,py; int sx,sy; for(int i = 0 ; i < N ; i++){ int x,y; cin >> x >> y; x += 20000; y += 20000; if(i){ if( y == py ){ int a = x; int b = px; if( b < a ) swap(a,b); seg[y].push_back({a,b}); } }else sx = x, sy = y; px = x; py = y; } if( sy == py ){ int a = sx; int b = px; if( b < a ) swap(a,b); seg[sy].push_back({a,b}); } // (2) カーテンの入力 & カーテンの範囲を求める int x1 = 1e9,x2 = -1e9,y1 = 1e9,y2 = -1e9; for(int i = 0 ; i < 4 ; i++){ int x,y; cin >> x >> y; x += 20000; y += 20000; x1 = min(x1,x); x2 = max(x2,x); y1 = min(y1,y); y2 = max(y2,y); } // 平面走査 & 正直あんましimosしてない vector<int> imos(50000); long long allans = 0; long long innerans = 0; long long innertot = 0; long long alltot = 0; for( auto vec : seg){ int y = vec.first; for(auto s : vec.second ){ for(int x = s.first ; x < s.second ; x++){ imos[x] ^= 1; // for inner if( (x1 <= x and x < x2) ){ if( imos[x] ) innertot += 1; else innertot -= 1; } // for all if( imos[x] ) alltot += 1; else alltot -= 1; } } // for all allans += alltot; // for inner if( (y1 <= y && y < y2) ){ innerans += innerans; } } cout << allans - innerans << endl; } }
D
本質は強連結成分分解なのですが,O(N+M)のアルゴリズム使わなくてもO(N3)のワーシャルフロイドっぽい実装で代替できます(N:頂点数,M:辺数).
#include <bits/stdc++.h> using namespace std; int main(){ int N; while(cin >> N && N){ bool g[110][110]={}; bool g_src[110][110]={}; int in[110] = {}; double p[110]; for(int i = 0 ; i < N ; i++){ int m; cin >> p[i] >> m; while(m--){ int j; cin >> j; --j; g[i][j] = true; g_src[i][j] = true; } } for(int i = 0 ; i < N ; i++) g[i][i] = true; for(int i = 0 ; i < N ; i++) for(int j = 0 ; j < N ; j++) for(int k = 0 ; k < N ; k++) g[j][k] |= g[j][i] & g[i][k]; bool used[110] = {}; int color[110] = {}; double p_to_col[110] = {}; // 強連結成分分解 for(int i = 0 ; i < N ; i++){ if( used[i] ) continue; double bad = 1.0; for(int j = 0 ; j < N ; j++){ if( used[j] == false and g[i][j] && g[j][i] ){ bad *= p[j]; used[j] = true; color[j] = i; } } p_to_col[i] = bad; } // 入次数数える for(int i = 0 ; i < N ; i++){ for(int j = 0 ; j < N ; j++){ if( g_src[i][j] and color[i] != color[j] ){ in[j]++; } } } // 入次数0の頂点のみに着目 double ans = 1.0; for(int i = 0 ; i < N ; i++){ if( in[i] == 0 and color[i] == i ){ ans *= 1 - p_to_col[i]; } } printf("%.10lf\n",ans); } }
E
よく考えるとdはソートしてよさそうなのでソートすると,布団を片付けることを一切考えなくて良い状態になってハッピー. 頭が悪いので遷移に全ての部分集合をぶち込んでいるが,遷移を工夫すれば計算量落ちます.
#include <bits/stdc++.h> using namespace std; // O(M*3^N) int s[110],d[110]; int N,M; int dp[110][1<<16]; vector<int> bit[1<<15]; int sum[1<<16]; int dfs(int x,int bit){ if( x == M ) return 0; if( dp[x][bit] != -1 ) return dp[x][bit]; int ans = 1e9; /*for(int i = 0 ; i < (1<<N) ; i++){ if( bit & i ) continue; ans = min(dfs(x+1,bit|i)+abs(sum[i|bit]-d[x]),ans); }*/ // 上と下は等価 int sup = ((1<<N)-1)^bit; int i = sup; do{ ans = min(dfs(x+1,bit|i)+abs(sum[i|bit]-d[x]),ans); i = (i-1)⊃ } while( i != sup ); return dp[x][bit] = ans; } int main(){ int t = 0; while( cin >> N >> M && N ){ memset(dp,-1,sizeof(dp)); for(int i = 0 ; i < N ; i++) cin >> s[i]; for(int i = 0 ; i < M ; i++) cin >> d[i]; for(int i = 0 ; i < (1<<N) ; i++){ int t = 0; for(int j = 0 ; j < N ; j++){ if( i >> j & 1 ){ t += s[j]; } } sum[i] = t; } sort(d,d+M); cout << dfs(0,0) << endl; } }
G
全てきひろちゃんとa3636takoが考えた.実装しただけ.
#include <bits/stdc++.h> using namespace std; long long mod = (int)1e9 + 7; long long b_pow(long long a,long long b){ return b ? b_pow(a*a%mod,b/2) * (b&1?a:1) % mod : 1; } #define CCCCCC 4000000 long long f[4000010]; long long inv[4000010]; long long ncr(long long a,long long b){ //cout << a << " " << b << endl; assert( b <= a ); return f[a] * inv[a-b] % mod * inv[b] % mod; } int main(){ // N!とN!の逆元を全て求めとく f[0] = 1; for(int i = 1 ; i <= CCCCCC ; i++) f[i] = f[i-1] * i % mod; for(int i = 0 ; i <= CCCCCC ; i++) inv[i] = b_pow(f[i],mod-2); int A,B,C,Sx,Sy; while( cin >> A >> B >> C >> Sx >> Sy and A+B+C ){ if( A == 0 and B == 0 ){ if( Sx != Sy ) cout << 0 << endl; else cout << ncr( Sx + C - 1, C - 1 ) << endl; continue; } if( A == 0 ){ swap(A,B); swap(Sx,Sy); } long long ans; if( B == 0 ){ ans = ncr(Sx-Sy-1,A-1) * ncr( (A+C-1) + Sy, A+C-1) % mod; }else{ ans = 0; for(int a = A ; a <= Sx ; a++){ long long X = ncr(a+A-1-A,A-1); int b = Sy - Sx + a; if( b < B ) continue; long long Y = ncr(b+B-1-B,B-1); long long Z = ncr( (A+B+C-1) + (Sx-a), A+B+C-1); ans += X * Y % mod * Z % mod; ans %= mod; } } cout << ans * f[A+B+C] % mod * inv[A] % mod * inv[B] % mod * inv[C] % mod << endl; } }