■ [SRM]SRM500 
2011-03-19 25:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14429&rm=307532
500回記念大会
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| 250 | MafiaGame | AC 21min | - | 簡単なはずだけど難しい問題、面白い |
| 500 | FractalPicture | Compiled | 済 | ひどいバグにはまった |
| 1000 | ProductAndSum | UnOpened | - | 簡単めだったらしい |
- Coding
- 250
- 問題文長い…けどそんなに読むのは詰まらなかった
- 投票対象の人数=投票者数なので
- 固定票が2票以上の人がいたら固定票最多タイの人だけが残る
- 逆に2票以上の人がいなかったら全員1票で並ぶ
- と考えると簡単だが
- そのへん気づいていなかったので、
- 1回目で決着がついた場合は～
- とか
- 1回目の投票結果の最大票数が固定票のみの最大数と同じ場合は～
- とかの無駄な場合分けをいっぱい書いていた
- 提出直後に全部気づいたが再提出で点数下がると悲しいのでよーく見直して問題ないことを確認
- 500
- 調べる四角形の座標が整数なのに着目
- 整数座標にある枝とそれ以外の枝の部分を分けて計算するとよさそう
- 枝の長さが1になるまでフラクタルを進めて、
- 残りの非整数な長さの枝は1*1のマスに分けてやるとすべて計算対象に含まれるか含まれないかのどちらか
- そして、長さ1の枝から派生する部分（1*1のマス内に収まる部分）の合計長さは厳密に計算可能
- というわけであとはひたすら実装
- フラクタルを作っていくところで枝の状態がどうにもおかしい
- デバッグしてもなかなか間違いが見つからない
- 終了2分前に、+と=をタイプミスしていて、不意なフィールドへの代入が起きて状態を壊しているのに気づく…
- 間に合わず
- その他小さいミスが2つあったけど十分普通のデバッグで対処できるようなものだった。残念
- 前日にTwitterでこう言っていたらまさにそんな感じのが出てくれた
- こういう問題は結構好きですよ
- 調べる四角形の座標が整数なのに着目
- 250
- Challenge
- 250で投票を1ターンしかさせていない人を発見、撃墜
- 調子にのってもう一人チャレンジしたら今度は自分がルールを勘違いしていた、失敗
- System Test
- 250は通った
結果
- スコア：171.49 + 0.00 + 0.00 + (50*1-25*1) = 196.49
- 順位：59位/867人
- レート：2121 -> 2204
このスコアでこのレート上昇とは…
けどこれまでの自分の結果を思い返すとこういう回（Easy/Mediumともに難しめ）はだいたい上がっている気がする
記念のTシャツやらバッヂ？やらが当たったらしい。わーい。
■ [SRM]SRM499 
2011-03-08 25:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14428&rm=307408
うさぎ回。
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| 250 | ColorfulRabbits | AC 6min | - | 慎重に |
| 550 | WhiteSpaceEditing | TLE 34min | 済 | ああ、またTLEだったよ。あいつは計算量を見積もらないからな |
| 1000 | ImpossibleGame | Opened | - | 途中まで |
- Coding
- 250
- 単純に数えればよさそうだけど
- 最近簡単な問題でもミスしまくりだったので慎重に取り組む
- サンプルを一つずつ丁寧に検証していって、合っている確信が持ててから書き始める
- 提出時の部屋内順位は真ん中くらいでそう早くはないけど十分
- 550
- O(N^5)でやった。大枠はたぶんwrongさんのと同じような感じ
- どんなふうにその考えに至ったかを書いておく
- 手元でルールに従っていろいろ操作してみると、これは範囲DPだなーと思う
- ある列を二つに割ったら、その片方が1列目～10列目をカバー、もう一方が11列目～50列目をカバー、と部分問題に分解できる形になるので
- 計算量的にもなんかそれらしい
- しかしこれだけでは、状態数が「i列目から」「j列目までの範囲を作るのに」「長さkの列から始めたときの必要な操作数」で50*50*100万になって無理
- 行き詰まったので単純なケースを考えてみる。これすごく重要
- 1列しかない場合…はさすがに自明すぎるので
- 2列しかない場合：その2列の目標長さをa,b（a
- x < a の場合：まずxをaまで伸ばして、分裂させて、bまで伸ばすので (a-x) + 1 + (b-a) = b-x+1回
- a <= x <= b の場合：まず分裂させて、片方はaまで縮める、片方はbまで伸ばすので 1 + (x-a) + (b-x) = b-a+1回（定数）
- b < x の場合：x
で、結局これは、線形関数を連結した形（折れ線グラフ）
- 列が2個じゃなくてもっと増えた時も、線形なのは変わらないだろう、きっと。（証明はしてません）
- 折れ線グラフの最小値だから、線が折れ曲がるところだけ、つまりどれかの列の目標長さのところだけ調べれば良い！
- あと開始状態の長さ0も追加で必要だけど
- というわけで状態数が50*50*50に落ちた
- だから計算量O(N^3)だと思ってテキトーにメモ化再帰書いて最大ケースもテストせず提出してしまった
- 各状態での最小値を計算するのにO(N^2)ループしてるので全体ではO(N^5)だ…
- 1000
- 文字の順番は関係ないことはすぐ気づいて、
- 強連結成分分解してどうのこうのかなあ、といったところまで
- 250
- Challenge
- 250のコーナーケース落ちを探すも見つからず
- System Test
結果
- スコア：238.28 + 0.00 + 0.00 + (50*0-25*0) = 238.28
- 順位：329位/755人
- レート：2179 -> 2121
半分より上でもこの落ちっぷり。おそろしい
■ [SRM]SRM497 
2011-02-11 11:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14426&rm=307222
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| 250 | PermutationSignature | AC 52min | - | いつもは解けるタイプなはずのが大混乱 |
| 550 | CssRules | Opened | - | 要実装で残念 |
| 1000 | ModuleSequence | UnOpened | - | 見てない |
- Coding
- 250
- 数列が作れないというパターンはなさそう
- 適当に法則を考えて実装するがことごとく外れる
- サンプル通ったので提出したが全然違っていることに気づいて
- さらにごちゃごちゃ修正してなんとかそれっぽのができたので再提出
- 今回通した人の中では一番ひどいコードなのではないか
- Dの範囲だけ反転させるというシンプルな解法はいつもだったら気づいてそうだけどなぜこの回は…
- 550
- 250で時間使いまくったのでひらめき一発で解けるようなのだったらいいなーと思って開いたら文法規則が書いてあるのが見えて絶望
- XTHMLのパースをやったくらいのところで時間切れ
- 250
- Challenge
- 呆然としていた
- System Test
- 通った
結果
- スコア：79.22 + 0.00 + 0.00 + (50*0-25*0) = 79.22
- 順位：423位/550人
- レート：2348 -> 2179
じわじわ上げてきてたのが一気に持って行かれた。さすがにここまで来るとワンミスが致命傷
