2006 TopCoder Open - Algorithm Competition

• の予選 (Qualification Round)に挑戦です． いよいよ，始まりました． TopCoder Open は TopCoder の "Crown of Jewels" ．一番，盛り上がるイベント・お祭りだそうです．

予選を通過できるのは 750 名．普段のレーティングが上位の 100 名は，自動的に予選を免除されますので，残された 650 の椅子を巡る戦いです．

• 予選 (Qualification Round): 750 名通過
• Round1: 750 名 -> 400 名
• Round2: 400 名 -> 200 名
• Round3: 200 名 -> 100 名
• Round4: 100 名 -> 48 名

見事，Round4 を勝ち抜いた 48 名は，ラスベガスにご招待され，オンサイトで決勝です．

通常の SRM と異なり，予選はちょっと形式が異なります．

• 問題は 2 問，制限時間は 1 時間
• 開始時間は決まっていない．24 時間以内ならいつ挑戦をはじめてもよい
• チャレンジ・フェーズはなし

問題セットは，5 種類用意され，そのうちどれか 1 種類が自動的にアサインされます．各問題セットから，上位 (650/5 =) 130 名が予選を通過できます．早速，アリーナに参加してみると

Set14 にアサインされました．問題 1 種類につき，Room が 3 つ用意されていますね．計 15Room です．

各 Room ごとに，およそ 170 名ほど割り振られていました．ということは，参加者の総数は 170 x 15 = 2550 名ほどか．

予選通過のためには各 Room 内で，130 /3 = 43 位くらいに入るのが目安になるか．自分が挑戦した時間が終了近かったので，もうすでに終わっている人のスコアをあらかじめみることができました．自分がアサインされた Room14 では，こんな様子でした．

なるほど，ボーダーラインの 43 位に入るためには，2 問とも確実に，その上ある程度スピードも要求されそうです．まだシステムテストは終わっていないから，ボーダーはこれより下がるでしょうが，思っていたより，レベルが高そう．．それとも問題が簡単なのか？．．

と思いつつ，自分もスタート．

SlowKeyboard (code)

250 点問題．問題の意味をつかむのに，一苦労．

結局，Brute Force で全パターンを調べました．この時点で，18 分ほど時間をとられました．まずい．

DigitFilter (code)

750 点問題．

数字が与えられます．

k = "12XX355"

X のところは判明しない桁です．この数字 k が(num)で割り切れるとした場合，このような数字 k は何通りありますか？という問題です.たとえば，

k = "1X"，num=3

ならば，"12", "15", "18" の 3 通りです．

k = "23X34XX24XX34X", num=17

ならば，58823 通りです．

DP でいけると思い，方針じたいは結構早めに決まったのですが，実装にとまどる，とまどる．あせっていたのか．．結局，30 分ほどかかり，Submit．

2 問あわせてスコアは 536.71． Room14 内で，65 位ほどでした．．これはだめか．．

結果

最終的なシステムテストの結果です．( Room Statistics )

Room7/9/14 は同じ問題セットだったそうです．その Room7/9/14 をあわせた中での順位は，

85 位．130 位以内なので，予選通過ですよね？まだ正式連絡はきていないけれど．

• Room14 だけ，なぜかハイスコアの人が多かったこと
• 750 点問題に落ちた人が，相当多かった

ということで，85 位に入り込めたっぽいですね．

750 点問題で落ちた人は，可能な数字をすべて生成してから，それらを num で割り切れるかどうかをチェックしている人が多かったようです． k の最大の長さの条件は 18 ですので，k = "XXXXXXXXXXXXXXXXXX" の場合，必要な数字は 10^18 通りになってしまいます．これを全て調べるのは，絶対無理ですね．．

今日の教訓

• もっと正確かつ早い実装力が必要．．