JOIG 2021/2022 春合宿 競技2 2問目

Airport 解説
大佐 健人

問題概要
• 空港に、𝑁 本の滑走路がある• 𝑀 個の着陸計画がある（使う滑走路は自由に決められる）• 合間を縫って、𝑇 分間でできるだけ多くの飛行機を離陸させる• ただし、1 回の離陸で 𝐾 分間、着陸で 𝐿 分間 1 つの滑走路を占有する

問題概要• 空港に、𝑁 本の滑走路がある

問題概要• 空港に、𝑁 本の滑走路がある• 𝑀 個の着陸計画がある（使う滑走路は自由に決められる）

時刻 0

時刻 T

問題概要
• 空港に、𝑁 本の滑走路がある• 𝑀 個の着陸計画がある（使う滑走路は自由に決められる）
L

L

時刻 0L

L

時刻 T

問題概要
• 空港に、𝑁 本の滑走路がある • 合間を縫って、𝑇 分間でできるだけ多くの飛行機を離陸さ• 𝑀 個の着陸計画がある
せる
K

時刻 0K

LK

時刻 T

問題概要
• 下図のような場合は、着陸する時間がどうしても被るので、スケジュールを立てられない（-1 を出力）

L

L

時刻 0

L

時刻 T

基本的な考え方①まず、各着陸でどの滑走路を使うかを決める

L

L

時刻 0L

L

時刻 T

基本的な考え方①まず、各着陸でどの滑走路を使うかを決める②そのもとで、最大どれだけ離陸させられるかを計算

K

時刻 0K

L

K

時刻 T

小課題 1•𝑁=1• 滑走路は 1 つなので、どの滑走路を使うか気にする必要はない• とにかく離陸数を多くすることを考える• 𝐴𝑖 の番号の付けかたに意味はないので、まずソートして良い• 以降、𝐴1 ≤ 𝐴2 ≤ ⋯ ≤ 𝐴𝑀 とする

小課題 1：-1 になる条件• 𝐴𝑖+1 − 𝐴𝑖 < 𝐿 なる 𝑖 が存在すると NG• 着陸している最中に次の飛行機が着陸を始めてしまうため

小課題 1• -1 でないとき、着陸の合間に𝐴𝑖+1 − 𝐴𝑖 − 𝐿 分間の空き時間がある• Q. この間にどれだけ離陸させられる？
𝐴𝑖+1 −𝐴𝑖 −𝐿• A.の小数点以下を切り捨てた数
𝐾

𝐴𝑖KKL

𝐴𝑖 + 𝐿𝐴𝑖+1 − 𝐴𝑖 − 𝐿

𝐴𝑖+1

小課題 1
𝐴𝑖+1 −𝐴𝑖 −𝐿• 答えは、すべての 𝑖 についての(の切り捨て)の和𝐾• 𝐴 のソートがボトルネックで、計算量は 𝑂(𝑀𝑙𝑜𝑔𝑀)•7点

小課題 2• 𝑁 = 2, 𝑀 ≤ 20
• 各飛行機について、どちらの滑走路を使うかを決める必要がある• 着陸する飛行機だけでも決められないか？

小課題 2：考察• 𝑀 機の飛行機について、滑走路の選び方は 2 通りあるので、全体で 2𝑀 通り• 全ての選び方について、そのときの離陸数の最大値を求める• -1 になる場合 (同じ滑走路で着陸が重なる) はちゃんと除く• 小課題 1 と同じように、(空き時間)/ 𝐾 を切り捨てた値の和を2 つの滑走路について計算• その合計が離陸数

小課題 2：計算量• 滑走路の選び方を決めるのに 𝑂 2𝑀
• 滑走路ごとに離陸数の最大値を求めるのに 𝑂(𝑁𝑀)• 全体で 𝑂 2𝑀 𝑁𝑀 で、𝑀 ≤ 20 なので間に合う(220 ≈ 106 )• 12 点

小課題 2：実装• 2𝑀 通りの全探索は、2 進数を使った方法が有名• 飛行機 𝑖 が滑走路 1 を使うなら 𝑖 桁目を 0 、滑走路 2 を使うな
ら 𝑖 桁目を 1 とした 2 進数で状態を表現する• 10 進数で 0 から 2𝑀 − 1 まで探索すれば、全状態を探索できる• いわゆる「bit 全探索」

小課題 3• 𝑁 = 2, 𝐾 = 2, 𝐿 = 2• 偶奇が重要な小課題？

小課題 3：-1 の場合• 明らかに NG な場合：𝐴𝑖 = 𝐴𝑖+1 = 𝐴𝑖+2

• これも NG：𝐴𝑖 + 1 = 𝐴𝑖+1 = 𝐴𝑖+2 または 𝐴𝑖 + 1 = 𝐴𝑖+1 + 1 = 𝐴𝑖+2

• つまり、長さ 2 の区間の中に 𝐴𝑖 が 3 つ以上あるとNG• 逆に、そうじゃなかったら OK であることがいえる考え方の転換• (空き時間)/𝐾 を切り捨てた数だけ離陸できるということは、切り捨てられた分の時間が無駄になっている• 無駄な時間の和を最小化できれば、答えが最大化できる• (無駄な時間)= 空き時間を 𝐾 で割った余り をできるだけ小さくすることを考えよう

無駄な時間

K

L
𝐴𝑖

𝐴𝑖 + 𝐿K
𝐴𝑖+1

小課題 3：𝐴𝑖 が相異なる場合• 無駄な時間：空き時間が奇数のとき 1、偶数のとき 0 になる→できるだけ空き時間を偶数にしたい• 𝐴𝑖 が偶数のものを滑走路 1 に割り当てる• 𝐴𝑖 が奇数のものを滑走路 2 に割り当てる• すると、同じ滑走路内での空き時間（端を除く）は必ず偶数！
• 𝐴𝑖 + 𝐿は 𝐿 = 2 より 𝐴𝑖 と偶奇が同じで、かつ (偶数) – (偶数) = (偶数)、(奇数) – (奇数) = (偶数) だから

小課題 3：𝐴𝑖 が相異なる場合• 空き時間が偶数、かつ 𝐾 = 2 より、空き時間に離陸を詰め込める→無駄な時間が端以外に生まれず、これが最適になる• 無駄な時間をこれ以下にすることができないことが示せる• 𝐴𝑖 に被りがある場合も、この戦略を応用すれば OK

小課題 3• 𝐴𝑖 が被っている場所は他にやりようがないので、滑走路を両方使う• その他の場所は、𝐴𝑖 の偶奇で滑走路を分ける• 実は、これが離陸数を最大にする戦略• 滑走路を同時刻に両方使うと滑走路 1 と滑走路 2 が等価になり、時刻0と同じ状況になる• この通りに滑走路を割り振って計算すれば、𝑂(𝑀) で答えが求まる• 17 点

小課題 4•𝑁=2• 今までの小課題で分かったこと• 着陸する滑走路が決まると、空き時間を 𝐾 で割って切り捨てたものの和が答えになる→空き時間を 𝐾 で割った余りが無駄• 𝐾 = 2, 𝐿 = 2 なら 長さ 2 の区間に 3 つ以上 𝐴𝑖 があると NG• 𝐾 = 2, 𝐿 = 2 なら 𝐴𝑖 の偶奇を滑走路内でできるだけそろえると良い• これを総動員しよう

小課題 4：-1 になる条件• 𝑁 = 2, 𝐾 = 2, 𝐿 = 2 のとき、長さ 2 の区間の中に 𝐴𝑖 が 3 つ以上あるとNG だった• 一般の場合では、長さ 𝐿 の区間の中に 𝐴𝑖 が 𝑁 + 1 個以上あると NG という条件になり、𝑂(𝑀) で判定できる←どこにも着陸できない

小課題 4• 空き時間を 𝐾 で割った余りの和をできるだけ小さくしたい• 小課題 3 では、同じ滑走路ではなるべく𝐴𝑖 の偶奇を同じにすればよかった• 滑走路 1, 2 で最後に着陸を終えた時間を 𝑥, 𝑦 とする• 次の飛行機が時刻 𝐴𝑖 に着陸するとき、生じる無駄な時間は？
• 滑走路 1 に着陸するとき 𝐴𝑖 − 𝑥 + 𝐾 %𝐾
• 滑走路 2 に着陸するとき 𝐴𝑖 − 𝑦 + 𝐾 %𝐾

小課題 4• 𝐴𝑖 − 𝑥 + 𝐾 %𝐾, 𝐴𝑖 − 𝑦 + 𝐾 %𝐾 を計算することで、どちらに着陸すれば次に生じる無駄な時間が小さくなるかわかる• つまり、毎回「生じる無駄な時間が最も小さい滑走路を選ぶ」という貪欲法ができる
無駄な時間

K
𝐴𝑖𝑥

無駄な時間

K𝑦K
𝐴𝑖

小課題 4• 普通、貪欲法は最終的に最適になるとは限らない（注意！）• そういう時は動的計画法が使われる• ただし、この問題では貪欲法で最適解を出せる• 各滑走路で最後に着陸を終えた時間を持てば、𝑂(𝑁𝑀) で実装できる• 12 + 17 + 28 = 57 点
• 貪欲法は正当性を確かめるのが大事（今回はちょっと難しい）貪欲法の正当性• 証明の概要• 滑走路 1,2 で最後に着陸を終えた時間を 𝑥, 𝑦 とする• 滑走路 1 を選ぶと、最後に着陸を終えた時間は (滑走路 1,滑走路 2)= (𝐴𝑖 + 𝐿, 𝑦)となる• 滑走路 2 を選ぶと、最後に着陸を終えた時間は(滑走路 1,滑走路 2)= (𝑥, 𝐴𝑖 + 𝐿) となるが、これは (𝐴𝑖 + 𝐿, 𝑥)と等価• 貪欲法だと滑走路 1 を選ぶことになるとする( 𝐴𝑖 − 𝑥 + 𝐾 %𝐾 ≤ 𝐴𝑖 − 𝑦 + 𝐾 %𝐾)• このもとで、任意の 𝑧 について、
𝐴𝑖 − 𝑥 + 𝐾 %𝐾 + 𝑧 − 𝑦 + 𝐾 %𝐾 ≤ 𝐴𝑖 − 𝑦 + 𝐾 %𝐾 + 𝑧 − 𝑥 + 𝐾 %𝐾 がいえる
• よって、滑走路 2 を選んでも得になることはないので、滑走路 1 を選ぶのが最適• 一般の 𝑁 の場合も同様に示せるので、以降の小課題でも貪欲法が使える

小課題 4 別解• 𝑁 = 2 ならば、𝑑𝑝[𝑖][𝑗]: 滑走路 1,2 で最後に着陸したのが飛行
機 𝑖, 𝑗 のときの離陸数の最大値 という DP ができる
• これは 𝑂 𝑀2 かかるが、Segment Tree で 𝑂(𝑀𝑙𝑜𝑔𝑁) に高速化でき、小課題 4 が通る• ただ、この解法は 𝑁 = 2 限定なので、満点には繋がらない…
• この解法自体けっこう難しい

小課題 5• 𝑁 ≤ 100
• 小課題 4 を、一般の 𝑁 に応用するだけ• 各滑走路について、「最後に着陸で使ったときの終了時刻を 𝐾で割った余り」を保存した配列をつくる• 最も無駄な時間が少なくなる滑走路を 𝑂(𝑁) で選ぶ• ただし、着陸時間が被るものを除くようにする• 𝑂(𝑁𝑀) で解けた• 75 点満点解法• 𝑁 ≤ 105
• 小課題 5 の解法を高速化したい• 「最も無駄な時間が少なくなる滑走路」を高速に求めたい→二分探索！
• ただし、二分探索はソートされていないとできないので、工夫する必要がある• 終了時刻 % 𝐾 の配列は中身の大きさ順に並んでないことに注意

満点解法• multiset という、集合を管理するデータ構造がある• set の重複を許したバージョン• 挿入、削除、検索、二分探索などが 𝑂(𝑙𝑜𝑔𝑁) でできる
• C++ の標準ライブラリにある• multiset で終了時刻 % 𝐾 を管理する• 各 𝐴𝑖 について、終了時刻 % 𝐾 が 𝐴𝑖 % 𝐾 以下のうち最大の滑走路を二分探索で求めれば、使う滑走路が分かる• 𝑂(𝑀𝑙𝑜𝑔𝑁) で解けた• 100 点

満点解法
• 着陸時間が被るものを multiset に入れないように注意• 被らなくなるまで queue に入れておいたりして取り除けば OK

得点分布0点

7点

19点

64点

75点