おもしろいタイトルですね．Smartphone Addiction（スマホ中毒）というタイトルです．この問題，B問題ですが残念ながらTLEで解けなかったので解説しようと思います．
問題
公式の問題はこちらです．
問題文
時刻 n + 0.5 ごとに残量が 1 [mAh] ずつ減少する，バッテリー容量が N [mAh] のスマートフォンを考えます．スマートフォンを満充電した状態で時刻 0 に外出し，途中で M 回カフェに訪れ，時刻 T に帰宅します．
i 回目に訪れるカフェで，時刻 Ai から Bi まで滞在し，この間は n + 0.5 ごとに 1 [mAh] ずつバッテリー残量が増加します（この際バッテリー容量は減少しません）．ただし，既にバッテリー残量がバッテリー容量と等しい場合は，バッテリー残量は増えも減りもしません．途中でスマートフォンのバッテリー残量が 0 になることなく帰宅することができるかを判定してください．
制約
- $1 ≤ N ≤ 10^9$
- $1 ≤ M ≤ 1000$
- $1 ≤ T ≤ 10^9$
- 0< A1 < B1 < A2 < B2 < A3 < B3 < ⋯ < AM < BM < T
- 入力は全て整数
解説
冒頭で記載したとおり，コンテストではTLEとなってしまい解けませんでした．原因は，現在カフェにいるか否かどうかを時刻ごとに判定していたため，計算量が $O(TM)$ となっていたことと思われます．
n+0.5 の時刻で放電 or 充電されるというのは，i 回目にカフェに着いた時刻に $A_i – B_{i-1}$ [mAh] 放電し，$B_i – A_i$ [mAh] 充電することと同義です．
ただし，$B_0 = 0$ とします．最後のカフェから家までの放電も忘れず加味するため，家の到着を M+1 回目のカフェへの到着と見立て，$A_{M+1} = T, B{M+1} = T$ とします．
こういう問題は境界条件を考えるのが結構しんどいですね．
また，バッテリ容量よりもバッテリ残量が大きくならないようにします．
これを踏まえると，以下のようなコードとなり，計算量は $O(M)$ となります．
#include <stdio.h>
#include <iostream>
using namespace std;
int main(void) {
int N, M, T;
cin >> N >> M >> T;
int bat = N; // charge is Max at the start.
int last_time = 0;
bool ret = true;
for (int i=1; i<=M+1; i++) {
int a, b;
if (i<M+1) { cin >> a >> b; }
else { a = T; b = T;}
bat -= a-last_time; // discharging outside cafe
if (bat <= 0) {
ret = false;
break;
}
bat = min(bat + b-a, N); // charging inside cafe
last_time = b;
}
if (ret == true) { cout << "Yes" << endl; }
else { cout << "No" << endl; }
return 0;
}まとめ・感想
TLEで解けないのははじめてでした．時刻ごとに調べるという発想から，チェックポイント（今回の場合はカフェ）ごとに状態を調べるという発想に転換することで計算量を減らせたんですね．勉強になりました．
コメント