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

Lilliput Steps

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

PCK2013 本選 (問題の部)

時系列順に行きます/\_/\


-00:10:00 競技説明
「友達がいない人は手を挙げて下さい」 でめっちゃ草生えた. (パートナーがいない人は知らせて下さいの意)

00:00:00 競 技 開 始
めっちゃ緊張しつつ問1 を開く. やばそうな図が書かれていて冷えるが, ゲームの遷移を全て載せればいいらしい... 書く.

00:15:26 問1 AC
問1 から再帰とか, 今年のPCK やばい...
後輩とハイタッチを行ってから問2 の概要を教えてもらう. Sparse な$M \times N (M,\ N \leqq 10^4)$ の行列に適当なベクトルをかけた時の結果を出力すれば良いらしい. グラフをリストで管理する要領で解いてみる.

00:26:54 問2 AC
やったぜハイタッチ. うまくいく.
問3 を聞くとただの多倍長らしい. 配列に分けて書くのはJOI のBeads とか言う問題でやって知っていたのでパパっとかく.
書いている途中にスマイリー風船が僕らのところに来る. めっちゃ焦ってMP さがる.


00:36:53 問3 WA
めっちゃMP さがる. こんなところでWAだすと順位下がると思って物凄く動揺する.
よく見ると"Fks" という単位を入れ忘れている...! 悔しいが直して提出する.

00:39:10 問3 AC
辛くなりますよ~ほんと...
後輩に焦らないように言われて, 口では気をつけると言っていたが行動は壊滅的な感じでよろしくなかった.
問4 を見る. 少し考えると簡単なDP であることが分かる. なんとなくメモ化再帰で書いてサンプルが通ったので提出.

00:49:53 問4 WA
MP さがる. 後輩に説明しつつ一緒にコーナーケースなどを考えた結果, 経験値が全く貰えない場合とかを考慮していない事がわかった. (おんなじ遷移繰り返しまくる). 適当に直す.

00:53:28 問4 WA
再びMP さがる. 漸化式の境界の考慮不足らしい. ふむむ...

01:08:54 問4 AC
このWA 数は許されないですね...と思う(しかし悲劇は始まったばかりだった.) ハイタッチはしていたがWA 数で生きた心地はしていなかった. この時点で2 位くらい.
問5 を読むが解ける気がしなかったので問6 から取り組む.

簡単なbitDP だと思ったがバグったらしく辛くなる. MP さがる. 状態空間が$2^n$ だと思っていたDP が実は$4^n$ で明らかに間に合わなくて辛くなる. MP さがる. その後に$n2^n$ のものを思いついて実装する.

01:48:01 問6 WA
またDP の遷移を間違えていた... 冷静に考えれば分かるんですよね... MP さがる.

01:50:01 問6 AC
やったぜハイタッチ(MP さがる). すこし休憩して問5 に戻る.
後輩の解法の指針通りに実装してみることにする. もうWA 数が悲惨で入出力レベルのミスをして5 WA を頂く. (MP さがる).

02:35:56 問5 AC (+5 WA)
泣きそうになりながらハイタッチしていた. この時点で3 位くらい. ココロを落ち着けて7 と8 を見る.

8 が解かれていたので8 を読んでみたが, 座標圧縮した後のクエリに対する処理がパッと思いつかず諦めていた... (クエリの点も一緒に座標圧縮すればdijkstra or 0-1 BFS に落ちたが考えが及ばなかった.)

7 は置換+構文解析の問題で, 僕が出したこの問題 の性質を使えば解けそうだった. がんばって残り時間で実装する.

03:50:08 問7 WA
3 位から落ちそうで怖くてめっちゃ焦る. もう全然バグの原因の見通しが立たなくてあまり意味の無さそうな変更を行う. (MP さがる).

03:51:29 問7 WA
どこを読んでも原因がわからなくて時間だけが過ぎていく. ものすごく悔しい. (MP さがる).
ちなみにこのコードは1 行直すとAC しました. 構文解析がミスっていた.


04:00:00 糸 冬 了
つらくなりますよー... (MP さがる).

まとめ
MP がものすごくさがった. Ω\ζ°)チーン
メンタル的な反省点が多すぎるのと, 後輩と後半にコミュニケーションがあまり取れなかったのが課題. もっと相談して, 一緒にデバッグしていけるようにしよう.
後輩君に未来を託します.

~~ここから現代的なコード~~

飛行機に乗る前なので解法は後ほど.

問1

#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int A, B;

void recur(int nA, int nB, string s)
{
	if (nA == A && nB == B){
		printf("%s\n", s.c_str());
		return;
	}
	else if (max(nA, nB) >= 5 && min(nA, nB) <= 3) return;
	
	if (nA < A && (nA <= nB || nA - nB <= 3)){
		recur(nA + 1, nB, s + "A");
	}
	
	if (nB < B && (nB <= nA || nB - nA <= 3)){
		recur(nA, nB + 1, s + "B");
	}
}

int main()
{
	scanf("%d %d", &A, &B);
	
	recur(0, 0, "");
	
	return (0);
}

問2

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int> > G[10001];

int main()
{
	int N, M;
	
	scanf("%d %d", &N, &M);
	
	int x, y, z;
	while (scanf("%d %d %d", &x, &y, &z) && z){
		G[--x].push_back(make_pair(--y, z));
	}
	
	int L;
	scanf("%d", &L);
	for (int i = 0; i < L; i++){
		int coef[10001], sum[10001] = {0};
		for (int j = 0; j < M; j++){
			scanf("%d", coef + j);
		}
		
		for (int j = 0; j < N; j++){
			for (int k = 0; k < G[j].size(); k++){
				sum[j] += coef[G[j][k].first] * G[j][k].second;
			}
		}
		
		for (int j = 0; j < N; j++){
			printf("%d%c", sum[j], j == N - 1 ? '\n' : ' ');
		}
	}
	
	return (0);
}

問3

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int> > G[10001];

int main()
{
	char unit[100][128] = {"", "Man", "Oku", "Cho", "Kei", "Gai", "Jo", "Jou", "Ko", "Kan", "Sei", "Sai", "Gok", "Ggs", "Asg", "Nyt", "Fks", "Mts"};
	
	int m, n;
	
	while (scanf("%d %d", &m, &n) && m){
		int poly[100] = {0};
		poly[0] = 1;
		
		for (int i = 0; i < n; i++){
			for (int j = 98; j >= 0; j--){
				poly[j] *= m;
				poly[j + 1] += poly[j] / (10000);
				poly[j] %= 10000;
			}
		}
		
		for (int i = 98; i >= 0; i--){
			if (poly[i]) printf("%d%s",poly[i], unit[i]);
		}
		printf("\n");
	}
	
}

問4

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int a[128], e[128], r[128];
int memo[128][128];
int D, N;

int getMin(int left, int exp)
{
	if (left <= 0) return (0);
	if (memo[left][exp] >= 0) return (memo[left][exp]);
	
	int ans = 99999;
	
	for (int i = 0; i < N; i++){
		if (exp == 100 && a[i] == 0) continue;
		if (r[i] <= exp && !(a[i] == 0 && e[i] == 0))
			ans = min(ans, getMin(left - a[i], min(100, exp + e[i])) + 1);
	}
	
	return (memo[left][exp] = ans);
}

int main()
{
	
	while (scanf("%d %d", &D, &N) && N){
		bool e0 = false;
		for (int i = 0; i < N; i++){
			scanf("%d %d %d", a + i, e + i, r + i);
			if (r[i] == 0) e0 = true;
		}
		
		memset(memo, -1, sizeof(memo));
		int ans = getMin(D, 0);
		
		if (ans >= 99999) printf("NA\n");
		else printf("%d\n", ans);
	}
	
	return (0);
}

問5

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int main()
{
	int N;
	while (scanf("%d", &N) && N){
		for (int x = 0; x < N; x++){
			int s, t;
			scanf("%d %d", &s, &t);
			if (s <= 0 && t >= 0){
				if (s < 0) s = -s;
				if (t < 0) t = -t;
				printf("%d\n", __builtin_popcount(s) + __builtin_popcount(t));
			}
			else if (s > 0 && t > 0){
				int ct = 0;
				while (s != t){
					for (int i = 30; i >= 0; i--){
						if (s % (1 << i) == 0 && s + (1 << i) <= t){
							ct++;
							s += (1 << i);
							break;
						}
					}
				}
				printf("%d\n", ct);
			}
			else {
				s = -s; t = -t;
				int ct = 0;
				while (s != t){
					for (int i = 30; i >= 0; i--){
						if (s % (1 << i) == 0 && s - (1 << i) >= t){
							ct++;
							s -= (1 << i);
							break;
						}
					}
				}
				printf("%d\n", ct);
			}
		}
		break;
	}
	
	return (0);
}

問6

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

using namespace std;

typedef long long lint;

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

#define zclear(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 n, m;
int a[16], b[16];
int memo[1 << 12][12];

int getMax(int state, int u)
{
	if (u == m || __builtin_popcount(state) == n) return (0);
	if (memo[state][u] >= 0) return (memo[state][u]);
	
	int ans = getMax(state, u + 1);
	for (int i = 0; i < n; i++){
		if (state >> i & 1) continue;
		int p = abs(a[i] - b[u]);
		ans = max(ans, getMax(state | (1 << i), u + 1) + p * (p - 30) * (p - 30));
	}
	return (memo[state][u] = ans);
}

int main()
{
	while (scanf("%d %d", &n, &m) && n){
		for (int i = 0; i < n; i++) scanf("%d", a + i);
		for (int i = 0; i < m; i++) scanf("%d", b + i);
		
		memset(memo, -1, sizeof(memo));
		printf("%d\n", getMax(0, 0));
	}
	return (0);
}

問7 (これはAC するコードです. factor 関数内のx を求める部分で条件分岐してなくてWA してたらしい...)

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

using namespace std;

typedef long long lint;

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

#define zclear(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;

struct VLA {
	public:
	char c;
	vector<int> perm;
};

map<char, VLA> conv;

int pos;
char s[1024];
vector<int> factor();

vector<int> doIt(vector<int> x, vector<int> y)
{
	vector<int> ret(x.size());
	
	for (int i = 0; i < ret.size(); i++){
		ret[i] = x[y[i]];
	}
	
	return (ret);
}

vector<int> doIt2(vector<int> v, int rep)
{
	vector<int> ret(v.size()), next(v.size());
	
	for (int i = 0; i < ret.size(); i++){
		ret[i] = i;
	}
	for (int i = 0; i < rep; i++){
		for (int j = 0; j < ret.size(); j++){
			next[j] = ret[v[j]];
		}
		ret = next;
	}
	return (ret);
}

int lcm(int a, int b)
{
	return (a / __gcd(a, b) * b);
}

int getSize(vector<int> v)
{
	int ret = 1;
	bool vis[128] = {0};
	
	for (int i = 0; i < v.size(); i++){
		int ct = 0;
		int p = v[i];
		while (vis[p] == false){
			vis[p] = true;
			ct++;
			p = v[p];
		}
		if (ct) ret = lcm(ret, ct);
	}
	return (ret);
}

vector<int> equation()
{
	vector<int> res = factor();
	while (s[pos] == '+'){
		pos++;
		vector<int> next = factor();
		res = doIt(res, next);
	}
	return (res);
}

vector<int> factor()
{
	if (isalpha(s[pos])){
		char c = s[pos];
		pos++;
		return (conv[c].perm);
	}
	else {
		int rep = 0;
		while (isdigit(s[pos])) rep = rep * 10 + s[pos++] - '0';
		
		int dx = (s[pos] == '(');
		pos += dx;
		vector<int> x = (dx ? equation() : factor());
		pos += dx;
		rep %= getSize(x);
		x = doIt2(x, rep);
		return (x);
	}
}

int main()
{
	int N, K;
	
	scanf("%d %d", &N, &K);
	
	for (int i = 0; i < K; i++){
		VLA x;
		char buf[128];
		int a;
		vector<int> perm(N);
		
		scanf("%s %d", buf, &a);
		x.c = buf[0];
		
		for (int j = 0; j < N; j++){
			perm[j] = j;
		}
		for (int j = 0; j < a - 1; j++){
			for (int k = 0; k < N - 1; k++){
				int sw;
				scanf("%d", &sw);
				if (sw == 1) swap(perm[k], perm[k + 1]);
			}
		}
		
		x.perm = perm;
		conv[x.c] = x;
	}
	int E;
	scanf("%d", &E);
	for (int i = 0; i < E; i++){
		scanf("%s", s);
		
		pos = 0;
		vector<int> ret = equation();
		
		for (int j = 0; j < N; j++){
			printf("%d%c", ret[j] + 1, j == N - 1 ? '\n' : ' ');
		}
	}
	
	return (0);
}