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

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-05-08

Google Code Jam 2011 Qualification Round

| 12:32 | Google Code Jam 2011 Qualification Round - eomole as a contestant を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qualification Round - eomole as a contestant Google Code Jam 2011 Qualification Round - eomole as a contestant のブックマークコメント

初の満点でした。

A. Bot Trust

前から貪欲に決まります。

19m 01s

source code

B. Magicka

何回もなめないといけないかと思いましたが、読み直したらそんなことありませんでした。英語読解問題。combineが連鎖しないこともポイント。あと、出力形式が微妙ですが、JavaだとtoStringするだけです。

2h 00m 38s + 04m

source code

C. Candy Splitting

不完全な加算はxorをとるだけです。A^B=0 <=> A=B なので、合計が0でなければNO、それ以外はどう分割してもいいので最小値だけ譲ってあげることにします。Seanさん鬼畜ですね。

2h 36m 04s + 08m

source code

D. GoroSort

割とまともに漸化式立てて計算たので解説見て唖然としました。手計算を間違えていたので適切な仮説を立てられず残念です。自分の解答の前処理は雑に書いてあるのでもう少し速くなります。

4h 46m 57s

source code

まとめ

スピードアップしたいですね。漸化式力も向上させたいです。

あと卒論の成果は特に使えませんでした。。

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 が十分速く解けるように励みたいです。

2010-12-24

Member SRM 491 Div2

| 17:45 | Member SRM 491 Div2 - eomole as a contestant を含むブックマーク はてなブックマーク - Member SRM 491 Div2 - eomole as a contestant Member SRM 491 Div2 - eomole as a contestant のブックマークコメント

調子が悪かったのでゆったりと頭のマッサージをしました。

250

結局のところ、最初の1桁を0にせよという問題。ただし0に例外処理が必要ですが、親切にもサンプルに入っていますね。

source code

500

N,Kが与えられたとき、表裏の和がk(k>=K)となるように、互いに異なる[1,...,N]の数字をサイコロに割り当てる方法は幾つありますかという問題。3つの数字を決めれば残りも決まるのでそれだけ試せばOK。N^3*(2N-K)くらい。同じ組み合わせでも、鏡像で2種類あることに注意、と言っても親切なサンプルから推測可能ですね。

source code

1000

{ x | left[i] <= x <= right[i], x % damage[i] == 0}の和集合のサイズを求める問題。区間に分けて小さい方から走査すればいいですね。各区間内では包除原理を使いました。

source code

今日のミス

題意勘違い例外忘れ境界設定ミスオーバーフロー
250 ×
500×
1000× ××