ARC226 A - Meeting Division

会議の分担

考え方

会議の開始時刻に、何人空いているかで分けて考える。

$1$ 人も空いていない場合、その時点で無理なので、その時点で打ち切ってよく答えは $0$ となる。
$1$ 人だけ空いている場合、その人を割り当てることしかできないので、パターン数に何も影響しない。

$2$ 人とも空いている場合、どちらに割り当てることもできる。
それぞれの片方に割り当てた場合のパターンは同じなので、片方で固定した場合の $2$ 倍とすればよい。

以上より、イベントソートでシミュレーションをすれば簡単に答えが出る。
すなわち、各会議の開始時点で何人が暇かを全てかけ合わせればよいだけである。

計算量はソートが支配的で $O(N\log N)$。
バケツソート等を使えば $O(N)$ にもできる。

入力を受け取り、開始時刻が早い順にソートすると、以下のようになる。

vec = [(1, 3), (2, 4), (5, 6)]

はじめ、$2$ 人の拘束終了時刻（フリーなら $-1$）と結果を以下のようにしておく。

a = -1
b = -1
result = 1

(1, 3) を処理する。
$2$ 人ともフリーなので、result を $2$ 倍し、a を時刻 $3$ まで拘束する。

a = 3
b = -1
result = 2

(2, 4) を処理する。
a は時刻 $3$ まで拘束されているが、b はフリーなので、割り当て可能な人数は $1$ 人である。
result は変わらず、b を時刻 $4$ まで拘束する。

a = 3
b = 4
result = 2

(5, 6) を処理する。
a, b ともに会議が終わっているのでフリーに戻す。
$2$ 人ともフリーなので、result を $2$ 倍し、a を時刻 $6$ まで拘束する。

a = 6
b = -1
result = 4

よって、答えは $4$。

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 する。

特になし。