ARC226 A - Meeting Division

会議の分担

考え方

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

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

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

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

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

入力を受け取る。

n: 3
meetings:
(1, 3)
(2, 4)
(5, 6)

開始時刻が早い順に処理する。

時刻 $1$ では $2$ 人とも空いているので、担当者の選び方は $2$ 通りである。
一方をこの会議に割り当てると、その人は時刻 $3$ まで拘束される。

時刻 $2$ では $1$ 人だけ空いているので、担当者の選び方は $1$ 通りである。
その人も時刻 $4$ まで拘束される。

時刻 $5$ では、それまでの会議はどちらも終了している。
再び $2$ 人とも空いているので、担当者の選び方は $2$ 通りである。

したがって、割り当て方の総数は $2\times1\times2=4$ 通りとなる。

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

特になし。