プレゼント交換 解説
JOI’23 本選４
渡邉 雄斗 (yuto1115)

問題概要• N 人の生徒がプレゼントを持っている．生徒 i のプレゼントの価値は Ai ．
• 生徒 i は価値 Bi ( < Ai) 以上のプレゼントしか受け取りたくない．
• Q 個のグループがある．j 個目のグループは生徒 Lj, Lj + 1,…, Rj からなる．
• それぞれのグループについて，そのグループ内でプレゼント交換できるか判定せよ．
• 価値 Bi 未満のプレゼントや，自分自身のプレゼントは受け取れない．

小課題１ (4 点)• N ≦ 10，Q ≦ 10
• 各グループについて，(グループの人数)! 通りある交換方法を全部試し，条件を満たすものがあるか判定する．

• 計算量 O(QN!)

小課題２ (5 点, 累計 9 点)
• N ≦ 18，Q ≦ 10
• 各グループについて，bit DP を用いて交換方法を効率的に全探索する．
• 計算量 O(Q2 )N

小課題３ (10 点)5• N ≦ 10 ，A1 ≧ 2N − 2，B1 = 1，Q = 1，L1 = 1，R1 = N• グループは，N 人全員からなる 1 つだけ• N 人全員でプレゼント交換できるかを O(N) くらいで判定したい• A1 ≧ 2N − 2，B1 = 1 ← だから何？

小課題３ (10 点)• A1 ≧ 2N − 2，B1 = 1 ← だから何？
• A1 としてあり得る値は 2N − 2, 2N − 1, 2N のみ• まずは A1 = 2N の場合を考えてみる

図の導入

B の昇順に並び替え1 個ずつずらして渡す

小課題３ (10 点)• 「Bi の昇順にソートして，1 個ずつずらして渡す」戦略をとれば，Bi の最大値が A1 より小さいとき，必ずプレゼント交換可能• これは A1 ≧ 2N − 1 ならば常に成立する• A1 = 2N − 2 のときは？
• (A, B) = (2N, 2N − 1) なるペアが存在するときに限り不成立• このとき，明らかにプレゼント交換不可能

小課題３ (10 点)• よって，(A, B) = (2N, 2N − 1) なるペアが存在するか探せばいい• 計算量 O(N)

もっと一般化できないか？

ダメなパターンこれはどうか？

やっぱりダメもっと一般的にこれはダメつまり• ある区間を境に「それより完全に左にある区間」「完全に右にある区間」に二分されてしまう場合，プレゼント交換は不可能• 言い換えると，どの区間も，他のどれかしらの区間と共通部分を持つ必要がある• 実は十分

証明
1. マッチングと捉えて Hall の結婚定理を適用• 知識が必要なので，詳細略• 証明に使えるだけでなく，最初から Hall で考えると自然にこの条件が出てくる
2. 貪欲法を用いる• どの区間も他のどれかしらの区間と共通部分を持つとき，実際にプレゼント交換をする方法を構築できればよい．

• 正しい貪欲法を用いれば，可能正しい貪欲法• グループは N 人の生徒全員からなり，B1 < B2 < … < BN が成り立つと仮定する．
• そうでなければソート等によって適切に変形する．
• i = 1, 2, …, N の順に以下を行う：• 生徒 i のプレゼントを受け取ることができ，まだ誰のプレゼントを受け取っていない人のうち，Bi が最も大きい人を選んで生徒 i のプレゼントを渡す．

• そもそもそんな人が 1 人もいないなら，プレゼント交換は不可能．

正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法正しい貪欲法• この貪欲法が途中で失敗する i.e. ある j について生徒 j のプレゼントを受け取れる人が誰もいない場合，区間 j は他のどの区間とも共通部分を持たないことが示せる．

• 対偶：どの区間も他のどれかしらの区間と共通部分を持つとき，この貪欲法は必ず成功する．つまり，実際にプレゼント交換をする方法が構築できる．証明完了．

小課題４ (31 点, 累計 50 点)• N ≦ 10 ，Q ≦ 105• グループ内の各区間について，その区間との共通部分を持つような他の区間がグループ内に存在するか判定すれば良い．
ソート等を用いて，クエリあたり O(N log N)• 条件を見つけていなくても，正しい貪欲がわかっているならば，std::set 等を用いて実際にシミュレーションし，貪欲が途中で失敗するかどうか調べればよい．

• 計算量 O(QN log N)• 嘘貪欲に気をつけましょう小課題５ (8 点, 累計 58 点)
5• N ≦ 10 ，A1 < A2 < … < AN ，B1 < B2 < … < BN
• 小課題４を貪欲法で解いた人が条件を見つけるのを助ける用の小課題• 限定された条件下での貪欲法の動作をよく観察し，貪欲法が失敗するのはどんなときか考察する．

小課題５ (8 点, 累計 58 点)•5N ≦ 10 ，A1 < A2 < … < AN ，B1 < B2 < … < BN

• 条件をすでに見つけている人にとっては簡単• ある区間が他の区間と共通部分を持つかは，その区間と両隣の区間との位置関係のみによって定まる．

• Ai−1 < Bi < Ai < Bi+1 を満たすような区間（つまり，両隣と共通部分を持たないような区間）の番号の集合 S を前計算する．

• クエリでは，[Lj, Rj] 内に S の要素があるか見ればいい．両端の扱いに注意．

小課題６〜満点• 各区間 i に対して以下の値を定義する：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）

• あるグループが生徒 i を含み，かつそのグループを成す生徒の番号の範囲が[Si + 1,Ti − 1] に含まれるとき，区間 i はそのグループ内で他と共通部分を持たない• ⇒ Lj ∈ [Si + 1, i] かつ Rj ∈ [i, Ti − 1] なら，グループ j はプレゼント交換不可能

小課題６〜満点• 従って， Si, Ti が各区間 i について求まっているとき，以下の問題に帰着される：• N × N の二次元平面上に N 個の長方形が存在している．
• 平面上の点が Q 個与えられる．
それぞれの点について，その点を内部に含む長方形が存在するか判定せよ．

• Fenwick tree (BIT) や Segment tree を用いた平面走査によって O(Q log N)小課題６〜満点• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）

• これを高速に求めるのが最後の課題（満点まで共通）．

小課題６ (12 点, 累計 70 点)• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）
5

• N ≦ 10 ，A1 < A2 < … < AN
• Si については簡単：Ai−1 > Bi ならば i − 1，Ai−1 < Bi ならば 0小課題６ (12 点, 累計 70 点)• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）
5

• N ≦ 10 ，A1 < A2 < … < AN
• Ti については？
• Ai > Bj を満たす最小の j ( > i)

小課題６ (12 点, 累計 70 点)• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）
5

• N ≦ 10 ，A1 < A2 < … < AN
• Ti については？
• Ai > Bj を満たす最小の j ( > i)
• segment tree や stack などのデータ構造上で二分探索• 計算量 O(N log N + Q(log N + log Q))

小課題７ (18 点, 累計 88 点)• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）
5

• N ≦ 10
• 2D segment tree (point update rectangle max) などを用いる（詳細略）• ほぼ ”貼るだけ” だが，余分 log が付くので満点は取れない
2• 計算量 O(N log N + Q(log N + log Q)) など

小課題８ (12 点, 累計 100 点)• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）
5

• N ≦ 5 × 10
• Si についてだけ考える（Ti も同様）
• 長さ 2N の配列 v = (0,0,…,0) を用意する．i = 1,2,…, N の順に以下を行う：• v[Bi], v[Bi + 1], …, v[Ai] の最大値を求め，Si とする．
• v[Bi], v[Bi + 1], …, v[Ai] の値をすべて i に更新する．

小課題８ (12 点, 累計 100 点)• 各区間 i に対して以下の値を定義する（再掲）：• Si：区間 i と共通部分を持つ区間の番号のうち，i 未満で最大のもの（ないならば 0）• Ti：区間 i と共通部分を持つ区間の番号のうち，i より大きくて最小のもの（ないならば N + 1）
• 長さ 2N の配列 v = (0,0,…,0) を用意する．i = 1,2,…, N の順に以下を行う：• v[Bi], v[Bi + 1], …, v[Ai] の最大値を求め，Si とする．
• v[Bi], v[Bi + 1], …, v[Ai] の値をすべて i に更新する．

• lazy segment tree (range update range max) が使える．
• 計算量 O(N log N + Q(log N + log Q))

得点分布
100

(0, 100] 77 人
[50, 100] 32 人
100 5 人755025004910 141719 50 58 70 88 100