2008-01-01から1年間の記事一覧
1月 赤くなった MarathonMatch初挑戦 2月 OBOG会の冬合宿でふるぼっこにされた 3月 TCOのAlgorithm部門敗退orz でもMarathonで通ったｗ 4月 きたまさがPKUにはまった 5月 TCOで惨敗 きたまさがTopCoderにはまった 6月 HITORI++結成 UTPC3位&模擬国内1位 黄色…
またしても奇跡が起こった 13:00 開始 きたまさがＤをそっこーで通した。 自分がＣをそっこーで通す、つもりがバグったorz とっとと印刷してきたまさと交代 きたまさがＥを組み始めた バグが見つかったのでＣを修正して通した 14:00 きたまさがEサンプル通ら…
うぉぉぉぉぉー 奇跡が起こったｗ 250 xの0のビットのところにkを入れればいいだけ 243.37 500 maxPartnersが3以下なので、ペアの個数について4^NのDPをすればいい 同じペアを複数作らないように注意 300.72 1000 36人以下なので、半分に割って18人ずつで考…
賞金付きだったのでついつい参加してしまったN+M次元のデータがU個あり、それにガウス分布のノイズがかかったものが与えられるから、N次元分のノイズのかかっていないデータから、残りのM次元のデータを推測せよ、という問題 U個のデータは別に生成されたC個…
250 やるだけ 241.11 500 KMCoderでほぼ同じ感じの問題が過去に出てる フロイドっぽく三乗回すだけ 438.90 1000 可能かどうか調べるだけならB優先で貪欲に使えばよいので、O(n^2) あとはＡを置いて可能か調べ、だめならＢとすればよいのでO(n^4)で解ける な…
250 next_permutationすればいいのに、わざわざ再帰したらなんかバグって時間かかったorzもうだめぽ 221.14 500 最初計算でがんばってたらなんかどっかで勘違いしてわけわかんなくなって、行列でいけるじゃんってなったから方針転換 どっかで覚えた[ [A,I], …
250 やるだけ問題 222.77 500 三分探索するだけなのになぜかいろいろめんどくさいことしたら、誤差死したorz Failed System Test 1000 てきとーにやったら撃墜されたorz あとで単体法で出したら通ったｗｗ Challenge Succeeded Challenge 500でt -50.0 合計1…
A ひとまずsmallは全部試すだけだったのでとりあえず出すかと思ったら、なぜかEclipse上で実行できない… どうやらJREのデフォルト設定がおかしいっぽく、設定し直したりして無駄に時間を食ってしまったorz プラクティス中にちゃんと試しておくべきだったorz …
250 全部試すだけ 240.39 500 ただの探索…なのに添え字ミスって再提出orz 321.62 1000 むりげー Challenge 1000が1つ出てたからPetrが苦しむ問題解けるはずないの理論により、ブラインド撃墜したら成功したｗ +50.00 合計612.01の38位 2639 → 2655 なんとか…
前回出れなかったから久しぶりのSRM 250 9から貪欲に使ってくだけ 一瞬６が大丈夫か不安になったがとりあえず提出 ちょっと考えたら問題ないことが分かったのでよかった 247.92 600 力と知の値で二次元DPするだけ 最悪1000^3かかりそうな気がしてオーダー下…
なんと、奇跡が起こって優勝してしまったｗ KMCoderの成果だー なぜか問題文が一部しかなくって手元にない上に、ソースファイルもないので記憶を辿りに書いたから間違ってるかもｗｗ A やるだけな問題 開始後数分間Eclipseとキーの設定をしてから解き始めた…
SRM後で超絶眠くて序盤からひどかったorz A 素因数列挙なのになぜか素数を列挙し始めたおれはもうだめぽorz B 問題文読みちがえ＋バグで延々とはまり続けたorz C 珍しくそこまではまらなかった D なぜか添え字ミスってバグってたのに通ったｗ E めちゃくちゃ…
250 包除原理 243.63 500 3^nのDPかと思いきや、ループができるのでダイクストラした いつもどおり頂点クラス作って辺を張って一気にダイクストラってやって提出したら、なぜかTLEしてたorz 仕方ないので、頂点クラスをやめて書き直して再提出orz 209.41 100…
250 ただの二分探索 236.50 500 ただの貪欲 370.58 1000 てきとーにやったらサンプルが一つとおらなかったorz Challenge 怪しいの見つけたからランダム投げたら成功した オーバーフローしてるのも見つけてもう一つ成功w +100.00 合計707.08の6位 2405 → 2522…
250 やるだけ 最悪何回ループが回るかって考えても、少なくとも50の分割数(20万くらい)以下なので余裕で間に合う 225.02 500 てきとーにDPするだけ 470.48 1000 どうせ上限決めてそれ以下になるまでは一番でかいの使うとかはだめなんだろ〜なと思い、解くの…
250 やるだけ 239.95 500 残りn個の状態で誰が勝てるかをDPしていけばいい 自分しか勝てる可能性がなくても、ゲームに引き分けが存在するため必ず自分が勝てるというわけではないことをすっかり忘れていて、システムテストで落ちたorz Failed System Test 10…
A 全ての鳥を含む最小の長方形を求めて、その中に入っていれば鳥で確定 そうでない場合は長方形をその点を含むように拡大した時に鳥でない点が含まれたなら、鳥でないことが確定 残りはUnknown smallもlargeも同じ D smallは大きい方のどの頂点が小さい方の…
250 全部試すだけ 237.20 500 グラフが直線と鎖になるので鎖はどっか一か所切って直線にしてあとはフツーにDPするだけ なんだけど、なぜか最初一部のループ除いて二部グラフだから、ループ一か所切って二部グラフにしてあとは最大安定集合求めればいいやーと…
しゅーりょー 疲れたー やはり東大の他のチームはめちゃ強かった 二日目 序盤は何か全然バグらず奇跡の６連続アクセプトしたのに、その後探索で詰まってしまって、バグがいっこうに取れず、結局８問しか解けなかったorz 探索のバグは途中で方針を変えて一か…
250 やるだけな問題 222.69 500 展開図ムズイー てきとーにやったらシステムテストで落ちたorz なるほど、さいころ転がしながら実際に番号振ってみればよかったのか Failed System Test 1000 わかんね Challenge 500で場合分けで解いてる人発見して、一つ忘…
1. 根以外の全ての点について、入ってくる辺のコストの最小値を求め、その値をコストから引く 2. 入ってくる辺がない点が存在したら、有向木は存在しないのでそこで終了 3. コスト0の辺のみからなるグラフ上で強連結成分を計算し、それらを一つにまとめる 4.…
250 ビットコンビネーション列挙のライブラリを使った 238.64 500 6M-21以下の数を6個に分割する分割数に帰着できるからあとはDPするだけ 367.77 1000 実装ゲー ルール理解するのに時間がかかった しかもどっかでバグったor理解が間違ったせいで答えが合わな…
結果が出てた テスト1000個という少なさに救われて？なんかPsyhoと同率１位ｗｗ さすがに同率解消のため小数点以下もう一桁使うとかいうことにはならないよね もしそうなったら負けそうだｗ まぁとにかく賞金たっぷりゲットだー ひゃっほい プログラミングの…
なんかトップのPsyhoが自分とほとんど同じことをしていたｗｗ 90%の時間を圧縮に費やし、最適な圧縮を山登りで探索し、あまったスペースに元の文章丸ごと１つ埋め込んだというとこまで全く一緒。 しかも圧縮で、直接ハフマンするんじゃなしにビットをグルー…
賞金付きな上に車校が仮免試験結果待ちで週末なかったので久しぶりにマラソン参戦 今回は暗号を解読しろっていう問題 コーディングフェイズが終了した段階で同率２位 点数は99.98だけどローカルで１万個実行して9999.44だったからもうちょい上がるはず… まぁ…
マラソンのしすぎで眠かったけど参加 250 やるだけな問題 234.58 500 ただのナップサック問題…だけどサイズでかすぎて間に合わねー 適度に枝狩りを入れて組んでみたけど自分で撃墜できたorz 1000 開いたけど難しそうだったからあまり考えてない Challenge 25…
250 全部の時間調べるだけ 236.56 500 後ろに∞をくっつけて、一番小さい文字列をとってきてその一文字目を使うっていうのを繰り返すだけ 438.57 1000 謎 Challenge みんなソースコードが短かったから、自分のとパッと見違う解法のを探してきてがんばって書き…
A マップのサイズの配列用意して通った道記憶して縦方向と横方向から眺めればいい メモリがやばいことになったけど気にせずヒープサイズ増やして強行突破 B ただの探索ゲー 奇跡のバグ0で動いてすんなり終了 C どう見ても二部グラフの安定集合 おいしく頂い…
GCJ Round2のCがもろ単体法一発な問題だったのでやっぱり単体法は必要だと思い、ちゃんと勉強して組んでみた 改訂の方は０要素圧縮しないと速くなる気がしなかったのでやめてふつーの不等式形の単体法を組んだ C問題で使うとなると行列のサイズが8000×4くら…
思いっきり寝坊したorzorzorz
