Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2009-09-24

[]今週のPKU 00:49 はてなブックマーク - 今週のPKU - TopCoderの学習のお時間

連休中にけっこうやったのでメモ。

基本的に正解者数が多い問題からやってるのでそんな難しいのは入ってません。

  • 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
    • segment-tree
    • Javaではやたら遅くてTLEしかしなかった。C++では入力をcinにするとギリギリ、scanfを使うと余裕

2009-05-16

[][]ACM/ICPC2007 Japan(東京大会) 23:09 はてなブックマーク - ACM/ICPC2007 Japan(東京大会) - TopCoderの学習のお時間

最近SRMの結果がへぼすぎて凹ましいので、冷静に現状の実力を測ろうと、一発勝負じゃないもので練習してみました。

http://acm.pku.edu.cn/JudgeOnline/searchproblem?field=source&key=Japan+2007

("Domestic"が付いてない問題群)


結果

表記は「正解時のスタートからの経過時間(分)/間違えた回数」

ABCDEFGHIJ
10/020/043/0--91/00/1235/0--

合計 5問/399min

本番での参加50チーム中13位相当。意外に良かった


問題ごとに

IDタイトル感想
AAnd Then There Was Oneヨセフス数。
効率の良い方法を使わなくても普通にシミュレーションしたら通った
BPrime Gap素数+探索。やるだけ
CMinimal Backgammon典型的DP
DLowest Pyramid幾何。
謎。座標が整数であることを利用してどうにかできるのか?
EGeometric Map実装+グラフ。
グラフができてしまえばダイクストラで終了なんだろうが、その実装がとても厄介。
手を付けたものの完全に方針が見えていない状態で書き始めたため行き詰まり
FSlim Span最小全域木。
使用する枝のコストの最小値を変えながら最小全域木を作ってやるとよい
GThe Morning after Halloween実装がちょっとややこしいビットBFS。
状態数100万くらいだからいけるよね? と思って書いたらMLE(たぶんTLEでもある)
いつもBFS書くのに使ってる方法、効率が悪いのかなぁ
HBug Hunt構文解析。
やるだけなんだけど、コードが汚くなってデバッグに少し時間がかかってしまった
IMost Distant Point from the Sea幾何。
2本の辺に接する円を他の辺に接するまでどれだけ大きくできるかを各辺ペアに対して調べるとO(N^3)でいけそう
このような方針は立ったけど、実装しようとすると固まってしまう。幾何は苦手です
JThe Teacher’s Side of MathMath。
係数の関係が連立一次方程式になるので線形代数的になんかやったら解けるんじゃなかろうか
学生の時にちゃんと勉強してなかった負債が重い