PKUの解いた問題数がちょうど700問目になった。 700問目の2112 Optimal Milkingは頂点数がK+C個の重みつき無向グラフが与えられて、1..Kの頂点にミルクマシンが置いてあり、K+1..K+Cの頂点に牛が1匹ずついるときに各牛がミルクマシンに配置させるときに最も…

アクセスしたらちょうど始まったところだったので参加． 結果は7問全てacceptで5位．ただ一発で通ったのが4つなのでTopCoderだと3問は落してる．ただD以外はもう少しtest caseが入ってくるので間違いには気づいたと思う． 解いた順番はC->E->F->A->B->G->D P…

PKUでFortranが使えるようにいつのまにかなってた．

時間，空間計算量が小さいアルゴリズムがあるならそっちを使いましょう． 複数ケースがある場合は配列をとったときにGCが間に合わない時があるのでSystem.gc()を呼ぶ．このばあいTLEになる可能性があるのでその辺はヒューリスティックに． Inputが大きいとき…

各単語をエッジと考えたグラフでオイラーパスが存在するかどうか調べる．SPOJの方にも同じ問題がある．こっちはRubyで通したかったのだけど，入力を読んで初めの文字と終わりの文字をとってくるだけでTLEになるので保留．

Time Limit 5000ms のところを14218msで通すのはどうかと思う.片側探索では通らないので両側からbfsする.ただし，終了状態のほうが状態数が多い(2^8)ので前側からの探索手数を多めに取って，後ろ側は10手ぐらいしか読まない.

http://acm.pku.edu.cn/JudgeOnline/problem?id=2631 与えられた重みつきグラフの直径を求めよという問題．ただし，グラフは木である．なお，グラフの直径とはグラフの任意の点対の最短距離の中の最も大きい値のことをいう．Floyd-Warshallとかは計算量的に…

今日解いた問題はhttp://acm.pku.edu.cn/JudgeOnline/problem?id=24111×2のタイルでh×w(h,w再帰的に全探索する．ただし，h段目を埋めるときにはh-1段目のタイルの形状だけに注目すればよいので，メモ化が効いてmax(h,w)*(2^min(h,w))ぐらいの記憶領域を用い…

ゼミが休みになったので少し解く．とりあえず順位をひとつあげる．とりあえず100位と34問差があるので当分2ページ目には載れそうだが，あと100解いてもまだ2ページ目なんだよな．解いた問題は以上 http://acm.pku.edu.cn/JudgeOnline/problem?id=3117 http:/…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3193java補正がかかるので，単にソートして二分探索するだけ．以下ソース

今日解いた問題は以下の通り， http://acm.pku.edu.cn/JudgeOnline/problem?id=3181 http://acm.pku.edu.cn/JudgeOnline/problem?id=3192 他の作業をしているので今日はあんまりやっていない以下ソース

TopCoderの方で詰まったので気分転換にPku JudgeOnlineの方に移る．こっちはときやすそうな問題を選んで解いていったのですんなりいった． 解いた問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=3173 http://acm.pku.edu.cn/JudgeOnline/problem?id=317…