Hatena::Grouptopcoder

shinichiro_hの日記

2009-09-12

Code Jam Round 1B

03:46

今回は社員枠がひっそりとあるらしいのでひっそりと参加。

Decision Tree

Small/Large: OK

適当に。 S 式パーサ欲しいから LISP 系…とか一瞬考えたけどまぁいいやと C++ で。解けた。問題読むのと S 式パーサ書いてる感じで時間がほぼ終わった。 lexical_cast くらいは使えばいいよなぁと思った。

The Next Number

Small: OK (4 wrong try), Large: wrong

問題を壮大に勘違いするのを繰り返す。実は next_permutation すればほぼ終わる問題だった。 Small 解けるのを先に書いといたら良かったなぁ。あとブラウザのキャッシュだかなんだか知らんけど正答に達してからも Incorrect って言われて、問題の間違った解釈とかも繰り返した。間違った解釈する前のバージョンに戻して出力ファイル名変えたら通った。

Large 通ってないっぽい。あるえー。ぎゃーこれ入力 long long より多いのかー。くだらねー。

Square Math

Small: OK, Large: TLE

適当に書いても Small は通るだろうと適当に幅優先探索を書く。適当に通った。でも Large はムリだろうなーと適当に最適化を考える。

あんま思いつかんかったのと Small の雰囲気的に結構 Large 通っちゃうかも…とか期待して Large 開けてみる。うーん進むけど時間足りない感があるなぁ…ということで困る。

2つ思いついたのは、 test case 一個の中で、一回一回たどるのをやり直すんじゃなくて、まとめてやっちゃえばいいじゃんねー(当たりまえじゃーん)というのと、 +9+9+9+... みたいなの多いんだから、 +9 連打モードに入れそうなら適当に処理とかいうの。

後者エンバグしそうだったので前者。しかし 8 分では実装がムリだったー。

結果できた物体100秒で終わってたのでまぁできてたんじゃないかなぁ。メモリがどっか漏れてるぽいのでメモリ使用が 100% 近く行くひどいありさまだった。

感想

換算すると1102位の位置。ダメだにゃー。 37 度という微熱は言い訳としては弱い。

メモリ解放とかめんどくさいので、 test case を分割しておいて各問題をプロセスにふるものを作れば良いと思った。ついでにプロセス複数使うようにすれば高速化もできるしねー。

JakaJaka2012/11/15 07:06At last some rationality in our litlte debate.

oaypsboaypsb2012/11/17 05:04xdPQ2B , [url=http://bpclalakwown.com/]bpclalakwown[/url], [link=http://loojoessjexf.com/]loojoessjexf[/link], http://wksvvcgpmdxy.com/

cfptljzcfptljz2012/11/17 12:065NZtUT <a href="http://kfwjguyrpkfs.com/">kfwjguyrpkfs</a>

mtwncbsmtwncbs2012/11/17 21:389zcv04 , [url=http://ckppsqftnjzz.com/]ckppsqftnjzz[/url], [link=http://qpawkcbmiqie.com/]qpawkcbmiqie[/link], http://nbfcxnauvgfm.com/

2009-08-08

SRM 446

04:23

235.92 + 50 - 25 。102位。 1713 => 1814 。あまりうまくやれた気はしないけどレートは結構増えた。

250 は…これでいいのっていうくらいあっさり解ける。 235.92 てん。

500 は…直前に msiroさんの動的計画法の解説 を斜め読みしてたので、これはまぁ DP なんやろねと実装開始。

でも DP ってイマイチ苦手感があるなぁという感じで実装終了。でも 10^9 とか終わらないなぁと思う。

まぁなんかしらんけど 20000 秒くらいを一気にやる感じでいいかなぁとか思ってやってみる。はじっこがそれでいいのかよくわからんので適当に最初と最後の20000の端数部分は細かく計算できる感じの実装気分で。

なんか全然おかしい…おかしい…と思ってるうちに終了。多次元配列のインデックスの順番がすごいおかしかった。アホかーと思ったけど、まぁそれにしてもかなり時間足りない感じだったので、この問題でこんだけ時間使いすぎるのはまずいんだろうなあという。

終わってから修正してもなんかバグっている。ダメダメだなぁ。

gusさんの解答が短くて綺麗だなぁ。そうか同じ位置に移動できることにしちゃえばラクに計算できるんだな…

チャレンジは、なんか複雑な if 文連打の子が何人かいて、そのへんはまぁ間違ってるだろーと適当に眺めてたら、特定の条件で移動しても位置変わらんだろうコレっていう子がいたので、適当にチャレンジ。失敗。その位置が変わらない移動は、赤→赤の移動だったので、バグっててもうまくいってしまうのだった…泣きながら W を一個足して expected=GREEN but actual=RED 的な感じにして落とす。

他にもなんかあるだろうなーと適当に探すけどあまり見つからず。やる気無くなって 500 考えてた。なんか終わってみると赤い子が 250 落としてた。うーん赤い子の 250 とか見てもいなかったよ。

2009-07-23

SRM445

02:01

まず開始前に contestapplet.conf を復元しておく。これが無ければ前回同様2問目間に合わなかったんじゃないかなあ。

2問時間ギリギリで解いて60位。なんか結構むずかしめの問題だったのかなあと思うに大健闘という感じかな。あと challenge しようとしてた子はやはり落ちてた。

275: 最初にうーんこれメッシュに切って…とか思ったら example に .5 がついてるのがあって諦めた。 50C25 は計算できない、できない、できない…とか考えてた。グリーディに近いのから取ってくのは…だめだなあとかなんとか。途中で気付いてたんだけど、解答に小数点があるとしても必ず .5 なので、0.5 でメッシュに切ってきゃ終わりだった。もっと早く気付けてしかるべきだったかなあ。なんか思考がループに陥るのはよくないなあ。

550: LL って書き忘れるな…忘れるな…忘れるな…とか思いながらやっていた。 define 1 1LL とかしたろうか。一番上のケタが 1 か 0 かは簡単に確定して、えーとその下はどうなるのかなぁ…と思って、要は前のケタの最終値に1くっつけたものと前のケタの k-2**(n-1)-1 までで一番大きかったものの最大値を求められればいいんだなぁと思った。一番大きかった方は単に再帰してやれば良くて、前のケタの最終値は同じ関数で再帰してたけど、うーんこれは絶対おかしいなぁそうか最大値じゃなくて特定の位置の値だしなあと特定の位置を求める関数を書いた。そっちもまあ、一番上のケタはさっさと確定するので、1 くっつける場合に似たような再帰をしてやれば OK 。あとは k が -1 とかになるとかなしいので、剰余取る感じで。

今見るとこれ k=2**(n-1) の時にバグみたいなものがあるけどたまたまうまくいくようになってるなぁ。ラッキーです。

レートは1713とかになった。増えた。やった!

SRM444 250

03:32

445 の開始前に少しだけやってみて、結構時間がかかって終わらなかったのだけど、一応終わらせておくかなぁとやってみた。

そこらじゅうバグバグで、ひどいものだったけど一応正解した。特にひどかったのは、三角形を埋める場所は三角形の始点を決めちゃえば貪欲に取ってきゃいいのに、メモ化再帰とかして埋める場所について全ての組み合わせを調べていたことだった。なんか SRM って最初の20分くらい明らかに頭にぶかったりするから、軽くウォーミングアップしてからやるようにしたらいいのかもなぁ。

2009-04-19

SRM438

02:50

300の名に恥じず、解き終わっても解けてる気がしない300と、同じ時間あればこっち解けたんじゃないかなぁと思う500と。

まぁむずかしかったおかげで300ゆっくり解いただけの121.86で129位。まぁ眠かったし良しとしよう。

てかいつも思うけど TopCoder はすごい強い子向けにチューンされすぎだよなぁ。今回の部屋は 300 通ったのが 5 人だけで 500 以上は一人も通ってないよ。

チャレンジは休憩時間中にくやしくて500いじってたのでスタートダッシュが悪すぎて、全くチャレンジできず。300一人くらいは落とせたよなぁ。

MuneebaliMuneebali2012/11/14 18:00You've really hpeled me understand the issues. Thanks.

kszfblqsxkszfblqsx2012/11/15 12:12e0OOuy <a href="http://glyeeyjkotmi.com/">glyeeyjkotmi</a>

hgylfpxhgylfpx2012/11/17 20:55yNjrrq , [url=http://htlhxwvlkoxa.com/]htlhxwvlkoxa[/url], [link=http://bnnogpypnhxb.com/]bnnogpypnhxb[/link], http://ewzmqcbaubbc.com/

2009-03-25

TCO Marathon Round 1

23:50

300位でいいんだろーと適当にやって261位。どっちかというと hack the cell 優先するかなぁとかいう感じで。ところが50人シードとかいう話らしく、なんか落ちた。マラソンなら Round 3 くらいまでは行けてもおかしかないと思うんだけどなあ…ざんねん。

問題は等高線から高さを推定せよ、但し何回か測地することができます、とかで、適当に等高線の上で測地してその間を xy 軸に平行な向きで適当に線型補完して、ガウシアンかけてぼんやりさせて終わりとかいう適当な感じ。線型補完じゃなくてスプラインにしたら余裕だったと思うんだよな。

PaopaoPaopao2012/11/14 16:46I'm really into it, thnkas for this great stuff!

uxpzwmjqguxpzwmjqg2012/11/15 11:58K2lDVM <a href="http://elpeplmkozha.com/">elpeplmkozha</a>

uhvxagpuhvxagp2012/11/16 10:20W0T402 , [url=http://xkdxhfqjphvy.com/]xkdxhfqjphvy[/url], [link=http://rbxvxphsbprq.com/]rbxvxphsbprq[/link], http://ntzaensbnhio.com/

rvgfcyvznrvgfcyvzn2012/11/17 00:462OscWO <a href="http://xtlzqsswwgwc.com/">xtlzqsswwgwc</a>

wsdsaecadwsdsaecad2012/11/17 20:40S8O1ul , [url=http://ecmypskdamxb.com/]ecmypskdamxb[/url], [link=http://gqotroyqmamj.com/]gqotroyqmamj[/link], http://bjxunmstheff.com/