hosの日記です

2010/07/02 (Fri)

[]国内予選 14:40

()内は後から調べました

開始 (00:00:00)

繋がらない……

7問ありました。Bを読む。すぐ。CDEあたりを見るが長くて読めない

Bを組む。提出。WA……

ものすごく焦る

交代してmattyaさんがAを通す

A (00:21:12)

一旦落ちついてDやEを眺める

Bをデバッグ。見つからない……

mattyaさんがCを書きだす

Bのバグ発見、急いで直して提出

B (00:33:11) 1 wrong try

roofさんにDの問題を聞いてサンプルの絵を見る

mattyaさんがCの残りを書く

C (00:38:13)

順位まずい…(この時点で7位)、ペナルティも酷くとても焦る

Dをひたすら書く

D (01:11:58)

順位は良さそう(40010とほぼ同時に通し2位)、しかしこの後どんどん抜かれて行く…

mattyaさん「Eはhosがやったほうがいいです」らしいのでちょっと考える

やや心配だが普通に通せそう

書く。提出。WAorz

嘘解法かと不安になったがすぐに撃墜できて修正

E (01:40:36) 1 wrong try

このままだと_に負ける…

Fで「この部分問題が解けると良い」を聞くがわからない…

mattyaさん「Gの方が簡単なのでGやりましょう」

によりGに集中することに

mattyaさんが幾何ライブラリを書き、roofさんがサンプルの絵を描き、自分が紙にコードを書く

組む、いろいろバグ

いろいろバグってるうちに、ここで駒場会場PCが強制シャットダウンというトラブル!

コード印刷して紙面で書く、PCが重い…

組む、サンプルが通る

とりあえず提出してみようということで提出、WAorz

40010に抜かれていて3位、ぴんち

入力データを印刷して2人にひたすら変な答えさがしてもらう

コード上では全然バグが見つからず、残り時間も絶望的に…

…というところでデータ1つ目で既におかしい挙動をしていることが発覚

原因がよくわからないまま場当たり的な修正をしてみる、答えは合ってそう…

提出、通ってしまった

G (02:57:15) 1 wrong try

mattyaさんがFの方針をひらめく!

がもちろん残り時間何もできず、祈って終了

終了 (03:00:01)

結果

1位でした。やったー

こう改めて見ると自分が担当すると遅かったりWAってたりダメダメなので、今後に向けて改善点がいくつも。

B→A→E→C→D→G→Fの順で一発で通せれば理想だったかなー。

2010/06/28 (Mon)

[]実プロ 2010.06.28. 00:40

B

Millar-Rabinで通してしまった

A

まっちゃさんに一任。めんどそうだった

C

自分は解いたことがあったような気がしなくもない。まっちゃさんメインでペアプロした

D

ただのDPなのにバグバグだった。終了後に通した

E

O(C^2 log C)がTLEして悲しんだ。終了後O(C log C)まで良くしたがたぶんO(C)が可能

2010/06/27 (Sun)

[]模擬国内予選 21:57

開始 (00:00:00)

XCodeの保存できないバグに悩まされて事故った

Bがなんかだるそうだったのでまっちゃさんに先にAをやってもらうことに

Dを読んで「どうせDijkstraじゃね」とか思っていた

A (00:14:19)

Bを書く、サンプル通る、出す、WAorz

交代も考えたが冷静になってバグをとって通した

B (00:25:59) 1 wrong try

Eを読む、誤差がちょっと怖い

Dを確認、近くにいた_が難しい難しい言ってるのが聞こえ(?)、よく考えたら嘘であったことに気づき焦る

その間にまっちゃさんがCを華麗に通す

C (00:40:15)

ちょうどDがわかったのでさっさと組む

D (00:54:20)

Fがめんどいらしいので誤差気にせずEに特攻ということに

割とさくっとサンプルが通って提出したがWAorz

印刷して交代

まっちゃさんがFの入力(水門の0/1とか)を処理する

Eで共通接線を正しく求められていないことが発覚、代わって修正、通す

E (01:33:27) 1 wrong try

Fを3人で考える、シミュレーションの方針をまとめていざ実装

と思ったところでいい実装はないか考えてみることに

…船1つずついけばいいんじゃね?

……座標1100までの整数だわー

実装、サンプル通る、出す、WA…

嘘かなあと悲しんだが、ケアレスミスであったことが発覚し修正

F (02:21:39) 1 wrong try

残り30分で無理幾何なG…

中心決めれば半径決まりそうなので山登りしてみようということに

るーふさんに紙上幾何してもらいながら実装

サンプルが通るがWA

いろいろ直すがWA

終了 (03:00:00)

結果

まぐれで1位でした。

自分の速度や自分のWAがどうしようもないので本番頭が回らないと危ない…。

環境は整備しましょう。

幾何は整備しましょう。

2010/06/21 (Mon)

[]実プロ 2010.06.21. 20:46

F

何も考えずに構文解析からやり出すとかどうかしてた

しかもバグって途中交代した

E

まっちゃさんに一任

H

瞬殺

G

union-findだけ書いて任せた

I

幾何書くの遅い…

運良く一発で通ったが終了後では意味ないですね

2010/06/20 (Sun)

[]TCO 10 Round 1 13:46

某氏に書けと言われたのでネトゲプレイ日記をつける習慣を久しぶりに再開?

2000→850

Room

Room 22

赤3人は少ないと感じてしまう

250

問題文誤読してなぜかb→a方向しかできないことにしてあわわわわ

26文字全部チェックが安全なのでそれで

500

Stern-Brocotと勘違いして最後のYが小さい方が辞書順早いとか嘘いことを…

かなり時間がかかってしまった

1000

見るからに流すだけの瞬殺問題

ちょっと慎重に行き過ぎた気がする

Challenge

のんびり250を開けてたらたちまち部屋の500が落ちまくって焦る

とりあえず500のTLEを見つけ、その後TLE狙いでミス、r=1で落ちるのを見つけ、またTLE狙いミス

全部生成すると、string使うかどうか、とかがかかわる微妙なラインなんですね。テストしておくべきだった

System Test

通った

Result

244.22 + 396.45 + 856.45 + 50.00 = 1547.12

4位 (部屋1位)

32353303


1000は速度2位でしたがACRush先生に完敗orz

レートはキープ困難なところにまで来てしまいました。TCOでなるべく稼ぎたい

2010/03/17 (Wed)

[]SRM 464 16:30

writerをやっていました。いかがだったでしょうか?

Editorialを執筆中なので詳しい解説は後日そちらを参照してください。また Practice Room にofficialな解答を上げています。

以下に出題した5問について簡単なコメントを。

続きを読む

2010/03/13 (Sat)

[]TCHS10 Round 3 09:25

Room

Room 8

平和

250

書くだけ

550

実装ゲー

950

縦横全通り回せばよいが判定の書き方がすぐにわからなかったので縦決めてから計算した

Challenge

見つけられなかったので最後に適当に投げたら失敗した

System Test

通った

Result

232.43 + 269.45 + 695.44 - 25.00 = 1172.32

5位 (部屋1位)

TCHS: 21172162


割と時間が危なかったセット…、Finalどうなるんでしょう

2010/03/06 (Sat)

[]TCHS10 Round 2 09:11

Room

Room 10

平和

250

書くだけ

500

距離1ごとにBFSは状態のエンコーディングがめんどいとか勝手に思って適度に点増やした。これするくらいなら場合分けの方が速い…

1000 09:11

何も考えずに座標圧縮してみた。提出したあと見直したら植木算や演算子の優先順位がぼろぼろだったがうまいこと通りそうだったので放置

Challenge

intと未ソート。500でどう見ても変なのがあったが時間が足りずに焦ってミス。

System Test

うん

Result

248.63 + 432.70 + 808.92 + 75.00 = 1565.25

3位 (部屋1位)

TCHS: 20332117


TCHSで3位はOKな気がする

2010/03/02 (Tue)

[]SRM 463 09:17

Room

Room 4

赤・黄色多め

250

ソートして終わり

500

考え込みすぎた上に適当に書いたものを出したので再提出…

1000

互除法っぽいから木っぽい推移だろーとか考えて時間切れ

Challenge

あまりちゃんと読まずに500に3つ投げたら2つ成功した

System Test

通った。全体的によく通ってるなあ

Result

248.48 + 180.88 + 0.00 + 75.00 = 504.36

94位 (部屋4位)

30332958


しかたがない

2010/02/27 (Sat)

[]TCHS10 Round 1 09:04

今年も始まりました。オンラインで4ラウンド。

Room

Room 8

neal_wu部屋。おわた

500

冷静にswapするだけ

250

やるだけ

1000

冷静にDPするだけ

Challenge

ぱっと見でわかるものは全部持って行かれた

System Test

まあ

Result

245.81 + 485.31 + 892.09 + 0.00 = 1623.21

6位 (部屋2位)

TCHS: 20222039


3問とも一度はバグを埋め込んでいたのは酷い。

2010/02/18 (Thu)

[]SRM 462 19:08

Room

Room 17

赤少ないし青多いしおいしそう

250

なぜか整数の(1/整数)乗しかない、と思い込んで組み出してからそうでないサンプルの存在に気付き、大きく出遅れ。二分探索に書き換え。コーナーケースがいろいろありそうな気はしたが、1桁になるケースだけ場合分けしておいてあとは大丈夫ということにしてsubmit

450

期待値の線形性は偉いです

確率だけS回分計算しておくと楽かつ速いですね

しかしこれだけのコードに16分orz

1000

状態100*(辺の数)にしてBellman Fordっぽく

TLEが不安だったが大丈夫だろうということにして提出

Challenge

250でreturn -2にだけひたすら着目したら5つ落とせた

500で/(N-1)にだけひたすら着目したら2つ落とせた

自分の250は落とされた

System Test

450と1000は通った

250は1=1+xとかで解ありと判定したのが原因、大量の人がそれで落ちた模様

Result

0.00 + 349.57 + 625.01 + 350.00 = 1324.58

5位 (部屋1位)

29893033


こういう250は落ちるのはしょうがないですがTopCoderらしくて良いと思います。残り2問が難しめのときにやられると困りますが今回みたいなセットだと楽しいです。いやまあもっと注意力つけなさいって話ですけどね。

2010/02/14 (Sun)

[]SRM 461 19:08

Room

Room 2

普通

300

やるだけ

500

普通にDijkstraで通るはずと信じてsubmitしたがTLEorz

とりあえず適当な枝刈りつけてresubmitしておいた

950

サイズ40の時点でやることがわかるが組み終わらなかったorz

500よりこっちからやればよかったと後悔

Challenge

終点だけ離れているケースを作ってみたら自分のもTLEしたのでやけになって投げまくったら2成功4失敗で悲しいことに

System Test

もちろん500は落ちる

Result

265.41 + 0.00 + 0.00 + 0.00 = 265.41

93位 (部屋4位)

30642989


こんなんで一応2桁順位なのねえ。ひとまず3000さようなら。

500は結局定数倍悪い実装をしていたのが原因。ヒープ自前にしたら結構速くなった。状態50*2000でない解法をやったらもっと速かった。座標の上限増やせばよかったのにー、とは思いましたが500なので仕方ないのかな

2010/02/11 (Thu)

[]SRM 460 00:40

Room

Room 5

赤5人部屋、しかも名前が線対称なあの方と同室だったので撃墜辛いかなぁと予想

250

枝刈り探索が想定されているだろう、とは思ったものの、なぜか怖気づいてしまったため血迷った結果無駄に包除原理を駆使して計算した

500

見るからにDP

推移の計算適当にしすぎて合わなかったが適当に修正したらサンプル通ったので出した、最大ケースの確認を忘れてたしメモリも相当危なかった

1000

わかりません

Challenge

250で書き写してみたら偶然落とせた

System Test

通った

部屋残り全部通ってた

Result

221.31 + 376.19 + 0.00 + 50.00 = 647.50

6位 (部屋1位)

30243064


250で10^3のDPの発想はなかった……

Top10入りが見えてきた気がしなくもないです。

2010/01/20 (Wed)

[]SRM 459 15:22

Room

Room 22

普通。

250

-1/2から2001/2まで全部調べる

500

冷静に考えれば1次方程式自然数解数えるだけのDPなのに計算量が駄目なのを組んで時間ロス

1000

フローじゃね?と思ったがさっぱり

Challenge

250で X > 1000 で落とせた

System Test

通った

部屋で2つ250が落ちていた

Result

242.19 + 413.72 + 0.00 + 50.00 = 705.91

5位 (部屋1位)

29613024


ここ最近妙に好調だなあ、とか思っていたらいつの間にか3000超えてしまいました。不思議。


2009/09/27 (Sun)

[]GCJ 2009 Round 2 11:21

3000人→500人

A

焦って大変だった。てきとーな順にバブルソートするも無理

上からgreedyに取るだけだった

それを組んだのにsmallでWA出してどうしようもなかったorz

B

壊す範囲が連続区間であることを使えそうな気がしたがわからなかった

smallは状態O(RC4^C)の0-1BFSで通した

C

流すだけ

だけってほどでもないがやったことがあってよかった

D

答えについて二分探索

Result

A,C,DとB-smallが通って83点の13位


個人的難易度はC<D<<<A<<Bでした。B,C,Dを読んでBから組もうとしたのがミスだったorz

とりあえずたぶん通過。これがRound3だったらよかったです。

2009/09/24 (Thu)

[]SRM 449 03:46

23時以降に帰宅して急いで風呂に入ったりして参加。

Room

Room 12

平和そう。

250

一瞬計算量が不安になったが全然問題なくて全通り調べるだけ

950

漸化式書いたらカタランそのものだった

1000000122を素因数分解してみたら終わった

550

開けたとき残り25分あったが面倒なDPに見えて通せる気がしなかったのですぐ放置した

Challenge

1000で明らかに嘘をやっている人がいたが怖がっていたら先を越されたorz

250を適当に写したりしていたが何もできなかった

System Test

通った

950通す人が少ないなあ

Result

234.64 + 0.00 + 463.69 + 0.00 = 698.33

8位 (部屋1位)

27092793


順位は自己記録タイらしいがそこまでたくさんは上がらなかった。

Mediumとか無理です。


2009/09/22 (Tue)

[]The First KMCMonthly Contest 20:01

ICPC夏合宿の問題。5時間10問。

以下、通せたものは通した順に、自分がやったこととかです。

詳しい解説はwataさんのところ(http://d.hatena.ne.jp/wata_orz/20090922)とかを参照してください。


続きを読む

2009/09/13 (Sun)

[]GCJ 2009 Round 1B 03:48

1Aから1Cまでのどこかで1000位以内に入れば通過。

B

next_permutationするだけ

桁が増える場合の処理を適当にしすぎてWA×2orz

A

ただのやるだけ

C

それっぽい順番でBFSする

バグバグだったが終了直前に通した

もっと楽に組む方法あるかなあ

Result

全部通って100点中最下位の63位


自分の実装力も問題の感じもいろいろと残念でした。