A ただのDP コピペしたとこ一部直し忘れてWA×1orz B 小さい方は一点原点に固定して残り二点四乗ループで間に合う 大きい方はO(NM)の解法なら分かったけどテストケース1000個もあったら間に合う気がしなかったのでパス なんとx1y2-y1x2=Aにおいてx1=N,y1=1と…

初参加 A やるだけな問題 B ただのダイクストラ… なのに、問題文読み落としまくってWA×3orz これがさいたまトラップかー C ビットDP 最初グループ数決まってるの忘れてて2^18*18^2なら余裕だなと思っていたけど、グループ数入れたら2^18*18^3になってしまっ…

するらしい

250 てきとーにDPするだけ 245.78 500 問題文読解ゲーorz 読み間違えまくってめちゃ時間がかかった 219.80 1000 ふつーにDPしたら間に合わなそー 時間も少なかったので諦めた Challenge 250のn=1とlongあたりを見てたけど誰もミスってなかったorz 合計465.58…

A ソートして片方逆向けるだけ B フローじゃね？とか思ってずっと考えてたけど分からずorz ひとまず何も出さないのはさびしいので全探索でsmallを通した よく考えたら一つに絞られた人から順に使ってけば大丈夫なので、テキトーに実装してlargeもクリア C 数…

いきなり部屋のメンバーがとてもカオスでわらたｗ 250 i文字目まで作った時の最小コストをDPするだけ 239.19 500 内部に含まれるカットの数を数えててきとーに計算した 場合分け一切なしでいきなりサンプルが通ったけど、ちゃんと他のケースでテストしたらや…

SuffixArray Larsson-Sadakaneとかいう構築法とLCPの求め方などの基本的なとこを勉強した おかげでようやくこれが解けた Hopcroft-Karp 二部マッチング版Dinicみたいな感じ 予想以上の速さでここで頂点数辺数ともに100万くらいの二部マッチングが間に合った …

250 テキトーにやりすぎて撃墜されたorz 後から考えたら、各連結成分を完全グラフにすればいいだけだから、余ってる頂点を一番でかいとこにつなげれば良かったのかー Challenge Succeeded 500 使う可能性のあるのは端点だけだからO(n)個しかないのでO(n^3)の…

A てきとーにDPした B 各出発時刻について二つ頂点作って間に合うところに辺を引いて二部マッチング なんていう激しいことはしないで、てきとーにPriorityQueue使って貪欲に使った C 正方形と円の共通部分の面積をまじめに計算した 三問とも通って予選通過 …

暇だったからいろんなMaxFlowを隣接行列でてきとーに実装してみた あるごりずむのかいせつはちょーてきとーだから間違ってるかも 1)藤重さんのスケーリング使う版 1.辺の容量の最大値をaとする 2.始点から確実にa以上の流量が届く点を探索する 3.終点まで届…

250 なんか珍しく速く解けた 242.62 600 篩で配列外アクセスして再提出orz 今度からは全部最大値でやっておこう 283.60 900 全部の点について調べるだけじゃねと思ってやったら通らねー よくみたら e(w,x)=2*x/w*(w-x+1)/w とかやって真ん中のやつ二重にカウ…

６完３位で予選通過やったー しかし６完しないと予選通過できないとかひどすぎる以下当日の流れ

250 範囲外アクセスで再提出orz 195.48 500 できたと思ったら間違ってた 直してる途中で時間切れorz Challenge Succeeded 1000 開いたけど読んでない Challenge 500の非連結な場合忘れを落とそうと思ってたら、いきなり非連結な場合忘れてるぽいのを見つけた…

諸事情により２人で参加 システムが調子悪かったみたいでBでfailedして投げまくってたら４連続WAが返って来たorz DはTLEするし、EでもWA出すし、Fは意味不明だしで今回はボロボロだった ついに国内予選まで一週間を切ったのでとっととライブラリ完成させてPK…

250 メモ再帰すればいいものを、なぜかトポロジカルソートしてからループでやって時間がかかった しかも答えがlongなのをすっかり忘れてて再提出orz 181.30 500 3^12のメモ再帰 珍しくバグらずに一発でできた 458.83 1000 よく分らんけど流せばいいんじゃね…

なんと奇跡が起こって６完で１位 この調子で今年こそは国内予選突破できるといいなぁ 思えば去年は３問しか解けなかったので、この一年練習してきた甲斐があったと思う以下当日の流れ

なんかJavaの勉強をしていたら新しいショートコーディング技法を発見したｗ ひとまず1001で最短コード達成

250 C++にしようかと思ったけど、バグると嫌だったのでJavaで テキトーに再帰で順列生成した 228.04 500 どう考えてもTLEしそうだったので諦めた 1000 しばらく考えているうちに、距離が9まであることをすっかり忘れて、E+A+...+A^kを生成する行列使って二分…

東京大学競技プログラミングクラブの練習会に参加 今回はペアプロ重視でやってみた いきなりAがむずかったり、Bのひっかけに見事にはまったりしたけど、ほかの問題はそれほど詰まることなくいけて、時間内に全部解ききることができてよかった 終了後の議論の…

250 なんか問題文長い上にバグってやたらと時間がかかった "ba".split("a") は ["b"] なのに "ab".split("a") って ["", "b"] になるんだ 知らなくってはまったorz 190.48 500 なんかもうやけくそで、間に合うのか知らないけど同じ隣接行列になるまでループ…

ええぇぇえぇぇぇぇえぇぇぇ http://forums.topcoder.com/?module=Thread&threadID=616032 ええぇぇぇえぇぇぇぇぇぇぇえぇ「え」がゲシュタルト崩壊してきたｗ

東京大学競技プログラミングクラブの練習会に参加 新しいチームになって初のチーム戦で、なかなかうまいこといかなかったけど、とても勉強になった 今年は１台のパソコンを有効に使うために、始めの方の簡単な問題は１人ずつで挑んで、その間に難しい問題の…

これはひどいorz 250 テキトーにやるだけな問題 228.51 500 lower_boundが必要なC++ゲーorz Javaも1.6ならTreeSetで同じことができるのにTopCoderはまだ1.5orz さすがに平衡二分木を作るのは面倒なので、仕方ないから木が偏らないように最初に平衡な二分木を…

結果としては12問中9問解いて、３位 順位的にはまぁ満足だけど、解けなかった３問中２問は解けそうな問題だったので、解きたかったなぁ以下当日の流れ

orz 250 何桁かでループ→4か7かをビットで表現してループ っていう全探索をした 前回の教訓を生かして念入りにチェックしてから提出 243.84 500 行列のN乗求めるだけじゃん簡単〜 と思ってたら、配列の添え字間違えて再提出orz しかもそれもまた間違ってて落…

250 8^8が小さいような気がしてMapじゃなくて配列にメモした メモリ足りないことに提出してから気づいて再提出orz やる前はしっかりテストしてから提出しようと思ってたのに本番になるとついつい先に提出してしまう もうだめぽ 190.70 450 450のくせにコード…

たぶん今年の選抜ルール http://sparth.u-aizu.ac.jp/icpc2008/d_selection.php 同じ大学から３チームまでに戻ったみたい どう考えてもむりぽ＼(＾o＾)／

システムテストが終わってそのまま８位 Forumでトップの人の運転動画が載っていたので見てみたところ、華麗に急カーブを曲がっていた スゲーーー Kiwiが話しかけて解法を聞いた感じでは、通過する点について山登りをしたと言っていた気がしたけど(英語苦手な…

勝てねー 問題はレーシングゲームのＡＩを作れみたいな感じ ７時間の競技時間は運転免許を取得するには短すぎたようだ ひとまずテキトーにスリップとか完全無視で最短路通るようにするしかできなかった 途中からスリップしないように急カーブ対策を入れよう…

結果出てた 481.76 / 500 で２位をキープできて奇跡的にまだレートが上がった 2489 → 2578 しかしトップの iroriさんはexample見る限り、制限時間をたっぷり余してあのスコアを出しているみたいだからすごいなぁ 今回のマラソンで日本人がトップ５に３人も入…