Hatena::Grouptopcoder

敗戦記

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に残れました。次は高見の見物ができそうです。

2011-04-16

Codeforces Beta Round #68

| 10:45

あまりに眠すぎるうえにCが解けないので途中で寝てしまいました。

A

  • 開く。map<int,string>に点数を負にしてつっこむ。

4分

B

  • 問題文が長いけれど頑張って読む。
  • キューに突っ込んで、幅優先探索を書く。
  • 2回ほどプリテストでWAをだした後通過。

45分

C

  • 開く。ここらへんで眠気が高まってきて、問題文の意味の把握にも手間取る。
  • Nクイーン問題に似たような奴っぽい?
  • 紙にいくつか小さいケースを書いてみても結局分からなかったので、眠かったこともあり、残り30分ぐらいで寝ました。

System Test

  • oo--- Bは微妙な感じがしたので安心しました。

1633 -> 1666 (+33) 紫に戻れました。

HillHill2012/11/15 02:46You're a real deep thinker. Thanks for sharnig.

ftcfwuknftcfwukn2012/11/15 12:37Hmh9Qx <a href="http://inqrsekwlrnt.com/">inqrsekwlrnt</a>

2011-04-14

Codeforces Beta Round #67 (Div. 2)

| 22:27

翌日は一限からでしたが試しに参加してみました。

前回、前々回がいろいろと酷い出来で凹んでいたので、満足のいく回で良かったです。

A

  • long longから0を省いてstring型にする関数と、stringを数字にする関数を書いた。

4分

B

  • 実装ゲー。
  • mapとか使いながら、pair<int,string>の配列にintをマイナスにしてつっこんでソートして出力した。

16分

C

  • 読む。最初TLEしない解法がすぐに思い浮かばない。
  • でも他の人達は即効で解いている人もいるので、そこまで難しくないのだろうと考える。
    • 最大公約数の約数を全列挙することにした。
  • あとは約数を-にして突っ込んだvectorをソートしてlower_boundした。
  • 提出した後に微妙にlong longを使っていなかったことにビクビクしていた。

36分

このあとDとEを読むが、Eは幾何なので無理で、DはTLEしない解法が思いつきそうになかったのでhack狙いで提出しようかなどと考えて取り合えずCのハックへ。

Hack

  • Cであきらかに一つのクエリにO(gcd(a,b))欠けている人が居たので落としました。
  • ここらへんでよくみると去年一緒にICPCに出てくれた先輩が同じ部屋だということに気づく。
    • ただ、Cで一つのクエリをO(gcd(a,b)^(1/2))で処理していて、これだと最大で1万×1万以上になり、ギリギリ間に合わさそうなので落とさせていただきました。

D

  • ここらへんであとは約数を全列挙しているものしか残っていないのでDのTLE解を書く。
  • 最小値を0にしたままだったのでプリテスト通らない。
    • 直してアクセプト

95分

Hack

  • 明らかに自分と同じ解法の人が居たので、急いでDのジェネレーターを書く。
  • 入力の形式を勘違いして何回か向こう側で弾かれる。
    • なんとか直して提出。
  • 二人ほど落とす。
  • 最後にCでTLEしそうな人が居たので落とす。

一限からなので終わったら速攻で寝ました。

SystemTest

  • ooox- Dは寝ながら考えていたのですが、解法全然思いつきませんでしたね。

結局3問とハック点500点で3212点で部屋一位、参加者全体では46位でした。

TLEが狙える回は、ソースコードを細かいところまで見る必要がなく、forの個数とかだけを見ればいいので恐ろしく楽でいいと思います。

ただ、部屋内でSystemTestで結構落ちている人もいて、約数全列挙でもスクリプト系言語で書いた人は約数の個数が多いケースでTLEになっていたようです。次からはせっかくのチャンスなので取りこぼしを少なくしたいです。

1533 -> 1633 (+100) 切りの良い上昇。

2011-03-30

Codeforces Beta Round #65 (Div. 2)

| 11:40

サンプルが結構強かった回。

ROOM 71

A

  • 開く。読む。サンプルを見てだいたい把握。
  • 10以上なのかより多いのか一瞬迷いましたが、10より多いにして提出。
  • サンプルが強いようで10以上で分けるとはじかれるみたいですね。

4分

B

  • 開く。読む。
  • だいたい把握して適当に書くとプリテスト通らない。
  • 仕方ないので、頭の悪さを嘆きながら数式どおりにaiを設定していく。
  • 大分混乱して時間がかかったけれど通った。

29分

C

  • 意味はすぐに把握したけれど愚直解法で大丈夫なのか心配になる。
  • まぁ愚直解法でダメならTLE狙いに行けばいいかと思って、取り敢えず書く。
  • わりとすぐに書けたけれど、愚直じゃない解法が思いつかないか考えてしばらく提出せずにいました。
  • しばらく考えても分からないので提出。

58分

Hack

  • CでTLE狙いするためにランダム出力のジェネレーターを書く。
  • 自分の書いたコードでも最大ケースがほとんど一瞬で終わってしまう。
  • Hack諦める。

D

  • ひらいて、読んで、実装重いと思いました。
  • 取り敢えずやるしかないのでゴリゴリと書き続ける。
  • スペルミスと細かいミスで何度か弾かれたあとプリテスト通過。

1時間41分

あとは他の人のコードを読んでいる間に終了。

System test

  • ooox-
  • Dは二つの正方形の交差判定をちゃんと出来ていなくて落ちました。

2490点で全体140位でした。

最近の微妙っぷりから多少は脱却出来た気がします。

感想

  • Dはあまり通る気はしなかったのですが、それでももしかしたらとか考えていました。
  • それからBを通すのに結構時間がかかったのがわりと問題な気がします。

1527 -> 1596 (+69) 多少上がったので、いいほうなんじゃないかと。

上位者を見ていると、結構いい順位に入ってもそう簡単にはオレンジにはなれないようです。

SteffenSteffen2012/11/15 07:31Big help, big help. And superlative news of cuosre.

najkyjnnajkyjn2012/11/16 05:38jZDUce <a href="http://vcipsfflhbup.com/">vcipsfflhbup</a>

2011-03-27

Codeforces Beta Round #64

| 13:24

レートの低下が止まらない・・・。

ROOM 10

A

  • 開く。
  • 読解に手間取るが、web辞書を使いながらなんとか読む。
  • 一番したのサンプルを見ると、一つ大きいサイズの箱には、もとの箱の左下半分を上と右に詰めて、大きい三角を詰め込めばいいと気づけたので、空白の数を数えると3倍ずつになることを確認し、0の場合に注意してsubmit
  • プリテスト通過

14分

B

  • 読む。どうもこれも意味が分からない。
  • 仕方ないので、一旦Aで0を忘れている人がいないかを探しに行きました。
    • 一人だけ落としてもどってきました。
    • 0で落ちるコードは殆ど刈り取られた後のようでした。
  • 取り敢えずメッセージを文で区切って、サイズがn以下なら答えを増やしていくとプレテスト5でWAる。
  • メッセージを出来るだけ少ない送信回数で詰め込むのかな?
    • サンプルの3を見ると前から詰め込んでいるよう。
    • 書く。なぜかスペースは数えないと勘違い。
    • 送る。プリテスト通過。

1時間2分

C

  • 読む。意味は分かったけれど全然考えが思いつかない。
  • 諦める。

D

  • 開く。幾何だったので無理です。

Hack

  • 仕方ないのでAとBのハックを狙うことに。
  • Aはもうすでに提出者がいなく、ミスっているような人は見つけられませんでした。
  • Bのコードを読むとスペースを数えている人がいたので、問題を確認しなおすと読み落としがありました。
  • 仕方ないので、また絶望的な気分になりながら読みにくいコードが多いBを読んでいく。
    • 文字数の数え方がおかしい人がいたので終了間際にハックをする。
    • 一回目ミスって、もう一度よく確認して再度送る。
      • Successful hacking attempt

150点獲得

System test

  • ox---
  • やはりBはアウト

感想

  • 結局624点で431位でした。
  • 1486 -> 1479 (-7) レーティングの低下が止まらないです。そろそろ底に到達して欲しいところです。

(追記)

  • 1486 -> 1527 (+41) レーティングの式が変更になったとかで上昇して青にまで戻れました。