TCO 2017 Round 1A 問題と解説

問題

Easy. PingPongQueue

M人の参加者がいて、それぞれ力skills[i]を持っている。
キューには0さんからM-1さんまで順番に入っている。
以下のルールでゲームをする時、K番目のゲームの勝者と敗者の力の大きさを答えよ。
1. 2人の参加者が揃っていないなら、キューの先頭から取ってくる
2. skillsの大きい方が勝ち
3. 負けた方はキューの最後尾に並ぶ
4. N回連続で勝った場合は、負けた人の後にキューの最後尾に並ぶ。さもなければ、場に残る

Med. CheeseSlicing

(A,B,C)の直方体のチーズがある。
これを上手くスライスして、良いスライスをいくつか作る。
良いスライスとは最も短い辺の長さがS以上のスライスである。
最適にスライスしたとして、できた良いスライスの面積(最も長い辺*中くらいの辺)の総和の最大を求めよ。

Hard. PolygonRotation

(0, ymax)から始まり、(o, ymin)を含む凸包が与えられる。
この凸包をy軸を回転軸として回転させたときの体積は？

以下、解説

Easy. PingPongQueue

愚直にシミュレーションをする。

struct PingPongQueue {
	vector <int> whoPlaysNext(vector <int> skills, int N, int K) {
		int n = skills.size();

		queue<int> que;
		rep(i, 0, n) que.push(i);
		
		int pla = -1, cha = -1, cnt = 0;
		int L = -1, W = -1;
		rep(i, 0, K) {
			if (pla < 0) pla = que.front(), que.pop();
			if (cha < 0) cha = que.front(), que.pop();

			if (skills[pla] > skills[cha]) {
				W = pla;
				L = cha;

				que.push(cha);
				cha = -1;
				cnt++;
			} else {
				W = cha;
				L = pla;

				que.push(pla);
				pla = cha;
				cha = -1;
				cnt = 1;
			}

			if (cnt == N) {
				que.push(pla);
				pla = -1;
				cnt = 0;
			}
		}

		return{ skills[L], skills[W] };
	}
};

Med. CheeseSlicing

メモ化再帰で間に合う。
int dfs(int x, int y, int z) := (x,y,z)をスライスした時の面積の総和
内部ではxで,yで,zでそれぞれ切って最適な答えを選択していく。
しっかり、メモ化しないと恐らく間に合わない。

int minmin(int a, int b, int c) { return min(a, min(b, c)); }
int maxmax(int a, int b, int c) { return max(a, max(b, c)); }
int S;
int memo[101][101][101];
int dfs(int X, int Y, int Z) {
	int mi = minmin(X, Y, Z);
	int ma = maxmax(X, Y, Z);
	int md = X + Y + Z - mi - ma;

	X = ma, Y = md, Z = mi;

	if (0 <= memo[X][Y][Z]) return memo[X][Y][Z];
	if (Z < S) return memo[X][Y][Z] = 0;

	int ret = X * Y;

	rep(x, S, X) {
		if (X - x < S) break;
		ret = max(ret, dfs(x, Y, Z) + dfs(X - x, Y, Z));
	}

	rep(y, S, Y) {
		if (Y - y < S) break;
		ret = max(ret, dfs(X, y, Z) + dfs(X, Y - y, Z));
	}

	rep(z, S, Z) {
		if (Z - z < S) break;
		ret = max(ret, dfs(X, Y, z) + dfs(X, Y, Z - z));
	}

	return memo[X][Y][Z] = ret;
}
struct CheeseSlicing {
	int totalArea(int A, int B, int C, int _S) {
		S = _S;
		rep(i, 0, 101) rep(j, 0, 101) rep(k, 0, 101) memo[i][j][k] = -1;
		return dfs(A, B, C);
	}
};

Hard. PolygonRotation

パップスギュルダン、みんな当たり前のように知ってるのか (自分は完全に忘れていてググッて思い出した)

— tubo28 (@tubo28) 2017年4月1日

知らない単語