Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

PCK 2013 予選

PCK

7 完だよ～～. 一時期3 位になったし嬉しかったが, vector 使えなくて8 落とすって許されないですね...

解法はおおざっぱに書きます(詳しく書くのはつらぽよ)


1.
59 秒でAC した. $a - b$ を出力すれば良い. (ソースなくしてる...)

2.
kakezan_gezan

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main()
{
	int s = 0;
	int cost[] = {6000, 4000, 3000, 2000};
	for (int i = 0; i < 4; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", y * cost[x - 1]);
	}
	
	return (0);
}

3.
なんか色々試す

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main()
{
	int n;
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int x, y, b, p;
		scanf("%d %d %d %d", &x, &y, &b, &p);
		
		if (b >= 5 && p >= 2) printf("%d\n", (x * b + y * p) * 8 / 10);
		else if (b < 5 && p >= 2){
			int c1 = x * b + y * p;
			int c2 = (x * 5 + y * p) * 8 / 10;
			printf("%d\n", min(c1, c2));
		}
		else if (b >= 5 && p < 2){
			int c1 = x * b + y * p;
			int c2 = (x * b + y * 2) * 8 / 10;
			printf("%d\n", min(c1, c2));
		}
		else {
			int c1 = x * b + y * p;
			int c2 = (x * 5 + y * 2) * 8 / 10;
			printf("%d\n", min(c1, c2));
		}
	}
	return (0);
}

4.
全部1 以下ならつらぽよな人生なのでペアはできない. そうじゃなければ#(1 以上あるもの) + 1.

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main()
{
	int N, K;
	int k[10000];
	
	while (scanf("%d", &N) && N){
		for (int i = 0; i < N; i++)
			scanf("%d", k + i);
		
		sort(k, k + N);
		
		if (k[N - 1] < 2){
			printf("NA\n");
		}
		else {
			int sum = 0;
			for (int i = 0; i < N; i++){
				if (k[i] != 0) sum++;
			}
			printf("%d\n", sum + 1);
		}
	}
	return (0);
}

5.
なんでこれが5 なのだろうか... シミュ.

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main()
{
	int N;
	while (scanf("%d", &N) && N){
		vector<int> player(N, 0);
		int mount = 0;
		char ch[128];
		
		scanf("%s", ch);
		
		for (int i = 0; i < 100; i++){
			if (ch[i] == 'M'){
				player[i % N]++;
			}
			else if (ch[i] == 'S'){
				mount += player[i % N] + 1;
				player[i % N] = 0;
			}
			else {
				player[i % N] += 1 + mount;
				mount = 0;
			}
		}
		
		sort(player.begin(), player.end());
		for (int i = 0; i < N; i++) printf("%d ", player[i]);
		printf("%d\n", mount);
	}
	return (0);
}

6.
2 重for どころか3 重for でも通るらしい(後輩が通っていた.)

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main()
{
	int Q;
	
	scanf("%d", &Q);
	
	for (int T = 0; T < Q; T++){
		int a, b, c;
		
		scanf("%d %d %d", &a, &b, &c);
		
		int ans = 0;
		for (int i = 0; i <= 333; i++){
			for (int j = 0; j < 555; j++){
				int aa = a - 3 * i - 2 * j;
				int bb = b - j;
				
				if (aa < 0 || bb < 0) continue;
				ans = max(ans, i + j + min(aa, min(bb, c)));
			}
		}
		printf("%d\n", ans);
	}
	return (0);
}

7.
せぐぽよ

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


pair<int, int> seg[1 << 18];

void update(int k, int x)
{
	int id = k + 1;
	k += (1 << 17) - 1;
	seg[k].first += x;
	seg[k].second = id;
	while (k){
		k = (k - 1) / 2;
		if (seg[k * 2 + 1].first > seg[k * 2 + 2].first){
			seg[k] = seg[k * 2 + 1];
		}
		else if (seg[k * 2 + 1].first < seg[k * 2 + 2].first){
			seg[k] = seg[k * 2 + 2];
		}
		else {
			seg[k] = seg[k * 2 + 1];
		}
	}
}

int main()
{
	int N, R, L;
	int team[100000] = {0};
	
	scanf("%d %d %d", &N, &R, &L);
	
	for (int i = 0; i < N; i++) update(i, 0);
	
	int prev = 0;
	int top = 0;
	for (int i = 0; i < R; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		team[top] += b - prev;
		update(a - 1, c);
		top = seg[0].second - 1;
		prev = b;
	}
	team[top] += L - prev;
	
	int maxi = 0;
	for (int i = 1; i < N; i++) if (team[maxi] < team[i]) maxi = i;
	
	printf("%d\n", maxi + 1);
	
	return (0);
}

h.
二分探索のバグとれて歓喜していたらREMOVE がバグった. サンプルは通る. $O(N\times leadernum \times \log N)$ っぽい解法.

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

//typedef __int64 lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
//const lint INFLL = (__int64)1001001001001001001;

//#define clear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int rev[1000000];
pair<int, int> st[1000000];
bool leader[1000000];

char q[1000];
int x[1000];

int main()
{
	int N, Q;
	
	scanf("%d %d", &N, &Q);
	
	for (int i = 0; i < N; i++){
		scanf("%d", &st[i].first);
		st[i].second = -1;
		rev[i] = st[i].first;
	}
	
	for (int i = 0; i < Q; i++){
		char qt[1024];
		scanf("%s %d", qt, x + i);
		q[i] = qt[0];
		if (q[i] == 'A'){
			st[x[i] - 1].second = x[i] - 1;
		}
	}
	
	sort(st, st + N);
	vector<int> leads;
	for (int i = 0; i < Q; i++){
		if (q[i] == 'A'){
			int pos = lower_bound(st, st + N, make_pair(rev[x[i] - 1], x[i] - 1)) - st;
			leads.push_back(pos);
		}
		else if (q[i] == 'R'){
			vector<int> tmp;
			tmp = leads;
			leads.clear();
			int pos = lower_bound(st, st + N, make_pair(rev[x[i] - 1], x[i] - 1)) - st;
			for (int j = 0; j < tmp.size(); j++){
				if (tmp[j] != pos) leads.push_back(tmp[j]);
			}
		}
		else {
			int l = 0, r = INF;
			
			while (l != r){
				int mid = (l + r) / 2;
				
				int over = 0;
				int prev = 0;
				for (int j = 0; j < leads.size(); j++){
					int pos = lower_bound(st, st + N, make_pair(st[leads[j]].first - mid, -1)) - st;
					over += max(0, pos - prev);
					prev = leads[j] + 1;
				}
				
				over += max(0, N - 1 - prev + 1);
				
				if (over > x[i]) l = mid + 1;
				else r = mid;
			}
			
			if (r == INF) printf("NA\n");
			else printf("%d\n", r);
		}
		
		sort(leads.begin(), leads.end());
		/*printf("leads.size() == %d\n", leads.size());
		for (int j = 0; j < leads.size(); j++){
			printf("%d%c", leads[j], j == leads.size() - 1 ? '\n' : ' ');
		}*/
	}
	
	return (0);
}

総合unagi

  • id1 の提出でAC できたのはめっちゃよかった. ファーストアクセプタンス～
  • 問題には何もトラブルがなくて, 4 問目や6 問目はいろんな解き方があるし好きだなあと思いました. ただ(想定はわかりませんが) 制限時間からいろんなオーダーを許してしまって6 問目まで早解き, + 7 問目が解けるか？というのが大きいのかなあと思いました.
  • そんなこと言っといて6 問目のfor のループをi = 0; i < 333 にしていて1 WA だしました. 7 問目とくのが全体の3 番目だったので救われましたがこのミスでペナルティは痛い...
  • 7 問目もインデクシングでバグりましたがこれはよくなかった. デバッグに10 分奪われたかなあ.
  • 8 問目はほんとに終わってから10 分以内でバグがとれたという点が悔しくて, ウ～ンという感じ. 方針を思いつくまでが遅かったのは反省で, ADD の動きと対称的にREMOVE をしていれば解けたなあと思うのでちょっと残念. CHECK じゃなくてREMOVE かよ... というのが
  • 目標は"8 完", "灘に3 つ負けない" でしたがどっちもΩ＼ζ°)ﾁｰﾝらしい. 本選は3 位いないに入賞出来ないと単位が貰えないらしいので本当に精進しないといけない...(さすがに本選はいけるつもりです.)