Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-05-29

UAPC 2010

00:03 | UAPC 2010 - naoya_t@topcoder を含むブックマーク はてなブックマーク - UAPC 2010 - naoya_t@topcoder UAPC 2010 - naoya_t@topcoder のブックマークコメント

http://rose.u-aizu.ac.jp/onlinejudge/cvolume.jsp?contestID=UAPC2010

途中から参戦。

  • Aを解いて、Bで躓いて、Cの問題が理解できなくて、諦めて食事して、戻ってDを解いて、Gを解くのにサイコロを作って、提出しようと思ったらもう試合終了していた
  • へぇー問題英語なんだーと思って頑張って読んでたけど、日本語で読めることに翌日気づいた
  • というわけで風船2個><
  • 続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100529

2010-05-28

Member SRM 471 Hard(1000): ConstructPolyline

| 12:53 | Member SRM 471 Hard(1000): ConstructPolyline - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM 471 Hard(1000): ConstructPolyline - naoya_t@topcoder Member SRM 471 Hard(1000): ConstructPolyline - naoya_t@topcoder のブックマークコメント

  • たまにはDiv1 Hard問題も眺めてみないとSTL使いこなし以上の実力がつかないと思いHard問題を開いてみる
  • 続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100528

2010-05-27

Member SRM471

01:57 | Member SRM471 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM471 - naoya_t@topcoder Member SRM471 - naoya_t@topcoder のブックマークコメント

DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
1 250 PrimeSequences 提出 - - - _ 0
1 500 ThirteenHard サーバ死に - - - _ >5
1 1000 開いてない - - - - _ -

500解いてて気がついたら接続が切れてた。再ログインしたらSRM471が消えていた。ノーゲームか。

折角250と500は解いたので、書いたコードは晒しておこう。どちらも解き方はすぐに思いついたが実装がさらっと行かずデバッグに時間を取られた。

続きを読む

Member SRM471 Medium(500): ThirteenHard (再考)

| 12:43 | Member SRM471 Medium(500): ThirteenHard (再考) - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM471 Medium(500): ThirteenHard (再考) - naoya_t@topcoder Member SRM471 Medium(500): ThirteenHard (再考) - naoya_t@topcoder のブックマークコメント

(最初に書いたコードはこちら: http://topcoder.g.hatena.ne.jp/n4_t/20100527/1274893027

  • (N-1)番目に到達すると分かっている(最短かは分からない)時刻があるなら、それ以降の時刻については検証無意味。
    • priority_queueを使ったほうがスマートかな。
  • int[25][2^13]である駅までの最短時間が分かったとしても、その後でmod13死にするかもしれないのでmod13が違うやつは生かしておくべき。最短との比較枝切りをやめると最悪ケースでTLE
    • やっぱりint[25][13][2^13]でないと駄目。
  • それから
    ...
    bool boo = false;
    if (sm>0) {
      for(int k=0,p=1; k<13; k++,p<<=1){
        if (msk & p) {
          if (((sm + 13) - k) % 13 == 0) { boo=true; break; }
        }
      }
    }
    if (boo) continue;
    ...

ここは

    if (msk & (1 << (sm % 13))) continue;

と等価ではないか!

勿論、C/C++の演算子の優先順位に従えば括弧は省略できて

    if (msk & 1 << sm % 13) continue;

と書けるが直感的にこれが(msk&1)<<(sm%13)などに見えてしまって怖くてたまらない。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100527

2010-05-25

TCO2010 Qualification Round 3

| 10:57 | TCO2010 Qualification Round 3 - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO2010 Qualification Round 3 - naoya_t@topcoder TCO2010 Qualification Round 3 - naoya_t@topcoder のブックマークコメント

  • みんなQR2までで通っちゃってるみたいで寂しいQR3
  • 難易度は普段のDiv2程度?妙に易しく感じられた
  • 3問全部submitできたのってDiv1・Div2通して初めてだ
  • 一瞬全体の20番台だった!コンテスト中なので通るかはまだ不明…お願い600以内に残って
  • →500が恥ずかしいミスで落ちて111位。とりあえず予選通過。そしてとりあえず黄色に戻れた

教訓:

配列は端をちゃんと見る

  • レーヴェンシュタイン距離5未満のミスで落ちた場合は何かペナルティを課すことにしよう…

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
- 250 SumRectangle 提出 - passed - 224.76 (9'44'') -
- 500 WhatThisChord 提出 - failed - 459.62 (8'33'')→0 4
- 1000 CuttingGlass 提出 - passed - 625.24 (25'27'') -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100525

2010-05-23

Google Code Jam 2010 Round 1C

22:01 | Google Code Jam 2010 Round 1C - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1C - naoya_t@topcoder Google Code Jam 2010 Round 1C - naoya_t@topcoder のブックマークコメント

5/23 6pm〜

1Bで通ったので観戦モード(と言いつつ問題を解く)。

外出先から戻って18:25からのスタート。

時間内に3問とも解けた。終了後、practiceのデータを通したらC-large以外は全部通った。76点相当。実行時間+submitの手間を考慮しても141〜142位あたりで通過。

ていうか何でC-large通らなかったんだ?(後述)

続きを読む

Google Code Jam 2010 Round 1B

11:52 | Google Code Jam 2010 Round 1B - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1B - naoya_t@topcoder Google Code Jam 2010 Round 1B - naoya_t@topcoder のブックマークコメント

5/23 1am〜

夢の満点通過ktkr

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100523

2010-05-22

Google Code Jam 2010 Round 1A

| 10:30 | Google Code Jam 2010 Round 1A - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1A - naoya_t@topcoder Google Code Jam 2010 Round 1A - naoya_t@topcoder のブックマークコメント

5/22 10am〜

A-small/A-largeだけ通して1068位で惜敗。1Bでリベンジ!

(あとで書く)

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100522

2010-05-21

SRM470

02:05 | SRM470 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM470 - naoya_t@topcoder SRM470 - naoya_t@topcoder のブックマークコメント

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 DoorsGame 提出 - passed - 192.41
- 500 DrawingLines 間に合わず - - - 0
- 1000 -- 開いてない -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100521

2010-05-12

TCO Qualification Round 2

22:06 | TCO Qualification Round 2 - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO Qualification Round 2 - naoya_t@topcoder TCO Qualification Round 2 - naoya_t@topcoder のブックマークコメント

予選通過ならず。駄目だこりゃ...

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 JingleRingle 提出 - passed - 180.43
- 500 FuzzyLife 間に合わず - - - 0
- 1000 - 開いてない -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100512

2010-05-10

Google Code Jam: Qualification Round 2010

14:59 | Google Code Jam: Qualification Round 2010 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam: Qualification Round 2010 - naoya_t@topcoder Google Code Jam: Qualification Round 2010 - naoya_t@topcoder のブックマークコメント

http://code.google.com/codejam/

暫定99点→C-Largeを落として76点 (暫定76位→1510位)。たぶん通過。

参加者10492名、予選通過者(Score≧33)は8523名。

続きを読む

問題名smalllarge備考
A Snapper Chain 0:46:06(WAx2) 0:47:05
B Fair Warning 1:25:56 1:26:37
C Theme Park 1:52:19 1:55:55(WA)
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100510

2010-05-04

SRM469

21:56 | SRM469 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM469 - naoya_t@topcoder SRM469 - naoya_t@topcoder のブックマークコメント

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 TheMoviesLvelOneDivOne 提出 - passed - 157.78
- 500 TheMoviesLvelTwoDivOne あきらめ - - - 0
- 1000 -- 開いてない -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100504

2010-05-03

TCO10 Qualification Round 1 (再試合)

09:37 | TCO10 Qualification Round 1 (再試合) - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO10 Qualification Round 1 (再試合) - naoya_t@topcoder TCO10 Qualification Round 1 (再試合) - naoya_t@topcoder のブックマークコメント

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 GirlsAndBoys 提出 - passed - 206.39
- 500 RobotSimulation 提出 - failed - 0
- 1000 SequenceMerger 間に合わず -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100503

2010-05-02

TCO10 Qualification Round 1 (※ノーゲーム)

10:02 | TCO10 Qualification Round 1 (※ノーゲーム) - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO10 Qualification Round 1 (※ノーゲーム) - naoya_t@topcoder TCO10 Qualification Round 1 (※ノーゲーム) - naoya_t@topcoder のブックマークコメント

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 DNAMatching 提出 - passed - -
- 500 Palindromize3 間に合わず - - - 0
- 1000 - - -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100502