hotpepsiの練習帳

Codeforces 102 Div2

23:11

不参加。

A. Help Vasilisa the Wise 2

問題

• 数独の簡単なやつ

方針

• 全探索
• なんかポインタ使って計算したら複雑に...

B. Help Kingdom of Far Far Away 2

問題

• お金を謎の国の通貨表示にする

方針

• 整数型には収まらない範囲
• よくある文字列処理

C. Help Farmer

問題

• 盗まれた結果の残数から、元の数量の最小値と最大値を求める
• 分散が小さくなるように並べるんだろうか...
• 小さい範囲のgreedyだけ書いた

感想

Aはポインタを使ってループの形に書いてみたが、int *(*pp[6])[3]とかいう謎の宣言になってしまった。6変数くらいならそのまま書いたほうがシンプルだった。

Bは特に悩むところはない。

Cはまだできてない。

SRM 529 Div2

00:07

Easy (250) PairingPawns

問題

• N個のセルにポーンを何個か配置する。
• セルXに2個あるポーンを消して、セルX-1にポーンを1個増やす操作ができる。
• セル0の最大のポーンの数を求める。

方針

• 難読化のため「同じ場所を占有する」みたいな書き方になっている
• 一番うしろの要素から半分にするだけ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_529/PairingPawns.cpp

Medium (500) KingSort

問題

• 王様の名前を辞書順に並べたい。
• 名＋代(ローマ数字) の配列が与えられる。
• 名でソートした上で、代については数値順に並べよ。

方針

• よく読んだら、代は1～50で、特定の文字列
• 代を01～50に変換してソートしてから元に戻す(やっつけ)
• std::set<std::pair<string, int> >に突っ込んだほうがスマート
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_529/KingSort.cpp

Hard (1000) MinskyMysteryDiv2

問題

• あるルールに基づいて、5つの袋からビー玉を足したり引いたりする
• 0から10^12まで処理できるようにせよ

方針

• わからん
• 実験したところ、偶数は半分になり、素数はほぼそのまま、その他の合成数は謎ルール
• つまり最初に割ることのできる数を求めているっぽい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_529/MinskyMysteryDiv2.cpp

結果

oo- 234.12+330.86=564.98pt 163rd 1093 -> 1133

いまいち。

mediumは、小さい数が前置されているのをパースするのは面倒だなあ(たとえばIILとか)と思ったら固定でよかった。ゆっくりしすぎた。

hardは面白い問題。機械式計算機っぽい。

Codeforces 101 Div2

00:45

A. Amusing Joke

問題

• 三つの文字列が与えられる。
• 最初の二つは二人の名前である。
• 三つ目の文字列から、足し引きなしで最初の二つの文字列が作れるかどうかを答える。

方針

• std::map<int, int>に1文字ずつ突っ込んでカウント・照合。
• ソートして比較すれば一発だった...

B. Hopscotch

問題

• Y軸方向に1辺がaの正方形が並んでいる。
• X軸方向には1つまたは2つ並ぶ。
• 並び方は1-1-2-1-2-1-2-(1-2)...である。
• 座標(x,y)に小石を投げて、マスの中に入っているかどうかを答える。

方針

• 最初の1マス目だけ規則性がないので場合わけ
• あとはY座標を2a単位で見る
• Y座標の余りが0からaなら2マス、aから2aなら1マスの部分に入っている

C. Queue

問題

• n人が一列に並んでいて、いったん解散した
• それぞれは、自分より背が高い人の数だけ覚えている
• 背丈は同じでもよい (同じ場合は高いと見なさない)
• 背が高い人の数の配列が与えられるので、可能なら並び方の例をひとつ答える

方針

• 撃沈...

結果

oo--- 1274 392nd rating 1526 -> 1523

簡単なのしか解けないのは問題。

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つしかないので厄介である。たとえばあるターンには複数の種類のカードが送れるとか。というか解いたらルールがわかる感じ。

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

SRM 526.5 Div2

03:06

不参加のため練習

Easy (250) MagicStonesStore

問題

• 2n個の石がある。
• 2つの素数の和で表せるかどうかを求める。

方針

• 素数表を作っておく
• 2nから素数を引いて、残りが表にあるか調べる
• https://github.com/firewood/topcoder/blob/master/srm_526/MagicStonesStore.cpp

Medium (500) MagicCandy

問題

• 1-nまでの番号がついたn個のキャンディーがある。
• x^2番目のキャンディーを取り除き、残ったy個に1-yの番号を割り当てなおす。
• 残りの1個になったとき、最初のどの位置だったのかを求める。

方針

• 想定位置がnであると仮定する
• k個あって、k番目を取り除くときだけ、想定位置を-1する
• nが2まで実行する
• https://github.com/firewood/topcoder/blob/master/srm_526/MagicCandy.cpp

Hard (1000) MagicNaming

問題

• 住人が発明した呪文がある。
• 呪文は住人の名前を結合したもののうち、辞書順で最小のものである。
• 最大で何人の住人が含まれるか求める。

方針

• あとで解いた
• 末尾からDP
• ある範囲に名前がa+bという形で含まれていると仮定して、辞書順でb+aより小さければOK
• https://github.com/firewood/topcoder/blob/master/srm_526/MagicNaming.cpp

感想

easyについては、表作らなくてもその場で判定すればよかった。

が、素数生成はコードをコピペしてくればよいので、表あってもよいかなと思う。

nがいくつまでならその場で計算してよいかすぐわからないし。

mediumは本番で出たら解けたかどうかあやしい。図を書いて納得した。

今年の目標

年末にdiv2に落ちてしまったが、今年は一瞬でも黄色になるのを目指す。

div2 mediumまたはdiv1 easyは毎回解くことにする。