■ [SRM][本番] SRM472 
2010-06-05 27:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14154&rm=304807
珍しい時間
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| DIV1 250 | PotatoGame | AC 29min+1回再提出 | - | 実験して推測 |
| DIV1 600 | TwoSidedCards | Compiled | - | 嘘DPを書いて撃沈 |
| DIV1 900 | ColorfulTiles | Opened | - | 正しく900とは珍しい |
- Coding
- 250
- Nimかー。サイズが大きいのでO(N)でも無理。単純なシミュレーションではない
- 4進数だと思えば、1ターンごとにどれかの桁が1ずつ減っていくから、4進数にしたときの各桁の和が系の性質を定める値だ！
- さくっと書いて提出、部屋内最速！
- って、これ本当か？ 怪しい気がしてならないので反例を探してみよう
- うーむ、n=8のとき、先手が4を取ると後手の勝ちだが、1を取ると先手の勝ちになるぞ。繰り下がりが起きるから、各桁の和は使えないのか
- ではなんだろう、わからない
- わからない
- サンプルがとても不親切なのは、いろんな例を載せてしまうとバレてしまうような単純な規則があるからではないか？
- DPでn=1000まで計算させてみた
- 明らかにパターンが見える…
- どうしてそうなるかは置いておいてとりあえずサブミット
- 600
- 何も手がかりがつかめない
- 600>900のこともあるから900を開いてみよう
- 900
- さっぱりわからない
- これは正しく900点だろう
- 600に戻ろう
- 600
- 250
- Challenge
- 250は間違いなく自分と同じミスしている人がいるのでスピード勝負
- 4で割った余りを足していっているようなコードを3つ落とせた
- System Test
- 自分の250は通った
- 部屋内で撃墜残しはゼロ
- スコア：119.70 + 0.00 + 0.00 + (50*3-25*0) = 269.70
- 順位：65位/686人
- レート：1697→1829
長らくレーティングの範囲が変わっていない
250の規則は、4 ≡ -1 mod 5 が関係してるのか
■ [GCJ] Google Code Jam 2010 Round2 
2010-06-05 23:00-
http://code.google.com/codejam/contest/dashboard?c=635102#
鬼門のRound2
| ID | タイトル | small | large | ひとこと |
|---|---|---|---|---|
| A | Elegant Diamond | WA*5->AC | AC | 全然合わずに辛かった… |
| B | World Cup 2010 | AC | Compiled | 最初からlarge用を書いた方がお得だった |
| C | Bacteria | WA*2->AC | Opened | 部分点拾い |
| D | Grazing Google Goats | UnOpened | UnOpened | 読んですらいない |
- A
- けっこう面倒そうだが点数低いだけあって書くだけ
- 各点が広いダイアモンドの中心になり得るか調べて、中心になり得る点の中でサイズが一番小さいものが求める新しいダイアモンド。O(N^4)
- データの持ち方は、変に変形させるとわけが分からなくなりそうなので入力のまんまで
- サンプル合った、提出
- Incorrect
- あ、新しいダイアモンドのサイズ計算が間違ってるぽい、再提出
- Incorrect
- あ、新しいダイアモンドのサイズ計算が間違ってるぽい、再提出
- Incorrect
- あ、4回対称じゃなくて点対称でやってた、再提出
- Incorrect
- あ、新しいダイアモンドのサイズ計算が間違ってるぽい、再提出
- Incorrect
- …次へ行こうか（80分）
- B
- 条件をかみ砕くのがちょいとややこい
- とはいえ、全部同じ値段ならば決勝に近い方から押さえていく方が有利なので貪欲に行けばいい
- サンプル合った、提出
- Correct、ようやくポイント獲得（90分）
- C
- とりあえずsmallはシミュレーションするだけだ、さっさと書いて部分点もらおう
- Incorrectだと…
- およよ、XとYがごっちゃになってる
- Incorrect
- ああ、普通に終了判定をミスっている、修正
- Correct（110分）
- さてもうあまり時間がないわけですが
- Dは解いてる人がかなり少ないので捨てよう
- Aのsmall/large解いても点数が500位に届かないが
- しかしB-large解いても時間的に無理そう、結局通過のためには両方が必要
- ならば意地でAを通そう
- Aに戻る
- 自分でサンプル足したりしつつ、もう一度よーく考える
- おいおいこれ新しいダイヤのサイズ計算全然違うぞ
- 修正して提出
- Correct！ やったついに…
- largeも提出（135分）
- B-large
結果
- A-large通った
- 845位/2500人くらい
今年もここで敗退…
まあ最終的に時間内にAを通せたのでそんなに気分は悪くない
来年こそは
■ [Codeforces] Codeforces Beta Round #16 (Div. 2 Only) 
2010-06-03 22:00-
http://codeforces.com/contest/16
初参加。
| ID | タイトル | 結果 | ひとこと |
|---|---|---|---|
| A | Flag | AC 00:08 | 痛恨のコピペミス |
| B | Burglar and Matches | AC 00:19 | 急いでて問題読み違え |
| C | Monitor | AC 00:28 | 算数 |
| D | Logging | WA*4->AC 00:48 | Wikipediaゲー |
| E | Fish | AC 01:22 | 最後の問題も結局やるだけか |
- A
- B
- 2^m通り全部調べればいいんじゃないの？
- サンプルの答えが合わない
- あ…問題の解釈間違ってた…。マッチは部分的に取ってもいいんですね
- 貪欲に多いやつから取ればいいのか
- AC。だいぶ時間食ってしまった
- C
- 縦か横のどちらかが最大になる取り方だけ調べればよい
- xとyを最大公約数で割って通分しておくのを忘れないよう
- AC
- D
- E
- さすがに最後はちょっとややこしそう
- 上手い方法は浮かばないがとりあえずビットDPぽくシミュレーションしてみようか
- 通っちゃった…
結果
- 順位：10位/252人
- レート：? -> 1661
