2011-05-15
TCO 2011 Qualification Round 1A
SRM | | 
UTPCの懇親会に参加していた関係で飲酒コーディングになってしまいますが、通ればよかったし、Div2相当だと予想したので参加してしまいました。
250
酒で問題よく覚えていない。最初ソートして判定しようかと思ったが、この状態で場合分けがちゃんとできるわけなかったので、決め打ちして条件を満たすか調べる方に書き直していたら無駄に時間がかかった。ような気がする。
204.70
500
酒で問題よく覚えていない。曲の切り替わる時間をDPで前処理して、それらを適当に加算した。ような気がする。
432.36
1000
酒で問題よく覚えていない。場合分け色々しないといけなかったっぽいが、この状態では無理だった。ような気がする。
Opened.
Challenge Phase
酒でプログラム読めなかった。。
結果
637.06 で 156位になりました。1820 -> 1863 で 1000 解けなかったのにレート上がって不思議。別に大丈夫かと思って出てしまったけれども、明らかにいろいろなスキルが下がってひどかったです。次のラウンドからはきちんと万全の体調で出ます。
2011-05-08
Google Code Jam 2011 Qualification Round
Other | | 
初の満点でした。
A. Bot Trust
前から貪欲に決まります。
19m 01s
B. Magicka
何回もなめないといけないかと思いましたが、読み直したらそんなことありませんでした。英語読解問題。combineが連鎖しないこともポイント。あと、出力形式が微妙ですが、JavaだとtoStringするだけです。
2h 00m 38s + 04m
C. Candy Splitting
不完全な加算はxorをとるだけです。A^B=0 <=> A=B なので、合計が0でなければNO、それ以外はどう分割してもいいので最小値だけ譲ってあげることにします。Seanさん鬼畜ですね。
2h 36m 04s + 08m
D. GoroSort
割とまともに漸化式立てて計算たので解説見て唖然としました。手計算を間違えていたので適切な仮説を立てられず残念です。自分の解答の前処理は雑に書いてあるのでもう少し速くなります。
4h 46m 57s
まとめ
スピードアップしたいですね。漸化式力も向上させたいです。
あと卒論の成果は特に使えませんでした。。
2011-02-11
SRM 497 Div1
SRM | | 
赤ブルの濫用で弱ってますが、起きたときにはまだ10時だったので参加できました。
250
増加、減少の情報から順列を再構築する問題。部分列に対する解を利用して1つずつ伸ばしていく方法をとった。今思うと後ろからやった意味ってあったのだろうか。
193.45
550
構文解析+αの問題。再帰降下で愚直に書いたあとに前処理を書き足したり、うっかり Greedy にできると思ってしまったりで手間取っている間に時間終了。。にしても、最初に concat が必要って仕様、どうにかならないんだろうか。
Opened.
1000
読んでる暇なかった。部屋で出してる人なし。
Unopened.
Challenge Phase
Twitterで知っている人をせっかくなので落としてあげたいと思ったけど、長くて断念。結局何もせず。ちなみにその解答はテストに通った模様。
結果
193.45 で 190位になりました。1630 -> 1672 でレートが収束気味です。卒論ももうすぐ終わるので、Medium が十分速く解けるように励みたいです。
2010-12-24
Member SRM 491 Div2
SRM Practice | | 
調子が悪かったのでゆったりと頭のマッサージをしました。
250
結局のところ、最初の1桁を0にせよという問題。ただし0に例外処理が必要ですが、親切にもサンプルに入っていますね。
500
N,Kが与えられたとき、表裏の和がk(k>=K)となるように、互いに異なる[1,...,N]の数字をサイコロに割り当てる方法は幾つありますかという問題。3つの数字を決めれば残りも決まるのでそれだけ試せばOK。N^3*(2N-K)くらい。同じ組み合わせでも、鏡像で2種類あることに注意、と言っても親切なサンプルから推測可能ですね。
1000
{ x | left[i] <= x <= right[i], x % damage[i] == 0}の和集合のサイズを求める問題。区間に分けて小さい方から走査すればいいですね。各区間内では包除原理を使いました。
今日のミス
| 題意勘違い | 例外忘れ | 境界設定ミス | オーバーフロー | |
| 250 | × | |||
| 500 | × | |||
| 1000 | × | × | × |