CODE FESTIVAL 2015 予選A D問題壊れた電車

23:26追記 私の考えていた80点解法は100点解法だったようです

http://www.slideshare.net/chokudai/codefestival2015quala

問題文

http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_d

20点解法

次のようなケースを考える (赤色の○が整備士がいる車両)。

f:id:kujira16:20150926230720p:plain

前のほうにいる整備士から数えて順に整備士1, 2, 3という番号をつける。solve(x,y)として「[x,M]の整備士で[y,N]の車両を点検する場合の最短時間」を返す関数を考える。solve(1,1)を計算することが目的である。

常識的に考えて、車両1や車両2は整備士1に担当させるのが妥当である。すると、solve(1,1)の計算は以下のような小問題に分解できる。

整備士1に[1,3]を点検させて、整備士2以降に[4,10]を点検させる (return max(2, solve(2,4);)
整備士1に[1,4]を点検させて、整備士2以降に[5,10]を点検させる (return max(4, solve(2,5);)
以下同様

整備士2も同様に計算できる。たとえば solve(2,4) なら以下のような感じになる。

整備士2に[4,6]を点検させて、整備士3に[7,10]を点検させる (return max(2, solve(3,7);)
整備士2に[4,7]を点検させて、整備士3に[8,10]を点検させる (return max(4, solve(3,8);)
以下同様

動的計画法を使うと O(MN²)。場合分けでバグらせそうで怖い。

80点解法

t分で点検が終わらせられるかどうか判定する関数を作り、二分探索でtが最小となるところを求める。

t分で点検が終わらせられるかどうか判定するには、前にいる整備士から順にt分以内で点検可能ななるべく多くの範囲を点検させて、M人で全ての車両を点検できるかを判定すればよい。

上に上げた図の場合であれば、車両1、車両2、車両3は明らかに整備士1の持ち場なので、[1,3]は必ず整備士1に担当させる。t=0, t=1の場合は車両1を点検できる人がいないので不可。t=2,t=3なら整備士1が[1,3]が点検でき、t=4,t=5なら[1,4]が点検でき、t=6なら[1,5]が点検でき、…といった感じに前から貪欲に決めていく。80点を目指す解法の場合は、どの車両までを点検できるか？ということを決めるときに二分探索を使って良い。

計算量は O(M log² N)。正直、100点解法のほうが簡単だと思う。