敗戦記 - TopCoder部

2011-07-27

TopCoder SRM 513 Div1

TopCoder | 11:48

http://www.topcoder.com/stat?c=coder_room_stats&cr=22918966&rd=14538&rm=309335

夜中じゃないので、普通に起きてて参加しました。

Easy

最初読んだだけじゃ意味が分からなくて、3度くらい読む。
- 何とか理解した。
けどこういう、端っことかを考えてごそごそやるのは、辛いです。
取り敢えず、一つの皿の配置パターン数を出して、それをかけました。
なかなかサンプルが合わなくて、必死にコードとにらめっこしながら何とか出す。
提出。

161点くらい。

この時点で、他の人より早いわけでは無かったので、レーティング上昇をあきらめました。

Mediumはどうせ解ける気がしなかったので、開かずしばらくボケっとしたあとにEasyのチャレンジケースを考えました。

longlong忘れの人を落とそうと決めて、それを落とせそうなコードを書いた後に、easyの見直しをすること。

よく自分のコードを見てみると、ボールが丁度mountpositionに落ちてきていた場合、死ぬ気がする。
- 急いで直してもう一度提出しました。

81点くらい。

Medium

やっと開く。
- 記憶力ぱない人が神経衰弱をやるときにカードをめくる回数の期待値を求めろというような問題。
これは内容はすぐに理解できましたが、メモ化再帰で書き始めると、なかなかサンプルが合わない。
タイマーを見ながら、あと1分ぐらいだと確認して、必死におかしいところを探そうとしましたが、実はintermissionになっていて、すぐにchallengeに入ってしまいました。

Challenge

easyをintでやっている人を探す。
- 見つけた。投げる。
- 足し算で実装されていたので防衛されて-25　orz
- 幅のオーダーをあと3桁くらい上げて欲しかったと思いました。
結局特に他に何もしないままsystem test通ることを祈りながら、ぼーっとしてました。

System test

o--という感じでした。
1639 -> 1518 なんとか黄色に残れるというほどよい負けっぷりだったので、いいことにしたいです。
次回青落ちしそうですけどね。

2011-05-20

TCO11 Qualification Round 2

TopCoder | 16:44

http://www.topcoder.com/stat?c=coder_room_stats&rd=14530&cr=22918966

qual1でコンテスト前に仮眠を取ろうとしたら、寝過ごした悔しさを噛み締めながら参加。

開始後30秒くらい落ち着く。

Easy

開いて、読む。
すぐには完全に理解出来なかったので、サンプルを見る。
- 理解した。
前から見ていったときに、黒があって、なおかつ、それより後ろに白があったとき、一番後ろの白と交換するように書きました。

http://www.topcoder.com/stat?c=problem_solution&rm=308388&rd=14530&pm=11418&cr=22918966

Medium

開いて、読む。
PKUやAOJにある探索問題に近い感じだったので、落ち着いて書けば通りそうに思いました。
現在地と、時間を状態として持つ感じでbfsしました。

http://www.topcoder.com/stat?c=problem_solution&rm=308388&rd=14530&pm=11424&cr=22918966

Hard

開く。問題の意味の把握はそこまで難しくは感じませんでしたが、思いっきり数学だったので、半ば諦めながら読んでいました。
どうすればいいかさっぱりだったので、何かパターンのようなものが見つからないかと1～100までの数字でやってみたりしたのですが、特にコレといったヒラメキなどは得られませんでした。
- 考えられたのは、d(x)=(x+8)%9+1と表せるというところまでで、1～9の倍数で場合分けをしてその先が分からない間に終わりました。

Challenge

人のeasyを読んで、明らかにシステムテストが通らなさそうなコードがありましたが、長くて読む気が失せるようなものだったので、諦めました。
mediumにいたっては、どの人のコードも長くよく分からなかったのでおとなしくしてました。

System test

oo-で提出したものは通っていました。
mediumがいつもこれぐらいなら嬉しいのですが、多分div2の人が居たのであまり難しくないものが出題されているのではないでしょうか？

全体で70位というかなりいい順位につけたのでqualは突破出来ました。

1376 -> 1530 初めて黄色になれましたが、自分に都合のいい回がこないと上げたり維持したりするのは難しそうです。

2011-05-15

UTPC 2011

その他コンテスト | 10:50

オンライン参加のつもりでしたが、ICPCで組む人と顔合わせのつもりで,現地からの参加に変更してもらいました。

A

足すだけ。
- ファイルをA.cpp,B.cpp・・・みたいにつくっていたのですが、いつもはmain.cppひとつだけだったので、コンパイルに手間取りました。

B

()と文字数奇数の場合に注意して、書く。

C

O(2^n)で全探索しました。

D

シミュレーション問題。
- それほど強実装というわけではないですが、(自分にとっては)簡単というほどの問題でもなく、好きなタイプの問題でした。
取り敢えず書くも、最初のサンプルが合わない。
- '@'か'_'のところがおかしかったので直した。
必ず停止するかを判定するのかと勘違いして3番目が合わない。
- 直してサブミット。
- 3つWAってる。
- メモリ用のブールを15個しか確保してなかった。
- 1つWA。
- 訪れたかどうかのフラグに方向も含めてAC。

E

解いている人がそこそこ多いので、開いてみるもすぐには思いつかない。
スモールが16<=nだけど順番全生成だと間に合いそうにない。
仕方ないので飛ばす。

ここらへんで取り敢えず残りの問題を全部読む。

G

なんとなくEの次に解いている人が多かったのでこれを考えてみる。
- ソートして、大きい辺から3つ次に大きい辺から3つ取ってくる方法を試してみる。
- 通らない。
考えても大きい方から3つ、次に大きいものから3つ取ってくる以外の組み合わせが思い浮かばないので、必死におかしそうなところを探す。
- long long配列なのに、ソートでgreater<int>を使っていた。
- 直す。
  - WAが減ったけど半分ぐらいはWAのまま。
よく分からなくなってきたので飛ばす。