ACM-ICPC World Finals 2016 M解法

M: What Really Happened on Mars?

問題

t個のタスクがある。各タスクは命令の列で、命令は3種類

  1. compute : 1クロック消費する。
  2. lock k : リソースkをロックする
  3. unlock k : リソースkをアンロックする

各タスクiは開始の時刻t_iと優先度p_iを持ち、時刻になると先頭の命令から順に実行可能になる。
実行中のタスクから最も優先度の高いタスクを選んでそれを実行することに成る。

続きを読む

ACM-ICPC World Finals 2016 L解法

L: Swap Space

問題

n個のHDDがある。
それぞれは現在 容量a_iで、一つづつ取り替えて容量b_iにしたい。
HDDは全てフルに容量が埋まっており、取り替えるときはデータをn個の中の他のHDD、もしくは追加のHDDに移して、空になってからb_iになる。複数に分けて移しても良い。
最終的にデータを元のHDDに入れる必要はなく、追加のHDDに残しても良い。
追加のHDDは最小でいくらの容量が必要か。

続きを読む

ACM-ICPC World Finals 2016 K解法

K: String Theory

問題

文字列について、先頭と末尾が「'」(シングルクォート) で、間にアルファベットのみが0文字以上あるものを1-quotationと定義する。
k > 1について、先頭と末尾がちょうどk個のシングルクォートで、間には「(k-1)-quotationとシングルクォートを含まない文字の二種類の、合わせて0個以上の任意の順番の連結」であるものと定義する。
文字列Sが与えられるが k-quotation のkを求めよ。
複数ある場合は最大、存在しない場合はそれを指摘し出力せよ。
Sは連続したシングルクォートのみ切り出して、その長さを持って与えられる。
例えば「3 2 5」が入力で与えられた時はSは '''(任意のアルファベット列)''(任意のアルファベット列)''''' を意味する。

続きを読む

ACM-ICPC World Finals 2016 J解法

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) の値でソートし、その順番で c_i == 1の人がなるべく集まるようにしなさい。

続きを読む

ACM-ICPC World Finals 2016 I解法

I: Road Times

問題

n 頂点 m 辺の有向グラフが与えられる。
各辺は距離[km]が与えられる。
あなたが頂点uからvへ移動するときには、必ず距離が最短に成るように移動する。
各辺は速度が定数で制限されており、それは時速30km以上60km以下の実数の定数で、あなたはその辺を通るときはちょうどその速度で移動する(要はx[km]の辺はx~2x[min.]の実数の定数時間が掛かる)。
その速度の定数は分からないが、情報としてr個のヒント(出発点、到達点、時間[min.])が与えられる。
q個の質問:「頂点sからdに移動するときに掛かる、最短時間と最長時間を出力」に答えよ。

続きを読む