読者です 読者をやめる 読者になる 読者になる

Codeforces Round #366 (Div. 2)

A. Hulk

問題文

codeforces.com

解法

問題文の通りに書くだけ。

感想

究極のやるだけ。

コード

#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

問題文

codeforces.com

解法

自明なこととして、同じサイズの円が二つ以上あったらそれらは無視してよい。(勝つ運命にあるほうが相手と同じ動きをすればよい)
奇数個で構成される円は片方が適当に分割しても、もう一方が残った円のうち大きいほうを少ないほうの円ともう一つの円に分割することで奇数個の円を残すことができるので、結局は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

問題文

codeforces.com

解法

実装するだけ。
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

問題文

codeforces.com

解法

巡回セールスマンっぽいが、もちろんサイズ的にそんなわけはない。
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

問題文

codeforces.com

解法

括弧に閉じられている論理式を頂点をみなし、絶対値が同じ数を含んでいる頂点同紙に辺を張ると、問題文より、一つの頂点からは最大でも二本しか辺が張られないため、パスもしくは閉路のみが残る。
パスや閉路についてはそれぞれ独立に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;
}