Hatena::Grouptopcoder

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

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

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。
係数の関係が連立一次方程式になるので線形代数的になんかやったら解けるんじゃなかろうか
学生の時にちゃんと勉強してなかった負債が重い

2009-02-23

[][]TCO08 Qual1 00:18 はてなブックマーク - TCO08 Qual1 - TopCoderの学習のお時間

去年の問題はどんな感じだったか見とこうと練習…してみたらかなり難しくてへこむ。

Levelタイトル試合中あとで感想
900MagicFingerprint-読んだ算数。データ構造を知ってるかどうかが鍵? 難しい。
600PrimeSums-○ 12minDP。小さな数から順に見ていき、合計weightごとの組み合わせ数を足し込んでいく。
入力に0もありえるのが意地悪。けど250よりこっちのが簡単かもしれん
250MonstersAndBunnies-○ 22min少しひねったDP。残りのモンスター数とウサギ数で回していく。
ウサギを殺す場合と殺さない場合との両方の確率を計算して高い方を取る。
サンプルのテストケースが異様に不親切だった。250でDPとは…

結果を見てみると、やはり難しめの問題セットだったようで、得点がプラスだった人は全員通過できてるみたいでした。

chokudaichokudai2009/02/24 17:51http://www.topcoder.com/stat?c=problem_solution&rm=268852&rd=12007&pm=8595&cr=22682274
コメントがあって見難いけど、easyこれで通りますよー

tomeruntomerun2009/02/24 19:07ひゃー
要は最後の1人になれれば良いってわけですか。これはやられた

2009-02-06

[][]SRM228 23:32 はてなブックマーク - SRM228 - TopCoderの学習のお時間

練習会ラスト。強い人たちがたくさん参加しててすごくよい練習になりました。

なんかdiv1 mediumが解ける気がしてきた(それは昔の問題が簡単なせい)


これeasyとmedium逆だろ、な問題セット。

点数配分がイレギュラーなときの難易度はたいがい [250超のeasy] > [500未満のmedium] 。

Levelタイトル試合中あとで感想
DIV1 1000Loopy-途中グラフっぽい実装系問題。ルールがとても難解。
コードを書き上げてみたらサンプルが通らなくてルールの解釈の抜けに気づく
DIV1 400BagsOfGold-○ 11minゲーム的シミュレーション。最大サイズ50^2、最大深さ50 なのでシンプルにメモ化再帰で。
DIV1 375BikeRace-× 38min→○時刻表的シミュレーション。アルゴリズム的にはそこまで難しくはないが実装量が多い。
時間を小数で扱わないといけないのに整数でやっててシステムテスト落ち

2009-02-05

[][]SRM229 00:27 はてなブックマーク - SRM229 - TopCoderの学習のお時間

練習会その5。昨日はお休みでした。昔ってこんなDPばっかりだったのか

Levelタイトル試合中あとで感想
DIV1 1000Hangman42-×ゲームシミュレーション。選択肢が少ない状態から勝率を決めていって、各ステップでは1手後のより小さい状態から勝率を求める。
方針は合ってそうだけど、どこか細かいところで見落としがあるみたいで通らず
DIV1 500BusinessPlan-○ 11minsimple DP。終了するのが目的金額ちょうどの時だけじゃなくてそれ以上でありさえすればいいことに注意。
このくらいの単純なDPはほとんど何も考えずに書けるようになってきた
DIV1 250Cafeteria-○ 13min時刻表シミュレーション。停留所ごとに最遅の出発時刻を調べる。
この時期のeasyからすると少しややこしい? 最近のDIV1 250で出てきそうな感じ

2009-02-03

[][]SRM231 23:20 はてなブックマーク - SRM231 - TopCoderの学習のお時間

練習会その3。25分遅れで参加。

点数の配分がなんでこうなってるのかいまひとつ分からないセット。

Levelタイトル試合中あとで感想
DIV1 1100Mixture-読んだ線形計画法を解くだけ。ライブラリ準備しとかないとコンテスト中に書くのは厳しいか。
doubleだと誤差落ちするらしい。昔は誤差の許容度が厳しかったようだ
これを機会にシンプレックス法のアルゴリズムを見てみるか
DIV1 450LargeSignTest-断念 40minMath。きのう覚えたDPをさっそく使ってみたらTLEした。
最大サイズ100万でO(N^2)だけど値が0になって無視可能な所がたくさんできるから大丈夫かと思ったが
素直に直接計算してやればよいのだった。logをとるのもあり
DIV1 200Stitch-○ 8min問題文読解ゲーム。やるだけ。200点だけど特別やさしいというわけでもない

suztomosuztomo2009/02/04 01:34練習会というのはどこかに予定が書いてあるウェブサイトがあるのですか?

tomeruntomerun2009/02/04 12:37これはchokudaiさん主催のやつですよー
http://d.hatena.ne.jp/chokudai/20090126/1232952987