atcoder.jp 二分法探索 N本とM本の組み合わせですが、最大で となりうるため、すべての組み合わせを計算して、ソートして 番目を求めるのは時間がかかりすぎます。 番目を求めたいけれど、ソートするのが大変な場合、二分法で探索することを考えます。ある濃…

atcoder.jp 範囲で調べる 圧縮された配列を元に戻して (最大長さ ) 2つの配列の各要素を比較するのは時間がかかりすぎるため、圧縮した情報のまま数えていきます。ある値が、配列の何番目から何番目までの範囲になるかは、 の累積和から決まります。 ごとに…

atcoder.jp 問題文の内容把握 問題設定がわかりずらいですが、整理すると、各人について 3つの状態があります。 (A) 呼ばれていない (B) 呼ばれて、受付前 (C) 受付済イベントは3種類ありますが、イベント1 は状態(A) ⇒ (B) への遷移、イベント2は状態 (B) ⇒…