Hatena::Grouptopcoder

敗戦記

2011-07-27

TopCoder SRM 513 Div1

| 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

| 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のまま。
  • よく分からなくなってきたので飛ばす。

E

  • もうこれぐらいしか解ける気がしないので戻ってきた。
    • 取り敢えず幅優先でn<=16を通した。
    • よく考えるとbでソートしたあと、bの小さい問題から順に見ていって、n問ファーストアクセプタンスを得るのに必要な最短時間を更新していけば、うまく行くような気がしてきたので書く。

I

  • Gが分からなかったで取り敢えずこれに。
    • xorを使うと、欲しい値以外は0に変換出来るなとか考えて、その値が1になってくれれば解決じゃないだろうかと、ずっと試行錯誤していました。
    • 時間がきて終了。

http://atcoder.jp/contest/8/standing

5問解いて50位でした。

F以降の問題をもう一問ぐらいとけるようにぐらいは成っていたかったように思いました。どうすれば難しい問題が解けるようになるんでしょうかね。

Fの解答を聞いたときはきれいすぎる生成方法にとても驚きました。

2011-05-04

TopCoder SRM 505 Div1

| 08:19

昨日の8時から参加。

Easy

  • 読む。
  • 問題の意味は分かったが、解法が全く思い浮かばずしばらく悩む。
  • 上下左右にYがあれば、つながっているひとかたまりのものと考え、上下左右にYがなければそこにYをいれた後、塊を数えたらサンプルが通ったのでそれを提出した。

Medium

  • 読む。
  • サンプルを見て、D/2からDまでは数える数に入るだろうということを考えただけで終了。

Challenge

  • Easyを開いて、微妙に変なのがあったので撃墜しようとしたけれど一回失敗した挙句に、先に落とされて終わりました。
  • 知らないうちにチャレンジされて自分の300が死んでました。

-25点で終了。

1353 -> 1196 (-157) 下がり過ぎ・・・。DIV2に戻ってきて意気消沈です。

2011-04-21

Codeforces Beta Round #69 (Div. 1 Only)

| 14:28

いつもと違ってTopCoderのようにdiv1,div2が分かれる形式になってました。

A

  • 問題文の長さにへこたれながら読む。
  • 最初迷ったけれど全探索でいくことにしたO(3^7)ぐらいでまにあうことも分かった。
  • ここから、友情ペア数が最大なもので、最も平等に近いものを選ぶと勘違い。
  • サンプルがあわない。よく分からないバグに苦しめられる。
    • サイズを取得する配列を間違えていたりした。直した。
  • サンプルがあったので提出。
  • 問題文をよく読んで、最も平等にした後、友情パワーを高くするんだと把握。
  • 書きなおすが、やはりバグバグな感じになる。
    • なんとか、サンプルがあったので提出したら通った。

48分

B

  • A問題なのに時間がかかりすぎたことを残念に思いながら開く。
  • 面積の割合を求めればいいと分かったので、aとbの長さの比で場合分けをして書く。
  • bが0の場合があったので、それを考慮して直す。
  • プリテスト通過。

C

  • 読む。
  • 読んでいる間にBをhackされたので、Bに戻る。

B

  • 今度は、aが0の場合を忘れていたので、それを考慮する。
    • 最初、0.5とするところを0にしてWAをもらう
  • 直してAC

100分

Hack

  • もうここらへんからCを読む気力が起きなくなってしまったので、Bで変な人がいないか探す。
  • なんとなく一人が0.5を考慮していないような気がしたので、投げてみたら失敗した。
  • そんな感じで終了。

System Test

  • oo--- ハックのお陰で一応通過出来た感じだと思います。

1666 -> 1650 (-16) ギリギリDiv1に残れました。次は高見の見物ができそうです。