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

Codeforces Round #367 (Div. 2)

codeforces

A. Beru-taxi

問題文

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;

double a, b;
int n;
double ans = 1000000.0;

int main(){
	cin >> a >> b;
	cin >> n;
	rep(i,n){
		double x, y, v;
		cin >> x >> y >> v;
		ans = min(ans,sqrt((a-x)*(a-x)+(b-y)*(b-y))/v);
	}
	printf("%.9f\n",ans);
}

B. Interesting drink

問題文

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 = 1000000009;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int x[100001];
int q;

int main(){
	scanf("%d",&n);
	rep(i,n) scanf("%d",x+i);
	sort(x,x+n);
	x[n] = INF;
	scanf("%d",&q);
	rep(i,q){
		int m;
		scanf("%d",&m);
		int s = 0, e = n, mid;
		while(e-s > 1){
			mid = (e+s)/2;
			if(x[mid] <= m) s = mid;
			else e = mid;
		}
		if(x[0] > m) printf("0\n");
		else printf("%d\n",s+1);
	}
}

C. Hard problem

問題文

codeforces.com

解法

dp[n][反転させるかどうか]のdpをするだけ。

感想

やるだけ。

コード

#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 = 1000000000000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
ll c[100000];
string str[100000], rev[100000];
ll dp[100000][2];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	rep(i,n) cin >> c[i];
	rep(i,n) cin >> str[i];
	rep(i,n){
		rev[i] = str[i];
		reverse(rev[i].begin(),rev[i].end());
	}
	rep(i,n) rep(j,2) dp[i][j] = INF;
	dp[0][0] = 0;
	dp[0][1] = c[0];
	for(int i = 1; i < n; i++){
		if(str[i-1] <= str[i]){
			dp[i][0] = min(dp[i][0],dp[i-1][0]);
		}
		if(rev[i-1] <= str[i]){
			dp[i][0] = min(dp[i][0],dp[i-1][1]);
		}
		if(str[i-1] <= rev[i]){
			dp[i][1] = min(dp[i][1],dp[i-1][0]+c[i]);
		}
		if(rev[i-1] <= rev[i]){
			dp[i][1] = min(dp[i][1],dp[i-1][1]+c[i]);
		}
	}
	ll ans = min(dp[n-1][0],dp[n-1][1]);
	if(ans == INF) ans = -1;
	cout << ans << endl;
}

D. Vasiliy's Multiset

問題文

codeforces.com

解法

各xiを二分木の葉に対応させてそこに出現回数を記録する。
具体的には、xiを上位bitから見ていき、フラグが立っていれば右の子に、フラグが立っていなければ左の子にと遷移していけばよい。
そのような二分木を構築すると、"? x"クエリが来た時、xorを最大化するためには右の子と左の子のどちらに移動するべきかがxのbitを見ればわかるので解ける。

感想

そこまで難しい発想ではないんだけどコンテスト中に解けてよかった。

コード

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

struct v{
	int ex;
	int dep;
	int r, l;
	int number;
} vv[10000000];
int q;
int counter = 1;
int p[30];

void init(){
	rep(i,30) p[i] = (1<<i);
}

void add(int x, int dep, int num){
	vv[num].ex++;
	if(dep == 0){
		vv[num].number = x;
		return;
	}
	if(x&p[dep-1]){
		if(vv[num].r == -1){
			vv[num].r = counter;
			vv[counter].dep = dep-1;
			counter++;
		}
		add(x,dep-1,vv[num].r);
	} else{
		if(vv[num].l == -1){
			vv[num].l = counter;
			vv[counter].dep = dep-1;
			counter++;
		}
		add(x,dep-1,vv[num].l);
	}
}

void del(int x, int dep, int num){
	vv[num].ex--;
	if(dep == 0) return;
	if(x&p[dep-1]){
		del(x,dep-1,vv[num].r);
	} else{
		del(x,dep-1,vv[num].l);
	}
}

int que(int x, int dep, int num){
	int ret = x;
	if(vv[num].ex == 0) return x;
	if(dep == 0) return x^vv[num].number;
	if(x&p[dep-1]){
		if(vv[num].l != -1 && vv[vv[num].l].ex != 0) ret = max(ret,que(x,dep-1,vv[num].l));
		else ret = max(ret,que(x,dep-1,vv[num].r));
	} else{
		if(vv[num].r != -1 && vv[vv[num].r].ex != 0) ret = max(ret,que(x,dep-1,vv[num].r));
		else ret = max(ret,que(x,dep-1,vv[num].l));
	}
	return ret;
}

int main(){
	init();
	cin >> q;
	rep(i,10000000){ vv[i].r = -1; vv[i].l = -1; vv[i].ex = 0;}
	vv[0].dep = 30;
	add(0,30,0);
	rep(i,q){
		char a; int b;
		scanf(" %c%d",&a,&b);
		if(a == '+') add(b,30,0);
		if(a == '-') del(b,30,0);
		if(a == '?') printf("%d\n",que(b,30,0));
	}
}

E. Working routine

問題文

codeforces.com

解法

全ての隣り合ってるセル間に辺をはり、クエリが飛んで来たらswapされる四角形の周囲のセルについてのみ辺を張りかえれば計算量がO(q*(n+m))となって解ける。
n*mの四角形の外に番兵的な用途でマスを追加しておくと実装が楽になる。

感想

わからなかったのでeditorialとか人のコードとか読んで通した。
解法自体は典型なのだが(思いつかなかったので猛省だけど)、辺を張りかえるという部分でやたらバグらせてしまった。

コード

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

struct ver{
	int r, d;
	int val;
} v[1500000];

int n, m, q;

int find(int id, int h, int w){
	int ret = id;
	rep(i,h) ret = v[ret].d;
	rep(i,w) ret = v[ret].r;
	return ret;
}	

int main(){
	scanf("%d%d%d",&n,&m,&q);
	rep(i,n) rep(j,m){
		scanf("%d",&v[(i+1)*(m+1)+j+1].val);
	}
	rep(i,n+1) rep(j,m+1){
		if(i != n) v[i*(m+1)+j].d = (i+1)*(m+1)+j;
		else v[i*(m+1)+j].d = -1;
		if(j != m) v[i*(m+1)+j].r = i*(m+1)+j+1;
		else v[i*(m+1)+j].r = -1;
	}
	rep(i,q){
		int a, b, c, d, h, w;
		scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&h,&w);
		int l1 = find(0,a,b-1);
		int l2 = find(l1,0,w);
		int u1 = find(0,a-1,b);
		int u2 = find(u1,h,0);
		int L1 = find(0,c,d-1);
		int L2 = find(L1,0,w);
		int U1 = find(0,c-1,d);
		int U2 = find(U1,h,0);
		rep(j,h){
			swap(v[l1].r,v[L1].r);
			swap(v[l2].r,v[L2].r);
			l1 = v[l1].d; L1 = v[L1].d;
			l2 = v[l2].d; L2 = v[L2].d;
		}
		rep(j,w){
			swap(v[u1].d,v[U1].d);
			swap(v[u2].d,v[U2].d);
			u1 = v[u1].r; U1 = v[U1].r;
			u2 = v[u2].r; U2 = v[U2].r;
		}
	}
	int st = find(0,1,1);
	rep(i,n){
		int now = st;
		rep(j,m){
			if(j == 0) printf("%d",v[now].val);
			else printf(" %d",v[now].val);
			now = v[now].r;
		}
		printf("\n");
		st = v[st].d;
	}
}