■ [SRM][本番]SRM449 
2009-09-24 00:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=13903&rm=302281
このmedium難傾向はいつまで続くのか
| Level | タイトル | 試合中 | あとで | 感想 |
|---|---|---|---|---|
| DIV1 250 | MaxTriangle | AC 35min | - | 整数+平面幾何。 全部調べればよくて計算量もまず大丈夫なんだけど、どのくらいのオーダーで抑えられるか証明できないので 意地になって華麗な解法を探しに行ってしまった。しかしそんなものありません 問題読んだ瞬間単純なコードを書き始めたら200点は超えると思うけどそれだと面白くないからなぁ…うぅむ |
| DIV1 550 | HexagonalBattlefield | Opened | - | DP？ マスの数は最大でも200くらいだから適当に枝刈りしつつ探索すればいける… わけないよね550だもんねmod付きだもんねなどと思って問題文読んだだけで放置 |
| DIV1 950 | StairsColoring | Opened | - | 面白そうだったのでずっとこれを考えてた。 i+1段の数をi段の場合から求める漸化式は立ったがそれでまともに計算するとO(10億)で無理。 logに落とさないと…と思ってi段をi/2段から作れないか考えてたができるわけないですね |
- Challenge
- スコア：129.82 + 0 + 0 + (50*0-25*0) = 129.82
- 順位：412位/792人
- レート：1630→1625
足踏み中。
■ [PKU]今週のPKU 
連休中にけっこうやったのでメモ。
基本的に正解者数が多い問題からやってるのでそんな難しいのは入ってません。
- 1035
- やるだけ
- 1042
- 経路を覚えつつDP
- 1094
- サイズが小さいので、全部の文字対について順序関係を持っておけばよい
- 1118
- O(N^2)で全部調べるだけ。同じ位置に複数の点がある場合に注意
- 1151
- 座標圧縮の練習問題
- 1152
- やるだけ。なんでこんなに正答率低いの…？
- 1159
- DP。2つ以上前の状態は不要なので捨てることによって空間計算量を抑える
- 1166
- 4^9の全通り調べる
- 1200
- BitSet.cardinality()
- 1222
- 一番上の行を2^6通り全部試す
- 1226
- やるだけ。入力サイズ1の場合に引っかけられた
- 1230
- greedy。入力形式にはめられてひたすらWAってた
- 1251
- もろに最小全域木
- 1273
- もろにMaxFlow
- 1274
- もろに2部グラフの最大マッチング
- 1316
- まさにやるだけ
- 1458
- DP
- 1459
- multi-source、multi-sinkなMaxFlowの練習問題
- 3368
