2012-12-08

■ [others]第2回WUPC 20:34 はてなブックマーク - 第2回WUPC - TopCoderの学習のお時間

  • F
    • 部分点が設定されていないのでアルゴリズムの問題じゃなくて実装hardなのかなあ→じゃあ自分でもうまくいくとFirstAccept狙えるかも
    • ということでまず開く
    • てきとーに最短路やるだけにしか見えない
    • サクサク書いて出すとWAになった
    • 問題文を読み直すと、連続して同じ方向に進めないという制約を忘れていることに気づく
    • 方向の情報も状態に加えて再提出するとAC
    • たまたま同じ問題を狙ってた人がいなかったみたいでファーストアクセプト取れた
  • G
    • ブロックの数が多いので、特定の高さの所にどのブロックがあるかはSegmentTreeで高さ情報を管理して得ることにする
    • ライブラリ化してなかったので頑張って実装する
    • 出力のせいで一度TLEしただけですんなり通った。バグりやすそうな問題だけどこれはうれしい
  • H
    • ひとまず座標圧縮して駅の個数をMのオーダーにする
    • U・N・C・O区間の左端が小さい順に列車をソートしてDPする
    • dp[i][j][k]: 1〜iの列車を使って、1〜j番の駅には2つ以上の列車が止まって、j+1〜k番の駅には1つの列車が止まるような選び方の数
      • 追記：これだとMLEするのでiのところは2にして偶奇で切り替えるアレをやる
    • ひたすらWAって部分点すら全然通らない
    • ナイーブ解法と比較してみると、列車がないため訪問できないとしないといけない部分の座標が座標圧縮したときに潰れて無視されていることに気づいた
    • 列車の始点・終点の前後の座標も考慮対象に加えるとTLE→ちょっと定数倍高速化してAC
  • A
    • やる
  • B
    • 一瞬DPしそうになったけど、 Xが連続する個数/3 を加えていけばOK
  • C
    • やる
    • 全体を回転させたらすっきりできそうだけど長方形だと面倒かなーと思って、とてもださいコードを書いてしまった
  • D
    • 大きい順に詰める
      • 5、4+1、3+2+1、2+1、1
    • 頑張って漏れないよう数える
  • E
    • ループがない森の場合は、枝を1つ消すとかならず独立なグループが1つ増えるので、コストが小さいものから貪欲に消せば良い
    • ループがある場合、ループ内の枝を消す場合と消さない場合とで場合分けした
      • ループ内の枝を消す場合、ループ内の枝で一番コストが小さいものを消して、あとは森として扱う
      • ループ内の枝を消さない場合は、ループ以外の枝だけからコスト少ない順に消す
    • バグバグだったがなんとか終了間際に直せた
  • I
    • 読んだだけ
    • パッと見ではいもす法に見えるが…