問題
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日
知らない単語