Hatena::Grouptopcoder

敗戦記

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に戻ってきて意気消沈です。