32bit版Windowsの一つのプロセスは2GBまでしかメモリを確保できないという制限が厳しくてUbuntu10.04の64bit版を使うことにした。32bit版のことしか考えてないのか、ちょっとめんどかったけど動いたのでメモとしてどうやれば動くのかを書いておく。64bitに対…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1023&lang=jp 問題 略 解法 平面走査を行う。 各点のイベントとしてx-2*rの位置にinイベント、x+2*rの位置にoutイベントを挿入してx座標でソートしておく。 イベントが起こるとy座標で…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3043 問題 H*Wのグリッド上に文字が書かれている。グリッドの上では左と下には行けず、右や上の方にいく場合は何マスでもジャンプできる。このグリッド上で辞書に載っている単語を作るパスは何通りあるか？ 1 …

http://acm.pku.edu.cn/JudgeOnline/problem?id=3042 問題 直線上に牧草がN個ある。それぞれの牧草を食べるまでの時間の和を最小化したい。自分の初期位置がLの時、最小値はいくらか？ 1 1 解法 メモ化再帰で解く。 calc(dir, left, right)は左側はleftまで…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3046 問題 T種類の数値がそれぞれNi個存在する。それらの数値を使って大きさS〜Bの集合を作りたい。何種類の集合の作り方が存在するか？ 1 1 解法 DPで解く。 DP[i][j]はi種類目の数値までを使って大きさjの集…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3650 問題 タグの付いた空欄が存在する2つの文章がある。2つの文章が同じかどうか判定し、同じ場合はそれぞれの空欄にはどんな文字を入れればいいか答えよ。 解法 2つの文章とタグを見て…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3649 問題 幅w,高さhのグリッド上に車がN台存在する。消防車が通るための道を空けたいのだが、どういう順序で車を動かせばいいか？ ただし、車を動かす時は必ずグリッドの外まで動かさな…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3648 問題 トラップが仕掛けられた幅w、高さhの迷宮を探索したい。トラップは26種類存在し、あるトラップを作動させてしまうと、それ以下の優先度のトラップは全て作動し、トラップのあ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3647 問題 1,2,5,10,20,50,100,200円玉がある。硬貨を全て使ってK人に同じ金額を分配できるか。 K 硬貨の枚数 解法 人数分以上の5,50円玉を10,100円玉に両替して、どの人に5,50円玉を何…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3646 問題 キーボードの配列と正解の文字列、実際に打った文字列を与えるので、スコアの最大値を求めよ。 解法 文字の距離を調べておいてメモ化再帰で解く。キーボードにはスペースが含…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3645 問題 ある時間までにスタート地点からゴール地点まで行きたい。ゴール地点まで飛行機を乗り継いで行くことにする。飛行機の出発地点Oと到着点E、乗れる人数C、出発時間D、到着時間A…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3644 問題 グラフが与えられる。グラフに閉路が出来ないようにしたいが何個の辺を取り除けばよいか。 解法 UnionFindとかを使えばよい。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3642 問題 箱がN個ある。キューブかピラミッドの形にして保存しておきたい。最低何個のキューブとピラミッドが必要か。 0 解法 1つのキューブかピラミッドで使用できる箱の数を計算して…

http://acmicpc-live-archive.uva.es/nuevoportal/data/p4545.pdf 問題 メインプログラムが2つあり、メインプログラムはサブプログラムをN個順番に実行することにより動作する。各サブプログラムはプロセッサーPで実行され、D時間で終了する。2つのメインプ…

http://mirac.jp:8080/cgi-bin/pku_prob.cgi?nosub=1&id=3041 解法 NxNの宇宙空間に小惑星がK個ある。行または列にある全ての小惑星を蒸発させることのできる強力な兵器があり、その兵器を用いて小惑星を全て破壊したい。最低何回兵器を使わなければならない…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3045 問題 牛たちN頭が縦に乗っていく。各牛の重さがWi,強さがSiで与えられたとき、その牛が崩れるリスクはその牛の上に乗っている全ての牛の重さの合計からその牛の強さを引いた物である。牛を最適に並べると…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3989 問題 安定結婚問題を解け。 男の人数 解法 安定結婚問題をO(N^2)で解けばよい。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3988 問題 頂点数M、辺数Nのグラフが与えられる。そのグラフの全域木の最小の重みはいくらか。 M N 解法 クラスカル法で解いた。プリム法でもいける。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3987 問題 2部グラフが与えられるので最小重みマッチングを求める問題。 頂点数は最大で250と350。 解法 最小費用流で解く。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3986 問題 川があってその間に橋を交差しないように架けたい。橋を架ける候補の川の両岸には都市がそれぞれN1,N2個存在し、各都市には得点と都市のタイプがある。同じタイプの都市同士に…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3985 問題 負の辺が存在する有向グラフが与えられる。スタート地点からゴール地点まで行く時の最小スコアを求めよ。 頂点数 解法 ベルマンフォードをする。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3984 問題 高さL、幅Cのフィールドの地形とスタート地点、ゴール地点、泉の場所が与えられる。プレイヤーは泉のあるマスに入ると幅NのジャンプをM回しなければならない。ただし、別の泉…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3983 問題 原点にある荷物をN箇所に順番に届けたい。しかし、荷物には重さがあって同時にC以下の重さの物しか持てない。全ての荷物を届け、原点に戻ってくる最小時間はいくらか。 N C 解…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3982 問題 辺に名前が付いた有向グラフが2つと目的地が2つ与えられる。2つの有向グラフの頂点0から同時に移動を開始して同じ名前の辺を通りながら目的地に行きたい。そのような最短経路…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3981 問題 分岐、ジャンプ、リターン0、リターン1の4命令で作られるプログラムが2つある。その2つのプログラムにどのような入力をしても同じ出力を返すか。 スタックの深さは最大128 コ…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3189 問題 牛がN頭、牛が何頭か入る家畜小屋がB個ある。 それぞれの牛たちには家畜小屋の好みのランクがあり、牛たちの間でなるべく不公平にならないようにしたい。 牛を全て小屋に入れたときに、それぞれの牛…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1059&lang=jp 問題 略 解法 メモ化全探索で間にあう。探索自体は左上の敵から始めてその点を0にするような長方形を使った場合を全て調べればよい。 微妙にメモリが足りないので一番左上…