AtCoder Beginner Contest 185, B : Smartphone Addiction

問題文

　https://atcoder.jp/contests/abc185/tasks/abc185_b

問題概要

　バッテリー容量が $N$ [mAh] のスマートフォンを携帯し散歩をすることを考える（単位の話は Wikipedia 先輩に 任せる．面倒なので以降無単位量として扱う）．
　散歩の詳細は，

• バッテリーを満充電した状態（バッテリー残量が $N$ な状態）で時刻 $0$ に出発する
• 途中 $M $ 回カフェに寄って充電をする
  • $i$ 回目の滞在は時刻 $A_i$ から時刻 $B_i$
• 時刻 $T$ に帰宅する

である．
　バッテリーは，カフェに居るとき単位時間あたり $1$ ずつ充電され（ただし容量 $N$ を超えることはない），それ以外の時間（歩行中）では単位時間あたり $1$ ずつ放電される．
　バッテリー残量が $0$ にならずに帰宅できるか？

制約

• $1 \leq N \leq 10^9$
• $1 \leq M \leq 1{,}000$
• $1 \leq T \leq 10^9$
• $A_i, B_i, T$ についてのいい感じの制約（時系列的な整合性の話）

解法

　特に賢い方法は思いつかないので，バッテリー残量の変化をシミュレーションすることによって問題を解くこととします．時刻を $1$ ずつ進めながらシミュレーションできれば楽ですが，$T$ の制約がそれなりに大きいことから，それはできません．そこで，歩き続けている間・カフェに滞在し続けている間はある種一様な動きをすることを使って，一回あたりの（極大な）歩行とカフェ滞在をまとめて処理することを考えます．
　便宜上，$B_0 = 0$, $A_{ M + 1 } = T$ とします．こうすると，

• $i$ 回目の歩行は時刻 $B_{ i - 1 }$ から時刻 $A_i$
• $i$ 回目のカフェ滞在は時刻 $A_i$ から時刻 $B_i$

という風に統一的に扱えます．また，バッテリー残量 $n$ の状態から時間 $d$ の歩行またはカフェ滞在を行った場合のバッテリー残量の変化……というか，実施後のバッテリー残量 $n'$ は，$n' = \min( N, \max( 0, n + \mathit{ sgn } \times d ) )$ という形で書けます．ここで，$\mathit{ sgn }$ は歩行中は $-1$ ，カフェ滞在中は $+1$ です．この算数（？）をすると，一回の歩行またはカフェ滞在を $O( 1 )$ 時間でシミュレートできます．あとは，全体をシミュレートする間にバッテリー残量が $0$ 以下になっていないかどうかをチェックすることで，問題を解くことができます．

コード

int main()
{
	IN( int, N, M, T );
	
	VI ts( 1 );
	REP( M )
	{
		IN( int, A, B );
		ts.PB( A );
		ts.PB( B );
	}
	ts.PB( T );

	int current = N;
	REP( i, SZ( ts ) - 1 )
	{
		const int a = ts[i], b = ts[ i + 1 ];
		const int increase = i % 2;

		current += ( increase ? 1 : -1 ) * ( b - a );
		chmin( current, N );
		if ( current <= 0 )
		{
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}

main = do
	[ n, m, t ] <- readInts
	ab <- concat <$> replicateM m readInts
	let
		ts = [ 0 ] ++ ab ++ [ t ]
	putStrLn $ which "Yes" "No" $ solve n ts n (-1)

solve _ [_] _ _ = True
solve n (a1:a2:as) current sign
	| nex <= 0 = False
	| otherwise = solve n (a2:as) nex ( negate sign )
	where
		d = sign * ( a2 - a1 )
		nex = min n $ current + d