eomole as a contestant このページをアンテナに追加 RSSフィード

2014-04-13

TCO 2014 Qual 1A

| 19:59 |  TCO 2014 Qual 1A - eomole as a contestant を含むブックマーク はてなブックマーク -  TCO 2014 Qual 1A - eomole as a contestant  TCO 2014 Qual 1A - eomole as a contestant のブックマークコメント

1週間延期されたのがあった。

去年の TCO 予選シーズン以来 TopCoder に出ていなかったのでかなり久々。

Easy: 文字列に対して適当な prefix を切り出して suffix N 文字をソートという処理を繰り返して辞書順最小の文字列を作る問題。Prefix の選び方は1文字ずつ前進で N 文字になるまで限界まで続ける戦略が最適であるのが、考察するとわからなくもないのでそれを実装するとよい。もう少し効率よくするなら、先頭 1 文字を除いてソート、先頭 N 文字を切り出してソートが最終結果なのでそれを実装すればよい。全体ソートして先頭 N 文字を切り出すという嘘解法にたどり着きやすいけど "TOPCODER" で落ちるので、サンプル親切だった。

Mid: 文字を並び替えて辞書順最小の文字列を作る問題。ただし、元の位置から N 文字以上離れてはいけない。これは先頭から使える文字を貪欲に置いていけば OK。ただし、その場所を逃すと制約を満たさなくなるという文字が生じたらそれを置かないといけないことに注意する。

Hard: よくわからなかったけど 8N くらいの DP でいいらしい。

Challenge: 灰色さんが "TOPCODER" で落ちるはずの嘘解法を提出していたので3人くらい落とした。(実のところ1人目はTLE狙いだった。枝刈り落とそうとしてしまうのやはり辞めた方がいい。まあ結果オーライ)サンプルくらいチェックしようね?

3 年前の TCO の時期のレートを超えて highest 更新。あと部屋 1 位で div で獲得した最高のスコアだったらしいけど、div 1.5 みたいな感じなので微妙い。

2012-03-18

SRM537

| 14:00 | SRM537 - eomole as a contestant を含むブックマーク はてなブックマーク - SRM537 - eomole as a contestant SRM537 - eomole as a contestant のブックマークコメント

賞金付きなのでたまには真面目に参加してみる。

275

AとBがXと適当なYから作れるか調べればよい。AもBもXだけで作れてしまうならYは何でもいいので-1。それ以外のときは1<=Y<=max(A,B)の範囲に収まるので全部調べて数え上げる。小さいのでユークリッドの互除法とかは不要。

200.27

http://community.topcoder.com/stat?c=problem_solution&rm=312058&rd=14730&pm=11817&cr=22695644 (要ログイン)]

500

Bit別に処理できるので、各部屋の各bitが1になる確率をDPで計算していけばよい。

352.97

http://community.topcoder.com/stat?c=problem_solution&rd=14730&rm=312058&cr=22695644&pm=11822 (要ログイン)]


925

Euler Cycle を貪欲に取り除いていくのではダメなんだろうなあ。と思いつつ放置。

Compiled.

Challenge Phase

TLE狙いで撃墜しようとしたけどミスした。あとで見たらWAだった。

-25.00

結果

528.24 で 103位。1374 -> 1534 で黄色復帰。闇雲な撃墜をやめたい。。

2011-05-15

TCO 2011 Qualification Round 1A

| 08:34 | TCO 2011 Qualification Round 1A - eomole as a contestant を含むブックマーク はてなブックマーク - TCO 2011 Qualification Round 1A - eomole as a contestant TCO 2011 Qualification Round 1A - eomole as a contestant のブックマークコメント

UTPCの懇親会に参加していた関係で飲酒コーディングになってしまいますが、通ればよかったし、Div2相当だと予想したので参加してしまいました。

250

酒で問題よく覚えていない。最初ソートして判定しようかと思ったが、この状態で場合分けがちゃんとできるわけなかったので、決め打ちして条件を満たすか調べる方に書き直していたら無駄に時間がかかった。ような気がする。

204.70

source code (要ログイン)

500

酒で問題よく覚えていない。曲の切り替わる時間をDPで前処理して、それらを適当に加算した。ような気がする。

432.36

source code (要ログイン)


1000

酒で問題よく覚えていない。場合分け色々しないといけなかったっぽいが、この状態では無理だった。ような気がする。

Opened.

Challenge Phase

酒でプログラム読めなかった。。

結果

637.06 で 156位になりました。1820 -> 1863 で 1000 解けなかったのにレート上がって不思議。別に大丈夫かと思って出てしまったけれども、明らかにいろいろなスキルが下がってひどかったです。次のラウンドからはきちんと万全の体調で出ます。

2011-02-11

SRM 497 Div1

| 23:33 | SRM 497 Div1 - eomole as a contestant を含むブックマーク はてなブックマーク - SRM 497 Div1 - eomole as a contestant SRM 497 Div1 - eomole as a contestant のブックマークコメント

赤ブルの濫用で弱ってますが、起きたときにはまだ10時だったので参加できました。

250

増加、減少の情報から順列を再構築する問題。部分列に対する解を利用して1つずつ伸ばしていく方法をとった。今思うと後ろからやった意味ってあったのだろうか。

193.45

source code (要ログイン)

550

構文解析+αの問題。再帰降下で愚直に書いたあとに前処理を書き足したり、うっかり Greedy にできると思ってしまったりで手間取っている間に時間終了。。にしても、最初に concat が必要って仕様、どうにかならないんだろうか。

Opened.

1000

読んでる暇なかった。部屋で出してる人なし。

Unopened.

Challenge Phase

Twitterで知っている人をせっかくなので落としてあげたいと思ったけど、長くて断念。結局何もせず。ちなみにその解答はテストに通った模様。

結果

193.45 で 190位になりました。1630 -> 1672 でレートが収束気味です。卒論ももうすぐ終わるので、Medium が十分速く解けるように励みたいです。