■ [SRM]Member SRM 485 
2010-10-21 20:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14238&rm=306103
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| 250 | AfraidOfEven | AC 7min | - | 250は全探索安定 |
| 500 | RectangleAvoidingColoring | AC 49min | - | DPは久々に通せた |
| 1000 | Deposit | UnOpened | - | - |
- Coding
- 250
- 等差数列は先頭2個を決めたら残りは全部決まる
- 先頭2個を32*32通り全探索すればよい。辞書順最小もそれで自然に得られる
- 入力の全ての数が奇数であることを忘れてしまっていたけど無問題
- 500
- いかにもDPぽいけどこのままではサイズが無理
- 具体的な例で考えてみる
- とりあえず1行目が全部白だったとすると
- 2行目には白は最高1つしか入れない、残りは全部黒
- 列がたくさんあったとすると、3行目には白も黒も最高1つしか入れないからこのケースはあり得ない
- など考えていると5*5以上のサイズのときは解が0になることがわかった
- 最大サイズ4*50になった。これはDPできそう
- 高さのほうが4以下とすると、
- 状態は、それぞれの行ペアに対して、（白、白）と（黒、黒）の組み合わせをもう使ったかどうかの2bitがある（全部が互いに独立というわけではないけど）
- そして一列の状態は最大で全部?の場合の 2^(行数)
- というわけで計算量は 2^(2*4*(4-1)/2) * 2^4 * 50 = 300万くらい よし大丈夫！
- がんばってbitbitしたDPを書く
- いくつかミスを直すとサンプル合ったので提出。最大ケースも一瞬で終わる。
- あと、高さ1の場合は別扱いしないといけないのも忘れずに
- 250
- Challenge
- まず500で幅1の場合が抜けている人がいないか見たがすぐには見つけられず
- 250に移る
- 2の累乗倍ではなくて2倍4倍6倍…と調べている人を発見した、が、テストケースを考えているうちに他の人に撃墜される
- 何もできず
- System Test
- 250も500も通った
結果
- スコア：232.17 + 215.50 + 0.00 + (50*0-25*0) = 447.67
- 順位：23位/613人
- レート：2204 -> 2288
自己最高順位タイ。
■ [Codeforces]Codeforces Beta Round #36 
2010-10-19 19:00-
http://codeforces.com/contest/36
| ID | タイトル | 結果 | ひとこと |
|---|---|---|---|
| A | Extra-terrestrial Intelligence | PE*4->AC 00:21 | Aにしては面倒 |
| B | Fractal | AC 00:31 | 再帰 |
| C | Bowls | WA | 実装 |
| D | New Game with a Chess Piece | WA*2->WA | 早とちりでミス |
| E | Two Paths | Opened | 読んだだけ |
Coding
- A
- B
- C
- 1つずつ置くときに、それまで置いた皿それぞれに対して重ねるとした場合の高さを出してみて一番高かったものを採用すればよい
- 最大3000枚なのでO(N^2)で大丈夫
- 重なり方のパターンがいっぱいあるのでがんばって場合分け
- すごくしょうもない括弧の位置ミスで数十分を浪費
- 結局WA、まあどこか間違えてたのだろう
- D
- ルールが今ひとつつかめなかったのでノートに書き出してみると法則性が見えた
- WA
- N=1の場合が特別なのを直したのと、先手必勝の列が一ブロックおきに後手必勝と入れ替わると勘違いしていたのを直して再提出
- 結局WA、N=1の場合の規則がミスっていた
- E
- とりあえず読んだだけ
- よくわからない
- hack
- 何もできず
結果
- スコア：1134
- 順位：171位/394人
- レート：1851 -> 1752
AでのPE*4が痛すぎる
