hotpepsiの練習帳

Codeforces 100 Div2

02:44

記念の回らしいので参加。div1とdiv2の区別なし。

A. New Year Table

問題

• 半径Rの円卓に、半径rの皿をN枚並べたい
• 皿は円卓に外接すること
• 並べられるかどうかを答える

方針

• 図を描いたら正多角形が出てきた
• R >= (1+1/cosθ)rという怪しげな式が完成

bool Test(int n, int R, int r) {
	if (r > R) return false;
	if (n <= 1) return true;
	if (n <= 2) {
		return (R/2) >= r;
	}

	double S = M_PI * (n - 2);
	S /= (2 * n);
	double x = 1/cos(S)+1.0;
	x *= r;
	return R >= (x - 1.0e-9);
}

B. New Year Cards

問題

• AlexanderはN人の友達からNew Year Card(e-mailみたいなの)をもらう
• 友達の番号=カードが届く順番としてカードにも同じ番号を振る
• すなわち友達1からカード1が最初に届き、友達2からカード2が次に届く
• もらったカードを再利用して全員に送る
• あるカードは何人に送ってもよい
• 友達と自分の全員はそれぞれ、好きなカードに序列がある
• 自分は手持ちのカードの中で好きな順番に送るが、もらったのと同じカードは送らない
• 1枚もらうごとに、自分の送信ルールを守る中で最良のカードが送れるタイミングで送る
• それぞれの友達に対して、何枚もらった時点で送るかを答える

方針

• 1枚からN枚まで1ターン毎にシミュレーション
• ターンごとに手札を自分の好きな順でソート
• 各友達について、送っていないか、または、より良いカードで送れるのなら送信履歴を上書き
• 最後に送信履歴を出力

for (i = 0; i < n; ++i) {
	vector<pair<int, int> > _pref;
	for (j = 0; j < n; ++j) {
		if (pref[j] <= i) {
			_pref.push_back(pair<int, int>(j, pref[j]));
		}
	}
	sort(_pref.begin(), _pref.end());
	for (j = 0; j < n; ++j) {
		for (k = 0; k <= i; ++k) {
			int card = _pref[k].second;
			if (card == j) continue;
		}
			int pos = (int)(find(c[j].begin(), c[j].end(), card) - c[j].begin());
			if (pos < sat[j]) {
				sat[j] = pos;
				ans[j] = i;
			}
			break;
		}
	}
}

結果

o---- 368pt 967th rating 1493 -> 1526 (+33)

Aを解くのに40分、Bに1時間以上悩んだ。

Aはepsの符号を書き間違えて1回WAを出した。WAが出たということは誤差をついてくるpretestがあったようである。

Bは長文かつサンプルが1つしかないので厄介である。たとえばあるターンには複数の種類のカードが送れるとか。というか解いたらルールがわかる感じ。

一応青に戻ったが戦える気がしない。