snuke21

https://snuke21.contest.atcoder.jp/
すぬけのお誕生日コンテストでした。

上位 6 位の人です。おめでとうございます。
1. cgy4ever (78)
2. semiexp (78)
3. IQモンスター (70)
4. ຣസںƙᘓ (66)
5. yutaka1999 (54)
6. uwi (50)

簡単な解説をします

A

これはやるだけです。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

int main(void){
	ll n;
	
	cin >> n;
	ll x = (ll)(sqrt(n * 8.0 + 1.0) / 2.0);
	
	if(x * (x + 1) / 2 == n){
		cout << x << endl;
	} else {
		cout << -1 << endl;
	}
	
	return 0;
}

B

前にある s から順に greedy に使うかどうか決定していきます。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

char buf[100010];

int N,K;
string s;
int cnt[100010];
bool big[100010];
bool alive[100010];

int main(void){
	int i;
	
	cin >> K;
	scanf("%s", buf);
	s = buf;
	N = s.length();
	
	for(i=N-1;i>=0;i--){
		cnt[i] = cnt[i+1];
		if(s[i] == 's') cnt[i]++;
	}
	
	for(i=N-1;i>=0;i--){
		big[i] = big[i+1];
		if(s[i] > 's') big[i] = true;
		if(s[i] < 's') big[i] = false;
	}
	
	REP(i,N) if(s[i] == 's'){
		if(K == 0){
			alive[i] = true;
		} else if(K == cnt[i]){
			alive[i] = false;
			K--;
		} else if(big[i]){
			alive[i] = true;
		} else {
			alive[i] = false;
			K--;
		}
	}
	
	string ans;
	REP(i,N) if(s[i] != 's' || alive[i]) ans += s[i];
	printf("%s\n", ans.c_str());
	
	return 0;
}

C

簡単な bid dp です

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

char buf[20];

int N;
int mask[10010];
int dp[(1<<12)];

int main(void){
	int i,j;
	
	cin >> N;
	REP(i,N){
		scanf("%s", buf);
		REP(j,12) if(buf[j] == 'o') mask[i] |= (1<<j);
	}
	
	for(i=(1<<12)-1;i>=0;i--) REP(j,N) if((i | mask[j]) > i) dp[i] = max(dp[i], dp[i|mask[j]] + 1);
	
	cout << dp[0] << endl;
	
	return 0;
}

D

たとえば t = "01001" のとき、t が s の subsequence になるのは
s = (1..1)0(0..0)1(1..1)0(1..1)0(0..0)1(任意の文字列)
となるときです。この性質を使うと解けます。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;
#define MOD 1000000007ll

ll comb[4010][4010];

ll func(int sum, int groups){
	if(groups == 0){
		if(sum == 0) return 1;
		return 0;
	}
	return comb[sum+groups-1][sum];
}

int main(void){
	int A,B,C,D,i,j;
	
	REP(i,4010) REP(j,i+1){
		if(j == 0 || j == i) comb[i][j] = 1;
		else comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
	}
	
	cin >> A >> B >> C >> D;
	
	swap(A, C); C -= A;
	swap(B, D); D -= B;
	
	ll ans = 0;
	REP(i,C+1) REP(j,D+1){
		ll tmp = comb[i+j][i] * func(C-i, B) % MOD * func(D-j, A) % MOD;
		ans = (ans + tmp) % MOD;
	}
	
	cout << ans * comb[A+B][A] % MOD << endl;
	
	return 0;
}

E

トーナメントグラフ G の強連結成分の個数は、
G の頂点集合の non-empty subset S であって
S の中から外へ行く辺がないようなものの個数と一致します。
この性質を使うと解けます。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;
#define MOD 1000000007ll

ll F[100010];

ll power(ll x, ll n){
	if(n == 0) return 1;
	ll y = power(x, n/2);
	y = y * y % MOD;
	if(n%2 == 1) y = y * x % MOD;
	return y;
}

ll comb(int N, int K){
	return F[N] * power(F[K], MOD-2) % MOD * power(F[N-K], MOD-2) % MOD;
}

int main(void){
	int N,i;
	
	F[0] = 1;
	for(i=1;i<=100000;i++) F[i] = F[i-1] * i % MOD;
	
	cin >> N;
	
	ll ans = 0;
	REP(i,N){
		ll edge = (ll)i * (i-1) / 2 + (ll)(N-i) * (N-i-1) / 2;
		ll tmp = comb(N, i) * power(2, edge) % MOD;
		ans = (ans + tmp) % MOD;
	}
	
	cout << ans << endl;
	
	return 0;
}

F

区間を分割して max + second max を最小化する問題です。

1. max を最小化する場合
2. max が元からあった区間である場合

の二通りがあります。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

int N,K,L;
int x[100010];

double min_max(void){
	int i,j;
	double low = 0.0, high = L;
	
	REP(i,100){
		double mid = (low + high) / 2.0;
		ll sum = 0;
		REP(j,N) sum += (ll)(x[j] / mid);
		if(sum <= K) high = mid; else low = mid;
	}
	
	return high;
}

int main(void){
	int i,j;
	
	cin >> L >> N >> K;
	x[N] = L;
	REP(i,N) scanf("%d", &x[i]);
	REP(i,N) x[i] = x[i+1] - x[i];
	
	double ans = 2.0 * min_max();
	
	sort(x, x+N);
	int l = -1, r = N-1;
	while(r - l > 1){
		int m = (r + l) / 2;
		ll sum = 0;
		REP(i,N) sum += (ll)(x[i] - 1) / x[m];
		if(sum <= K) r = m; else l = m;
	}
	
	double tmp = x[r];
	x[r] = x[N-1];
	N--;
	double tmp2 = min_max();
	ans = min(ans, tmp + tmp2);
	
	ans /= 2.0;
	printf("%.12f\n", ans);
	
	return 0;
}

G

三頂点 (g, s, b) の組であって
辺 s -> g, b -> g, b -> s が存在せず、かつ g, s, b からその他の頂点への変がないものを数えます。
g -> s, g -> b, s -> b が存在するかどうかによって場合わけします。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

int N,M;
vector <int> graph[100010];
int deg[100010],deg2[100010];

int main(void){
	int i,j,a,b;
	
	cin >> N >> M;
	REP(i,M){
		scanf("%d%d", &a, &b);
		a--; b--;
		graph[b].push_back(a);
	}
	
	REP(i,N){
		set <int> s;
		REP(j,graph[i].size()) s.insert(graph[i][j]);
		graph[i].clear();
		snuke(s,itr) graph[i].push_back(*itr);
	}
	
	REP(i,N) deg[i] = graph[i].size();
	
	int leaf = 0;
	REP(i,N) if(deg[i] == 0) leaf++;
	ll ans = (ll)leaf * (leaf - 1) * (leaf - 2);
	
	REP(i,N) if(deg[i] == 1){
		int p = graph[i][0];
		if(deg[p] == 0) ans += (leaf - 1) * 3;
		if(deg[p] == 1 && deg[graph[p][0]] == 0) ans++;
		deg2[p]++;
	}
	
	REP(i,N) if(deg[i] == 2){
		int p = graph[i][0], q = graph[i][1];
		if(deg[p] == 0 && deg[q] == 0) ans += 2;
		if(deg[p] == 0 && deg[q] == 1 && graph[q][0] == p) ans++;
		if(deg[p] == 1 && deg[q] == 0 && graph[p][0] == q) ans++;
	}
	
	REP(i,N) if(deg[i] == 0) ans += (ll)deg2[i] * (deg2[i] - 1);
	
	cout << ans << endl;
	
	return 0;
}

H

C >= A+B ならば YES です。
また、ord 2 で考えると C <= A+B-80 ならば NO であることがわかります。
その他の場合は C+1, C+2, ..., A+B の素因数を全部チェックします。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

ll ord(ll N, ll p){
	ll ans = 0;
	while(N > 0){
		N /= p;
		ans += N;
	}
	return ans;
}

bool check(ll A, ll B, ll C){
	if(C >= A + B) return true;
	if(C < A + B - 80) return false;
	
	for(ll x=C+1;x<=A+B;x++){
		ll y = x;
		for(ll p=2;p*p<=y;p++) if(y % p == 0){
			while(y % p == 0) y /= p;
			if(ord(A, p) + ord(B, p) > ord(C, p)) return false;
		}
		if(y > 1 && ord(A, y) + ord(B, y) > ord(C, y)) return false;
	}
	
	return true;
}

int main(void){
	ll A,B,C;
	
	cin >> A >> B >> C;
	
	bool ans = check(A, B, C);
	cout << (ans ? "YES" : "NO") << endl;
	
	return 0;
}

I

全ての辺の |dx| + |dy| の和が 4000000 以下である必要があるので、|dx| + |dy| の小さいほうから詰め込みます。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

struct edge {int dx,dy;};

bool operator<(const edge &e, const edge &f){
	bool eup = (e.dy > 0 || (e.dy == 0 && e.dx > 0));
	bool fup = (f.dy > 0 || (f.dy == 0 && f.dx > 0));
	if(eup && !fup) return true;
	if(!eup && fup) return false;
	return (ll)e.dx * f.dy > (ll)e.dy * f.dx;
}

vector <edge> v;

int gcd(int x, int y){
	return x ? gcd(y%x, x) : y;
}

int M;
int x[100010],y[100010];

int main(void){
	int cnt=0,peri=0,s,i,j;
	
	// 169, 35242
	
	for(s=1;s<=169;s++) REP(i,s) if(gcd(s, i) == 1){
		int dx = i, dy = s-i;
		REP(j,4){
			edge e = {dx, dy};
			v.push_back(e);
			swap(dx, dy);
			dx = -dx;
		}
	}
	
	s = 170;
	REP(i,120) if(gcd(s, i) == 1){
		int dx = i, dy = s-i;
		REP(j,4){
			edge e = {dx, dy};
			bool bad = false;
			if(dx == 83 && dy == 87) bad = true;
			if(dx == -83 && dy == -87) bad = true;
			if(!bad) v.push_back(e);
			swap(dx, dy);
			dx = -dx;
		}
	}
	
	sort(v.begin(),v.end());
	
	M = v.size();
	REP(i,M-1){
		x[i+1] = x[i] + v[i].dx;
		y[i+1] = y[i] + v[i].dy;
	}
	
	int minx = 0, miny = 0;
	REP(i,M){
		minx = min(minx, x[i]);
		miny = min(miny, y[i]);
	}
	REP(i,M){
		x[i] -= minx;
		y[i] -= miny;
	}
	
	int maxx = 0, maxy = 0;
	REP(i,M){
		maxx = max(maxx, x[i]);
		maxy = max(maxy, y[i]);
	}
	
	int N;
	cin >> N;
	
	if(N > M){
		cout << "NO" << endl;
		return 0;
	}
	
	cout << "YES" << endl;
	REP(i,N) printf("%d %d\n", x[i], y[i]);
	
	return 0;
}

J

三つの飲み物の組であって一つが最大の a、他の一つが最大の b、他の一つが最大の c をもつような組を数えるパートが本質的です。これは

(1)
(i, j, k) の組であって a[i] > a[j], a[i] > a[k], b[i] > b[j], b[i] > b[k] をみたすもの

(2)
(i, j, k) の組であって a[i] > a[j], a[i] > a[k], b[i] > b[j], b[i] > b[k], c[i] > c[j], c[i] > c[k] をみたすもの

などの値を足し引きすることによって求められます。

どちらの場合も i を固定して j, k になれるものが何個あるか数えます。
(1) の場合は a でソートした後 BIT でできます。
(2) の場合も分割統治をすれば BIT でできます。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

typedef long long ll;

#define T (1<<17)
int tree[T];

void init(void){
	int i;
	REP(i,T) tree[i] = 0;
}

void add(int pos, int val){
	for(int i=pos;i<T;i=((i)|(i+1))) tree[i] += val;
}

int sum(int pos){
	int ans = 0;
	for(int i=pos;i>0;i=((i)&(i-1))) ans += tree[i-1];
	return ans;
}

int N;
int a[100010][3];
int p[100010],q[100010],cnt[100010];

void conquer(int L, int R){
	if(R - L == 1) return;
	
	int i;
	int M = (L + R) / 2;
	
	vector <pair <int, pair <int, int> > > v(R-L); // p, id, q
	for(i=L;i<R;i++){
		v[i-L].first = p[i];
		v[i-L].second.first = i;
		v[i-L].second.second = q[i];
	}
	sort(v.begin(),v.end());
	
	REP(i,R-L){
		int p = v[i].first;
		int id = v[i].second.first;
		int q = v[i].second.second;
		if(id < M){
			add(q, 1);
		} else {
			cnt[id] += sum(q);
		}
	}
	
	for(i=L;i<M;i++) add(q[i], -1);
	
	conquer(L, M);
	conquer(M, R);
}

ll func(int id){
	int i;
	
	REP(i,N) p[a[i][(id+1)%3]] = a[i][(id+2)%3];
	
	init();
	
	ll ans = 0;
	REP(i,N){
		ll tmp = sum(p[i]);
		ans += tmp * (tmp - 1) / 2;
		add(p[i], 1);
	}
	
	return ans;
}

int main(void){
	int i,j;
	
	cin >> N;
	REP(i,N) REP(j,3){
		scanf("%d", &a[i][j]);
		a[i][j]--;
	}
	
	ll ans = N + (ll)N * (N-1) / 2 + (ll)N * (N-1) * (N-2) / 6;
	REP(i,3) ans -= func(i);
	
	REP(i,N){
		p[a[i][0]] = a[i][1];
		q[a[i][0]] = a[i][2];
	}
	
	init();
	conquer(0, N);
	
	REP(i,N){
		ans -= cnt[i];
		ans += (ll)cnt[i] * (cnt[i] - 1);
	}
	
	cout << ans << endl;
	
	return 0;
}

L

まず原点 O と点 P, Q を含む最も粗い正方格子を求める問題を考えます。
P を原点に対して 90 度回転した点を P' とすると、

point gcd(point P, point Q){
if(dist(P, O) > dist(Q, O)) swap(P, Q);
if(P == O) return Q;
find integers n, m s.t. dist(P, Q+nP+mP') is minimal
return gcd(P, Q+nP+mP')
}

このような操作をすると原点からの距離が毎回 1/sqrt(2) 倍以下になるので log 回で終わります。
O と gcd(P, Q) を正方形の一辺とするような正方格子が最も粗い正方格子です。

K

全ての N に対して解が存在します。N の偶奇によって違うので N = 7, 8 の場合を置いておきます。

N = 7
21 この三角形でできます

N = 8
56 個の三角形でできます

このブログについて

これは Competitive Programming Advent Calendar の記事です。プログラミングコンテストに登場したキャラクターの紹介をします。見たいキャラクターの記事をクリックして下さい。

忘れているものがあればコメント欄などで教えてください。

Magical Girl

概要

• 魔法を使う。

主な活動

• 魔女と戦う (SRM 514)

Bolivian man

概要

• TopCoder で writer をしている。

主な活動

• John and Brus にインタビューする (SRM 460 D1 Easy)

あり

概要

• プログラミングコンテストチャレンジブック に登場した。縦に書かれている、大きすぎる、灰色であるなどの理由で判別しにくい。

主な活動

• 竿の上を歩く (POJ 1852)