PCK 2017 本選:5 - 朝昼晩ごはん
問題
解法
朝・昼・晩の時間の決め方は,単純に考えると (24*60)^3 通り.これを全て計算していては間に合わない.時間の決め方は N 人の3つの時間の区間の始点と終点の数だけに抑えることが出来るので N^3 通りになる.それぞれについて,その時間に何人が当てはまるかを計算すればよい.O(N^4).
解答
1回 TLE を出してしまった.
朝・昼・晩の時間の決め方は,単純に考えると (24*60)^3 通り.これを全て計算していては間に合わない.時間の決め方は N 人の3つの時間の区間の始点と終点の数だけに抑えることが出来るので N^3 通りになる.それぞれについて,その時間に何人が当てはまるかを計算すればよい.O(N^4).
1回 TLE を出してしまった.