CODE FESTIVAL 2017 Final C Time Gap
問題概要
人の都市について、高橋君の都市との時差が与えられる。
高橋君を含めた 人の都市のうち、すべての2つ都市の時差の最小値を としたときの、 の最大値を求めよ。
制約
解法
num[ ] := 高橋君との時差が 時間の人数
とする。
num[ ] となる が存在するとき、高橋君との時差が 時間の人の中で、互いの時差が0時間となる2人が必ず存在することがわかる。よってその場合の答えは0となる。
そうでないとき、 高橋君の都市が0時であるとする。
num[ ] となる については、 時の都市と 時の都市が存在することが確定する(時差を最大にしたいので2人の時差を0時間にしたくない)。
num[ ] となる については、 時の都市か 時の都市かがわからないので2通りある。
よって、num[ ] となる について全探索する。
このような の数を とすると、 は高々12であり、すべての場合に対しそれぞれの都市間の時差を調べるので、この全探索にかかる計算量は となる。
Submission #2099469 - CODE FESTIVAL 2017 Final (Parallel)
[追記]
解が13個しかないので、決めうちしてから2-SATで殴ることもできます。
Submission #2150954 - CODE FESTIVAL 2017 Final (Parallel)