足跡-sokuseki-

りかの日進月歩の記録

CODE FESTIVAL 2017 Final C Time Gap

C - Time Gap

問題概要

 N 人の都市について、高橋君の都市との時差が与えられる。
高橋君を含めた  N+1 人の都市のうち、すべての2つ都市の時差の最小値を  s としたときの、 s の最大値を求めよ。

制約
 1 \le N \le 50


解法

num[  i ] := 高橋君との時差が  i 時間の人数
とする。

num[  i ]  > 3 となる  i が存在するとき、高橋君との時差が  i 時間の人の中で、互いの時差が0時間となる2人が必ず存在することがわかる。よってその場合の答えは0となる。

そうでないとき、 高橋君の都市が0時であるとする。
num[  i ]  = 2 となる  i については、  i 時の都市と  24 - i 時の都市が存在することが確定する(時差を最大にしたいので2人の時差を0時間にしたくない)。

num[  i ]  = 1 となる  i については、 i 時の都市か  24 - i 時の都市かがわからないので2通りある。
よって、num[  i ]  = 1 となる  i について全探索する。
このような  i の数を  a とすると、 a は高々12であり、すべての場合に対しそれぞれの都市間の時差を調べるので、この全探索にかかる計算量は  O(a^2 \times 2^a) となる。


Submission #2099469 - CODE FESTIVAL 2017 Final (Parallel)

[追記]
解が13個しかないので、決めうちしてから2-SATで殴ることもできます。
Submission #2150954 - CODE FESTIVAL 2017 Final (Parallel)