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;
}
}
