週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

SRM 390に今朝2時から。初参加なのでDiv. 2で参加です。

初参加前に過去問を解いてみました。結果としては全部解けたものの時間ぎりぎりで、しかも250点以外はSystem testを落とすという体たらく。250点問題も、はじめ問題を誤読していて、面倒なDPを書いていました。正しく読めていれば10分せずに片がつくはずです。とりあえず、

  • 問題はよく読む。特にサンプルは手で解いてみる。
  • 範囲ぎりぎりのテストケースを入れる。
という普通の教訓が得られました。本当になまっています。もっとも、問題をよく読むとかコンテスタント時代もよく反省した覚えがあります。

練習の成果なのかコンテスト本番はDiv. 2で54位、部屋一位。rateは1468もらいました。まだblue coderなのでつぎもdiv. 2なのでしょうか?どこからdiv. 1になるかわかりません。

問題のメモを次に。

  • 250 pts : 11分。答えが2から8となるテストケースを投入。慎重すぎです。
  • 500 pts : 26分。値域が大きいのでオーバーフローに注意。なぜかkの値域が大きいことも心配してました。106ループなんて0.1秒なのに。さらにnumber = 1,000,000のケースを手計算で検算して、検算にミスをして酷く混乱して時間をかけてしまいました。
  • 1000 pts : 33 分。killed in challenge phase。nCrをnext_permutationのノリで展開するコードを書き始めて脳みそが溶け始める。2^nをまわしてpopcountを取ればすぐでした。

終了時には部屋2位でしたが、challenge phaseで一人が1000 ptsをすべて撃墜するという荒業を見せて戦況が混沌とします。3位くらいまで下がったので、私も一位の人の500 ptsを撃墜。下☆克☆上しました。javaで数字をStringに変換してそれをn個concatしてBigIntegerに変換している遅そうなコードだったので、境界値で簡単に撃墜できました。 ちなみに撃墜した人は、とりあえず'?'をたくさん投げたらみんな落ちたとのこと。なんじゃそれ。

  • 以下はうそ罠でした~
部屋でのチャットルームで1000 ptsの罠がわかりました。{"a","a","a"} 1という入力に3と答えたら負けです。 パターン1でマッチする文字列とパターン2でマッチする文字列との間に重複がある場合、重複して数えているのでそれを除かないといけません。 A+B+C-AB-BC-CA+ABCみたいなことをすれば大丈夫です。ちなみに、この問題の正解率は0.8 %でした.

おっしゃるとおり"exactly"なので上の場合は0と答えないといけないようです。どうするんだこれ。

そのほか備忘録。

  • challengeは落としやすいのを狙わないとだめ。上の人を落とそうが下の人を落とそうがもらえる点数は同じです。さらに落ちるほうの人はどうせsystem testで落ちます。
  • いいツールを導入してテストケースを簡単に追加できるようにしないと手間です。
  • 直前の練習が多分効果的でした。コンテストなんてN年ぶりなので。
  • 2時だと頭がメルトします。
スポンサーサイト
コメント
この記事へのコメント
御無沙汰しております。nod_chipです。ICPCのOB/OG会では大変お世話になりました。
TopCoderへの参加お疲れ様です。自分も数ヶ月前から参加しておりますが、実力が中途半端なせいで青と黄色の間を行ったりきたりしている今日この頃です。
レーティングが1468とのことですので、次回はdiv1での参加ですね。(div1の条件は1200以上です。)しばらくはGusさんを目標にがんばりたいと思います。

TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed
http://gulfweed.starlancer.org/d/index.php?itemid=10

こちらのページでコーディング補助を行ってくれるArenaプラグインが公開されています。もし御覧になったことが無いのであれば、ぜひ御覧ください。きっと強力な助っ人になると思います。
2008/02/03(日) 16:33 | URL | nod_chip #d7.ZNk7c[ 編集]
どうもどうも。お久しぶりです。gwtコメント以来でしょうか?

プラグイン導入してみました。uploadが簡単になるのはいいですね。TZTesterだけは使い方がよくわかりませんでしたが。

私はおそらく土曜にSRMがきたときしか参加できませんが、よろしくお願いいたします。ってカレンダーを見ると、ここから1-2ヶ月はTCOの方がメインでSRMは少なくなってますね。
2008/02/03(日) 21:53 | URL | Gus #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/301-986d9d14
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。