Algorithm
昨日予選の反省会をやって,Dのアルゴリズムについてよく考えてるうちに,グリーディなやり方で上手くいくことが分かった気がした.普通のダイクストラだと,常に最小距離の点しか訪問していかないんだから,結果として最小距離しか出てこないに決まってる.…
やばい.瞬殺だった・・・.10!通りあるのはあるわけだけど,実際にはある2つの汚れたタイル間の距離は一回計算すればいいわけだから,めちゃめちゃ早い.そんなことにも気づかなかったなんて.30分くらいでコーディングできたし,恐らく合ってる.んー.解…
今書いてみたら動いてる.なぜ本番でこれが出来ないんだ・・・.結局デバッグか.確かにそこは甘かった.動いているといっても,それは文字通りなので,合ってるかどうかは分からないけど.アルゴリズムはダイクストラに極めて近いので,かなり怪しい.ダイ…
ものもらいが出来てたためテンションが低かった昨日に続き,今日もものもらいが完全に治ったわけではないものの,昨日の予選の様子を.心地良い緊張感の中でコンテストはスタート.とりあえず全問印刷してAに目を通すと,やばそうな気配.Aを置いておいて他…
結果は微妙・・・.3問解いて1時間あまってたからもう1問解けると思ったんだけどなぁ.やっぱり練習不足な感じでした.とりあえずアジア予選には行けるみたいなんで頑張ります.
あぁなんてこったい.先頭行のパターン生成・・・もう二度と忘れるなよオレ.
combatさんのとこで解法発見.http://d.hatena.ne.jp/tanakh/20050619コピーか・・・.確かに.こういうとこがオレはバカだなぁとすごい思うところです.バカ正直にやることないのに・・・.今日の教訓としては,Fだからってびびるなってことかな.びびって…
今終了.久々の緊張感が心地よかったです.問題はこちらから.http://icpc-mock.ipl.t.u-tokyo.ac.jp/contest/problems.htmlAからCまではサクサク解けると思ってたけど,1人でやってたこともあってしょうもないミスを連発してたorz.やっぱりペアプログラミ…
やっと分かったー.なるほどね.フローネットワークはこう扱うのねん.この調子で2部グラフの最大マッチングもいくぞ!
820がフォード・フルカーソンで解けた.どうして10330はダメなんだろうか・・・.適当なテストケースは全部通ったんだけど,もっとアナーキーな入力があるかもしれない.一応今のアルゴリズムをライブラリに登録.プログラムのライブラリを作るのに,uvaはも…
完成しない・・・.どこがおかしいんだろうか.最小カット最大フロー定理って直感で分かりそうでよく分かってないのかもしれん.一日が34時間くらいあればなぁ.まだ勉強してたいけど明日朝早いから寝ないと.
ベクトルと行列か.どっちもないがしろにしてきた報いが今.
凡ミスが多すぎる.落ち着いてやらないと.
炎狐も直ったことだし,uvaでも思ったら.んー,wrong answer連発.難しくないと思うんだけどなぁ.やっぱり幾何が苦手だ.ちょっとデバッグに集中.
http://acmicpc-live-archive.uva.es/nuevoportal/data/p3083.pdfそのままやればおk.難しい問題が解けないと,簡単な問題に手を伸ばす癖が・・・.
ん.やっぱりこれ全探索かな.あーだめだもう.頭が痛い.
http://acmicpc-live-archive.uva.es/nuevoportal/data/p2816.pdf幅優先探索.BFSでこういう問題もありかぁ.後輩に教えてやろう.
http://acmicpc-live-archive.uva.es/nuevoportal/data/p2815.pdf動的計画法で.一発acceptのはずだったのに.くそったれー!by stance punks.
ハンガリアンメソッドを実装.全部で300行になってしまった.サンプルといくつかのテストケースは通ったので,たぶん合ってる.もっと効率の良いコーディング方法があるはずだけどなぁ.どこにもプログラムがないから泣きそうですよ.世界大会かぁ.きついっ…
ハンガリー法.印刷して読むしかない.
こっちはid:tanakhさんによる,World Finalの問題の解説.さすが,知識と実力が違いすぎますorz.マジで頑張らなきゃ.あーでも英語も・・・.Aはやっぱり難しいみたいですね.tanakhさんも捨てたみたいです.Bはグラフを作るのがなぁ.どうやるんでしょうか…
幅優先探索だよなー.めっちゃ遅い.サンプルは通るけど,n=10だともう動かない.インタラクティブに探索しようとしても上手くいかない・・・.勉強しなくちゃ.
問題は,またもや携帯絡み.携帯の電波塔の建設計画と,各電波塔のカバーできる顧客数が与えられ,その中からm個の塔を実際に建設するとき,どのような組み合わせで建てれば一番多く顧客をカバーできるかという問題.これはDPでできる.1つの塔を選んだ場合…
幾何問題.幅の高さの分かってるビルがいくつか与えられて,あるビルのある部屋に太陽の光が当たるのは何時から何時までかを求める.部屋太陽の光が当たるということは,部屋の片側全てに太陽の光が当たるか,もしくは部屋の真上に太陽があることと定義され…
カードシャッフルの問題.カードを上下で半分に分けて,両手でばらばらとシャッフルする.その際に,正確に左手と右手から交互にカードを置かないとならないのだけれど,1回だけミスる可能性がある.シャッフルを何度か繰り返した後のカードの列が与えられて…
combatさんのとこは,D,E,Jを解いたみたい.問題を見てみようっと.ついでに,A問題は誰も解いていない・・・((;゜Д゜)ガクガクブルブル
人が町から町へと携帯を持って移動するとき,その携帯の通信エリアの変更が最も少なくなるようなルートを求める問題.通信エリアは電波塔で一意に定まり,ある地点から最も近い電波塔がその地点の通信をカバーする.ルートは全て線分.幾何+グラフってやつで…
入力として2つの図A,Bが与えられて,Aの拡大縮小したものがBに含まれるかを判定する問題.図は,水平か垂直である線分の集合.拡大縮小があり得るから,線分を,それが含まれる図とその端点の関係を抽象化した情報で表現しなければならない.基準点を決める…
もう書きましたけど.米国発の記事だから,内容が面白い.日本のニュースではやってないのかなぁ.
面白そうだったのでアマゾンにて注文.ワクワク.