ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, E 解答

E: 3D プリント

問題

3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。
ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。
n個の設計図からk個選んで立体を置いたとき、一つの立体に成るようにしなければならない。
このとき、その大きい立体の表面積の最小値を出力せよ。
入力のn個の立方体は次の条件を満たしている。

  1. 各立方体は0個・1個・2個の立方体と連結することはあるが、3個以上の立方体と連結することはない
  2. ある立方体が2個の立方体と連結するとき、その2つは連結していない
  3. どの2つの立方体も頂点・辺・面で接することはない。真に離れているか、真に共通部分を持つかのどちらかである
続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, D 解答

D: ダルマ落とし

問題

長さnの数列aが与えられる。次の操作を好きなだけ繰り返す。

  • 数列の任意の隣り合う2数を一つ選び、その差の絶対値が1以下ならばその2数を数列から取り除き、数列は詰めて長さが2短くする

最大で幾つ取り除くことができるか。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, B 解答

B: 当選者を探せ!

問題

選挙の開票を行う。26人の候補者があり、票の総数はnで、1票づつ開けていく。
単独首位で当選確実になった候補者が初めて決まるのは何票目で誰か、出力せよ。
ただし開票して首位が2人以上いるならば"TIE"と出力せよ。

続きを読む

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を持ち、時刻になると先頭の命令から順に実行可能になる。
実行中のタスクから最も優先度の高いタスクを選んでそれを実行することに成る。

続きを読む