JOI2018/2019予選参加記

520点。そこそこ相性がよかったので楽だった（実装はボロボロでしたが）

1問目：ソーシャルゲーム
Cの制約見えてなくて1WA。何やってるんだ。

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int a,b,c;

void input(){
	cin>>a>>b>>c;
	return;
}

void solve(){
	for(int i=1;i<=1000000;i++){
		if(i%7==0)c-=b;
		c-=a;
		if(c<=0){
			cout<<i<<endl;
			return;
		}
	}
	return;
}

int main(){
	input();
	solve();
	return 0;
}

2問目：すごろくと駒
1問目より楽...?

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int n,m,a[1010],b[1010];

void input(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	cin>>m;
	for(int i=0;i<m;i++)cin>>b[i];
	return;
}

void solve(){
	a[n]=2020;
	for(int i=0;i<m;i++){
		if(a[b[i]-1]+1==a[b[i]])continue;
		a[b[i]-1]++;
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<endl;
	}
	return;
}

int main(){
	input();
	solve();
	return 0;
}

3問目：マルバツスタンプ
適当な貪欲を書くと通る。(番兵の意味とは)

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int n,ans;
bool flx,flo;
string s;

void input(){
	cin>>n>>s;
	s+='$';
	return;
}

void solve(){
	for(int i=0;i<n;i++){
		if(!flx&&s[i]=='X')flx=true;
		if(!flo&&s[i]=='O')flo=true;
		if(flx&&flo){
			flx=false;
			flo=false;
			ans++;
		}
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

4問目：日本沈没
島が分断されるか、消えるかを見て足し引きすればよし。座圧して、高さが低い順に島を見たときに、両隣りが沈んでいるか、まだ残っているか、否かで場合分けしていけばOK。

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()


int n,a[100010],ans,cnt;
vector<int>v;
vector<int>it[100010];
bool deep[100010];

void input(){
	cin>>n;
	v.eb(0);
	for(int i=0;i<n;i++){
		cin>>a[i];
		deep[i]=true;
		v.eb(a[i]);
	}
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
	for(int i=0;i<n;i++){
		int num=lower_bound(ALL(v),a[i])-v.begin();
		it[num].eb(i);
	}
	return;
}

void solve(){
	for(int i=0;i<v.size();i++){
		for(int j=0;j<it[i].size();j++){
			int now=it[i][j];
			if(now==0){
				if(!deep[1])cnt--;
				deep[0]=false;
			}
			else if(now==n-1){
				if(!deep[n-2])cnt--;
				deep[n-1]=false;
			}
			else{
				if(deep[now-1]&&deep[now+1])cnt++,deep[now]=false;
				else if(!deep[now-1]&&!deep[now+1])cnt--,deep[now]=false;
				else deep[now]=false;
			}
		}
		ans=max(ans,cnt+1);
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

5問目：イルミネーション
i番目の木を飾った時、次に飾ることができる最も近い木へ遷移するDP。どこから飾れるかは、遅延セグ木を用いて求めた。どこにも属していない木は最後にまとめて足しました。
(セグ木は長いのでカットしてあります)

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()

int n,m;
P p[200010];
vector<ll>v;
ll a[200010],dp[200010],ans;


void input(){
	cin>>n>>m;
	v.resize(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>p[i].sc>>p[i].fr;
		p[i].fr--,p[i].sc--;
	}
	sort(p,p+m);
	return;
}

void solve(){
	LazySegmentTree nex(v);
	for(int i=0;i<m;i++){
		nex.update(p[i].sc,p[i].fr+1,p[i].fr+1);
	}
	for(int i=0;i<n;i++){
		dp[i+1]=max(dp[i+1],dp[i]);
		if(nex.find(i,i+1)==0)continue;
		dp[nex.find(i,i+1)]=max(dp[nex.find(i,i+1)],dp[i]+a[i]);
		ans=max(ans,dp[nex.find(i,i+1)]);
		ans=max(dp[i+1],ans);
	}
	for(int i=0;i<n;i++){
		if(nex.find(i,i+1)==0)ans+=a[i];
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

6問目：座席
20点だけもらった。4進数にして残っている人数を管理し、前の人が誰かを持っておきながら配列を使いまわす（メモリがきつい）。同じ国の人の並べ方は最後に階乗をかければOK。100点は知りません。

#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()

int n,a[110];
int dp[2][1100000][11];
int sum,till,ans;
int fact[40];
vector<int>v[1100000];

void input(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	return;
}

void solve(){
	if(n>10)return;
	fact[0]=1;
	for(int i=0;i<n;i++){
		till+=fact[i]*a[i];
		fact[i+1]=fact[i]*4;
	}
	for(int i=1;i<=till;i++){
		int c=i;
		while(true){
			v[i].eb(c%4);
			c/=4;
			if(c<4){
				v[i].eb(c);
				break;
			}
		}
	}
	for(int i=0;i<n;i++){
		dp[0][till-fact[i]][i]=1;
	}
	for(int i=1;i<sum;i++){
		for(int j=1;j<=till;j++){
			for(int k=0;k<n;k++){
				if(dp[(i-1+2)%2][j][k]==0)continue;
				for(int l=0;l<n;l++){
					if(k==l||k==l-1||k==l+1)continue;
					if(l>=v[j].size())continue;
					if(v[j][l]==0)continue;
					int s=j-fact[l];
					dp[i%2][s][l]+=dp[(i-1+2)%2][j][k];
					dp[i%2][s][l]%=10007;
				}
			}
		}
		for(int j=0;j<=till;j++){
			for(int k=0;k<n;k++){
				dp[(i-1+2)%2][j][k]=0;
			}
		}	
	}
	for(int i=0;i<n;i++){
		ans+=dp[(sum+1)%2][0][i];
		ans%=10007;
	}
	for(int i=0;i<n;i++){
		while(a[i]){
			ans*=a[i];
			a[i]--;
			ans%=10007;
		}
	}
	cout<<ans<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}