M: What Really Happened on Mars? 問題 t個のタスクがある。各タスクは命令の列で、命令は3種類 compute : 1クロック消費する。 lock k : リソースkをロックする unlock k : リソースkをアンロックする 各タスクiは開始の時刻t_iと優先度p_iを持ち、時刻に…

L: Swap Space 問題 n個のHDDがある。 それぞれは現在 容量a_iで、一つづつ取り替えて容量b_iにしたい。 HDDは全てフルに容量が埋まっており、取り替えるときはデータをn個の中の他のHDD、もしくは追加のHDDに移して、空になってからb_iになる。複数に分けて…

K: String Theory 問題 文字列について、先頭と末尾が「'」(シングルクォート) で、間にアルファベットのみが0文字以上あるものを1-quotationと定義する。 k > 1について、先頭と末尾がちょうどk個のシングルクォートで、間には「(k-1)-quotationとシングル…

J: Spin Doctor 問題 n人の個人情報が与えられる。i番目の人の情報は a_i : 覚えている円周率の桁数 0 ~ 2000000 b_i : 髪の毛の本数 0 ~ 2000000 c_i : 候補者Xに投票したかどうか 0/1 実数のパラメータS, Tを適切に決めて人々を (a_i * S + b_i * T) の値…

I: Road Times 問題 n 頂点 m 辺の有向グラフが与えられる。 各辺は距離[km]が与えられる。 あなたが頂点uからvへ移動するときには、必ず距離が最短に成るように移動する。 各辺は速度が定数で制限されており、それは時速30km以上60km以下の実数の定数で、あ…

G: Oil 問題 地面水平方向x軸。垂直方向下向y軸。y=0が地表の2次元座標上の問題。 油井は地中にあり、地表と水平な線分で表される。 n個の油井のいち情報が与えられる。 地表から1本の直線状に任意の角度でドリルで掘って、接するか交差した油井の油を得るこ…

F: Longest Rivers 問題 n+m+1頂点、葉がn個の重み付き根付き木が与えられる。 各葉は川の源流で、川は辺にそって根の方向に続く。すべての辺はただ一つの川に属する。 (辺をn個の川に分割する、一つの川はつながって枝分かれしない。合流した川はいずれか一…

E: Forever Young 問題 私はY歳です。 適切なBを求めて、「YをB進数で表した時全ての桁は0~9であり、その表示を十進数とみなすとL以上である」ようにしなさい。 その最大のBを出力しなさい。

D: Clock Breaking 問題 7セグデジタル時計がある。4桁とコロンの2セルの計30箇所のセグの表示がある。 この時計は壊れている可能性があり、各セグは 正しく動作する 常に0を表示する 常に1を表示する のどれかである。

C: Ceiling Function 問題 n個のk頂点-二分探索木が与えられる。 二分探索木は挿入する値とその順番によって与えられる(回転などはしない)。 何種類の形があるか数えよ。

B: Branch Assignment 問題 n 頂点 r 辺の重み付き有向グラフがある。頂点はv_1 ... v_nとする。 そのうち、v_1 ... v_bのb個の頂点はbranch (支店）が置いてあり、v_{b+1}にはheadquarter(本店)がある。 支店をs個のグループに分割したい(s 月に一度、各支…

A: Balanced Diet 問題 Dannyはm種類の菓子を一つづつ食べる。今までの菓子iを食べた個数をs_iとする。 各菓子iの個数は割合f_iに近い値にしたい。 正確には、今まで食べたお菓子の総数をnとすると、任意のお菓子iは を満たす必要がある。すでに、k個のお菓…