2020年1月16日木曜日

CODE FESTIVAL 2016 Relay H - 早起き

$T=0$の場合に高橋君が起きる時刻を$c_1, c_2, ..., c_N$とする。数列$(c_i)$全体に定数を足して(または引いて)、$\mod 86400$で$\{ 0, 1, ..., 10800\}$に含まれるような$c_i$の数を最大化すればよい。ところで、$(c_i)$の代わりに後者に定数を足すと考えてもよい。つまり、$c_i$を$\mod 86400$で分類した時に、$[x, x+10800]$に含まれる$c_i$の数を($x$を動かして)最大化する問題と考えられる。調べる範囲は$x=0, 1, ..., 86399$でよく、累積和で処理しておけば各ステップは${O}(1)$で済む。