2008-11-23

■ [練習][Tournament]2008 China Round1A 22:20

2008-11-23 15:30-（JST）

中国の人たちだけのコンテスト。難しさはSRMのDIV2くらい？

Level	タイトル	試合中	あとで	感想
1000	MislabeledWeights	-	一度×→○ 25min	シンプルなDP。コピペ箇所を修正忘れのまま提出して一度システムテスト落ち…
500	OrderParser	-	一度×→○ 19min	面倒なだけの文字列操作問題。特殊ケースの考慮（文中に数値0がある）が一つ抜けててシステムテスト落ち
250	CampLunches	-	○ 2min	最大サイズ50なのでO(n^2)のbrute-force全探索

■ [練習][SRM]SRM426 00:28

2008-11-23 26:00-（JST）

参加できなかった回。

Level	タイトル	試合中	あとで	感想
DIV1 1000	LongStraightRoad	-	読んだ	-
DIV1 500	CatchTheMice	-	2度×→○	凸関数の最小値を探索する手法である、三分探索を覚えた。 システムテストで誤差落ちの恐怖を味わう
DIV1 250	ShufflingMachine	-	○ 32min	問題文が難解。 ゴールから逆向きに考えて、カードごとに各位置での期待値が出せる
DIV2 1000	DistinctDigits	-	読んだ	難しそう。DIV2とはいえ正解者ゼロだし
DIV2 500	ShufflingMachine	-	-	DIV1 250と同じ
DIV2 250	KnockoutTourney	-	○ 5min	2進数で考えてビット処理

凸関数の三分探索は、「黄金分割法」という名前が一般的のよう。