箸判長　鵜川始陽
最初に統計データを示すことにしよう。正解数ごとのチーム数を表1に示し、各問題の正答チーム数、誤答チーム数、提出数を表2に示す。
また、審判団が想定していた難易度の順に並べた問題番号と正答数を表3に示す。
今年は３年ぶりにオンサイトで開催することができた。審判団も前々日から会場に詰めて問題の仕上げを行ったが、会場の準備や選手が集まってくる様子を目にし、コンテストが始まるというのを実感できた。審判団では最初に、前回（2022年3月開催のICPC 2021）よりも難易度を下げるという方針を確認した。前回はオンライン向けに難しい問題セットにしたが、今年度はオンサイト開催になるためである。結果としては、オンライン開催だった前回よりも多くの問題が解かれ、難易度の設定は適切だったように思える。しかし、表３に現れているように、必ずしも想定難易度の易しい順に解かれている訳ではない。特に、難しい問題として出題したK, F, Iの3問のうちKとFは比較的解かれている一方、中盤問題として出題したH, J, Cは正解が少ない。これらの問題は提出数が少ないので、あまり手をつけられていなかった可能性がある。問題A, B以外の想定難易度はコンテスト中は選手に分からず、他のチームの正解状況だけが分かる。そのため、難しい問題であっても、正解したチームがあるとそれに引きずられて手をつけてしまう傾向がある。今回もそのようなことが起き、その結果、このような「荒れた」コンテストになった。今回は、日本の地区大会では初めてインタラクティプ問題を出題した。どの難易度のインタラクティプ問題を出題するかについては議論があった。全チームにチャレンジしてもらいたいという思いがある一方、インタラクティプ問題には通常問題とは違う入出力の取り扱いが要求され、問題の本質以外にも難しさがある。最終的には、易しい問題の枠で出題し、事前にインタラクティプ問題で気をつける点を周知したり、前日のリハーサルにもインタラクティプ問題を含めるなどで、選手が本質でないところでつまずくのを防いだ。大会の本番では大きなトラプルもなく、ほぼ全てのチームが正解にたどりついた。以下では各問題について、解法を中心に簡単に解説する。
問題A: Hasty Santa Claus
n個の整数の区間が与えられ、それぞれの区間から整数を一つずつ選ぶ問題である。ただし、同じ整数は高々k個しか選んではならない。問題文は、留守を狙ってプレゼントを配るサンタクロースのスケジューリングとして仕立てた。区間は配る先のn軒の家が留守にしている期間で、選択するのはプレゼントを配る日である。サンタクロースは１日に高々に軒しかプレゼントを配ることができない。この問題は、スケジューリングでは典型的な食欲アルゴリズムの解法を想定していた。具体的には、区間の終点が小さい家から順にプレゼントを配る日を割り当てる。このとき、区間の条件と、1日に配れる数の条件を満たす最も早い日を割り当てる。
問題B:  Interactive  Number  Guessing
日本の地区大会では初めてとなるインタラクティプ問題である。通常の問題では、一度に全ての入力を受けとり、それに対する正解を計算して出力するプログラムを作る。一方、インタラクティプ問題では、競技者が作る解答プログラムは審判プログラムに対して質問をして、その返答から次の質問を決めたり、正解を求めたりする。この問題では、解答プログラムが秘密の数nを当てる。解答プログラムは、審判プログラムに対して、0以上の数αを送る。それに対して審判プログラムはn + αを10進数で表記したときの、各桁の数字の総和を返答する。例えばn = 75のとき、解答プログラムがα = 3の質問を送ると、審判プログラムは75 + 3 = 78の各桁を合計した15を返答する。 0 ≤ n,a ≤ 10¹8 – 1なので、a = 0の質問をしてn = 0の場合を除外したうえで、a = 10¹8 – 1から順にαを1ずつ小さくしながら質問をすれば、いつかは正解を見つけることができる。α + n = 10¹8 = 100 · · 0のとき初めて返答が1となるからである。しかし、質問の回数が75回以下と制限されているので、もっと効率のよい質問の戦略を考えなければならない。想定解法では、返答からα + nの計算で繰り上がりが起こったかどうかを判定できることを利用する。もし繰り上がりが起こっていなければ、α + nの各桁の和は、αとnで独立に各桁の和を計算して、それを足した値になる。しかし、もし繰り上がりが起こっていれば、α + nの各桁の和は独立に計算して足した値より小さくなる。これを利用すると、αに1桁だけ0でない数t × 10 ºを指定し、 10cの位が10 −む以上かどうかを判定できる。最初にα = 0の質問をした後、1桁につき4回の質問を使って二分探索すればその桁の数を確定できるので、18桁であれば1 + 4 × 18 = 73回の質問でnの価を求めることができる。
問題C: Secure the Top Secret
平面上のグリッドの格子点に柱を立て、隣接する柱の間のいくつかを壁や開閉可能なシャッターで仕切ったような長方形の建物を考える。4本の柱で囲まれたグリッドの１マスを単にマスと呼ぶことにしよう。この問題では、入口のマス(S)から秘密があるマス(T)への経路を確保しつつ、S以外に外から侵入できるマス(U)からＴへの経路ではどの経路をとってもＵとＴが２枚以上のシャッターで隔てられるように、閉じるシャッターを選択する。ただし、S, Uだけでなく、Tも建物の外周部にある。また、建物の外周部には全て壁が設置されている。一見してグラフ問題だが、この問題で考えるべきグラフは、マスを頂点とするグラフ（これをGとする）ではない。格子点を頂点とし、壁や閉じたシャッターを辺とするグラフC'である。ただし、 G'では建物の外周の壁のうち、S, T, Uのマスの壁は取り除く。これにより、建物の外周部は三つに分割される。これらを外周区間S-Tのように呼ぶことにしよう。問題文ではGに対する条件が与えられているので、これをG ′に対する条件に言い換える。例えば、Ｇで「ＵからTに経路がない」は、G'では「外周区間U-Tから外周区間S-Tか外周区間S-Uに経路がある」と言い換えられる。問題の条件はもう少し複雑で、Ｃで「ＵからＴへの全ての経路が2枚以上のシャッターで隔てられる」（条件1）である。これはC'では「外周区間U-Tから外周区間S-Tか外周区間S-Uに二つ以上経路があり、それらは同じシャッター辺を使わない」（条件1'）と言い換えられる。また、もう一つの条件であるＧで「ＳからＴに経路がある」（条件2）は、G'では「外周区間S-Tから他の外周区間に経路がない」（条件2′）と言い換えられる。条件1′は条件2′を加味すると「外周区間U-Tから外周区間S-Uに二つ以上経路があり、それらは同じシャッター辺を使わない」（条件1″）と簡単にできる。このように言い換えて、最小費用流の問題に帰着する。つまり、シャッターを全て閉じたときのグラフG'を考える。このグラフ上で、外周区間S-Tと、そこから壁(シャッターではない)で連結している壁辺には容量0を、残りの壁辺には容量∞、コスト0を、シャッター辺には容量1、コスト1を設定し、外周区間S-Uから外周区間U-Tへの流量2の最小費用流を求める。
問題D: Move One Coin
ある形に並べられたコインのうち1枚だけを動かして、別の形を作る。そのとき動かすべきコインを求める問題である。コインを動かした後の形は、90度の整数倍回転させた形で与えられるが、4通り試せばよいだけなので、ここでは回転はしていないとして説明する。コインを動かす前と後の形を重ねることができれば、位置の違うコインは簡単に見つかる。しかし、重ねるためには、コインを動かす前後の形で対応する、基準となる点を決める必要がある。もし、この問題が、コインを動かさずに合同な図形を重ねるだけの問題であれば、コインの位置が辞書順で先頭である（ x座標が最小なコインの中でy座標が最小である）コインを基準にできる。つまり、二つの図形の辞書順先頭のコイン同士が同じ位置になるように重ねれば、二つの図形はぴたりと重なる。しかし、この問題ではそのコインを動かす可能性があるので、単純に辞書順先頭のコインを基準にすることはできない。この問題を解く上で鍵となるのは、動かすコインが一つだけであるという条件である。もし辞書順先頭のコインを動かす場合、辞書順で2番目のコインは動かさない。コインを動かした後の形についても、辞書順先頭のコインはもともとは別の位置にあった可能性があるが、その場合は辞書順で2番目のコインは動かしていないことになる。したがって、コインを動かす前後の形のそれぞれで、辞書順で先頭のコインを基準にする場合と２番目を基準にする場合の、合計４通りを試せば、その中に正解がある。正解のときはコインを1枚動かすだけで与えられた形が得られる。基準の選び方は、この他にも様々な方法が考えられる。例えば、コインが十分に多ければ、全てのコインの重心を基準としてもよい。コインを置ける範囲は決まっているので、コインが十分に多いと、その範囲の中でコインが1個動いたぐらいでは重心の位置の座標が1/2も変化しなくなる。一方、コインは整数座標にあるので、重心同士を重ねた後、コインを最も近い整数座標にずらせば、ぴたりと重なる。
問題E:  Incredibly  Cute  Penguin  Chicks
文字列をICPC-ishという条件を満たす文字列に分割するとき、何通りの分割方法があるかを求める問題である。競技プログラミングに慣れていれば、動的計画法を使うのだろうというのは簡単に察しが付くだろう。入力Sの先頭t文字だけを取り出した文字列に対する分割方法の数d(t)を順に計算するのである。d(t)の計算では、t' < tである各tについて、入力のt' + 1文字目からt文字目までを切り取った文字列（以降、S[t' + 1,t]と書く）がICPC-ishかどうか判定する。ICPC-ishであれば、S[t' + 1,t]を一つのICPC-ish文字列とするような分割の方法がd(t')通りある。したがって、そのようなt'全てについてのd(t')を合計すれば、d(t)が計算できる。この方法ではd(t)の計算に入力文字列長nに対してO(n)時間かかり、アルゴリズム全体ではO(n²)時間かかる。しかし、n ≤ 10 6なので、これでは残念ながら時間内に正解を求めることはできない。想定解法では、t'をグループに分類して管理し、S[t' + 1,t]がICPC-ishになるようなd(t')を高速に探せるようにする。Cだけが多いICPC-ish文字列をC-ICPC-ish文字列と呼ぼう。C-ICPC-ish文字列は、ＩとＰを同数含む。そこで、あるｒにおいてt ′を、S[ℓ ′ + 1,t]に含まれるＩの数からＰの数を引いた数よで分類し、集合Ckを作る。t ∈ CoであるS[ℓ + 1,t]がC-ICPC-ish文字列の候補であり、そのうちCが他の文字より多く出現する文字列がC-ICPC-ishである。さらに、C kの要素をS[t' + 1,t]に含まれるCの数からPの数を引いた数の順に並べておけば、C-ICPC-ish文字列を作るt'は連続する。集合C kの添字は、次の文字を読んだときに一斉にずらす。つまり、次の文字が１であれば、C nをC1に、C1をC2にというように1ずつ増やす。実装では全ての集合の添字をずらすのではなく、集合の添字をｋ＋αとしておき、αを増減させることで定数時間で全ての集合の添字をずらす。こうして新しくCoになった集合の要素であるtから作った文字列S[t' + 1,t + 1]が新しいC-ICPC-ish文字列の候補である。順序付き集合Ckの要素をt の代わりにd(t')にし、それをFenwick木を用いて実装すれば、O(log n )時間でC-ICPC-ishを作るtに対するd(t')の総和が求められる。以上を、1-ICPC-ish文字列やP-ICPC-ish文字列についても計算するのだが、この計算は二次元座標系を使って、次のように簡潔に整理できる。文字列を先頭から１文字ずつ読み、それに従って二次元座標の格子点の上を移動する点Aを考える。この点はCを読むと(1, 0)、Iを読むと(0, 1)、Pを読むと(−1, −1)だけ移動する。そして、t文字目まで読んだとき、その座標にd(t)を記録する。同じ点を複数回訪れることもあるが、その時は訪れる度にd(t)を加算する。ここでは、S[t ′ + 1,t]に含まれるＩとＰの数の差は、t ′文字目まで読んだときの点AのY座標とt文字目まで読んだときのY座標の差になる。これが（座標を複数回訪れたときのd(t)は個別に記録せず総和にした）順序付き集合Ckの添字であり、Ckの要素はX軸に平行な直線上に並ぶ。また、点AのX座標がCの数からPの数を引いた数になる。1-ICPC-ish文字列については、Y軸方向について同様に考えればよい。また、P-ICPC-ish文字列については、(−1, −1)方向について考えればよい。ここでは、Y軸（またはX軸）方向にいくらずれているかがIとCの文字数の差を表す。
問題F: Make a Loop
プラスチックのレール部品を連結して環状の線路を作り、その上に列車の模型を走らせるおもちゃで遊んだ人は多いだろう。この問題では、様々な回転半径を持つ90度分の円弧の形状をしたカーブのレール部品だけで線路を作る。与えられたレール部品を全て使って環状の線路を作ることができるかどうかを判定するのが、この問題である。環状の線路を作るには、一周したときに最後のレール部品の終点が最初のレール部品の始点と同じ座標になければならない。これを「位置条件」と呼ぶことにする。いま、1からnの番号を振ったn個のレール部品を使って環状の線路ができているとしよう。そのうちのレール部品を一つ選び、その半径をｒとしたとき、一方の端（始点）が原点、他方の端（終点）が(r.r)となるような座標を考える。また、他のレール部品にも、このレール部品の始点から終点に向かうように環状の線路を一周する方向で向きを付ける。位置条件は、各レール部品の始点と終点の座標の差を求めて合計したときに、X座標もY座標も0になると言い換えられる。どのレール部品も90度の円弧なので、レール部品iの半径をr 。としたとき、その始点と終点の座標の差の絶対値はX座標、Y座標ともr 。となる。符号はそのレール部品がどの向きに置かれているかによる。始点に対して終点が第一象限に来るように置かれているレールの番号の集合をS+.+としよう。同様に、第二象限、第三象限、第四象限をそれぞれS_.+, S_._, S+._としよう。これらを使って、位置条件を次のように書ける。
さらに、最後のレール部品の終点と最初のレール部品の始点を原点で連結するためには、それらが同じ向きに向いていなければならない。これを「向き条件」と呼ぶことにする。原点での線路の向きを0度として、反時計回りに角度を考えよう。S+,+のレール部品には0度の向きの線路を90度にする置き方（反時計回り置き）か、90度の線路を0度にする置き方（時計回り置き）がある。同様にS_.+, S_._, S+._でも反時計回り置きと時計回り置きの二通りの置き方がある。向き条件を満たすには、それぞれの集合の反時計回り置きをしたレール部品の数から時計回り置きをしたレール部品の数を引いた値が等しい必要がある。それには、次の式の条件を満たす必要がある。
これに加えて、環状の線路を作るには、いずれの集合も空であってはならない。
実は、以上の条件が線路が環状になるための必要十分条件である。与えられたレール部品を上の条件を満たすように四つの集合Sz,y (x,y ∈ {+, −})に分割できるなら、環状の線路を作ることができる。このような四分割が存在することは、
を満たすような二通りの分割、つまり、S+,*とS−,*への分割と、S*,+とS*,−への分割が存在することと同値である。なぜなら、例えばS+,+ = S+,* ∩ S+,+とすれば、元の条件を満たすS+,+が得られるからである。二通りの分割は、それぞれ、和が等しく、要素数が偶数になるような分割である。これは部分和問題なので動的計画法で求められる。
問題G:  Remodeling  the  Dungeon
迷路の入口から出口までの最短経路が最も長くなるように壁を一枚壊して一枚追加する問題である。うまく壁を一つ壊すと、入口から出口までの経路が二つできる。元の最短経路と、その途中のマスAで脇道に逸れ、壊した壁を通過して、マスBで元の経路に合流して出口に至る「寄り道経路」である。その後、元の最短経路上のAB間に壁を追加すれば、この寄り道経路が最短経路になる。したがって、寄り道経路が最長となるように壊す壁を決めればよい。ただし、A. Bが同じマスになるような壁、つまり、壁の両側が元の最短経路の同じマスから分岐した先にあるような壁は、壊しても寄り道経路が作れない。ある壁を壊したときの寄り道経路の長さは、入口から壁の入口側（壁に隣接するマスのうち元の最短経路からマスAで分岐した先の側）までの長さと、出口から壁の出口側までの長さの和に、壊した壁を通過するコスト１を加えることで計算できる。壁に隣接する二つのマスC. Dのうち、どちらが入口側かは分からないが、入口からCまでの長さとDから出口までの長さの和（αとしよう）か、入口からDまでの長さとCから出口までの長さの和（βとしよう）のどちらか短い方が寄り道経路の長さになる。もし、α = βだったときは、寄り道経路が作れないような壁である。したがって、全ての壁についてαとβを計算し、α ≠ βの中でmin(α,β)が最大となる壁を探せばよい。なお、壁ごとに両側のマスの入口や出口からの距離を毎回計算すると、計算が間に合わない。想定解法では、あらかじめ入口と出口それぞれから迷路全体を探索して、各マスの入口からの距離と出口からの距離を計算しておく。
問題H:  Cake  Decoration
整数L, R, Xに対して次の条件を満たす異なる整数の組(d,c,r,b)の数を求める問題である。 1.  L ≤ d + c < R 2. dcrb ≤ X 3.  (d + 1)crb > Xかつd(c + 1)rb > Xかつdc(r + 1)b > Xかつdcr(b + 1) > X整数を小さい順に並べて、A, B, C, Dと名前を付け直そう。そうすると2以降の条件は2′.  ABCD ≤ X 3′.  ( A + 1)BCD > XかつA(B + 1)CD > XかつAB(C + 1)D > XかつABC(D + 1) > Xと書ける。条件１はｄとｃがＡからＤのどれに割り当てられているか分からないので、12通りそれぞれの場合を分けて場合の数を計算する。ただし、dとcを逆に割り当てても場合の数は同じなので、６通り計算して２倍すればよい。また、rとrの割り当ても２通りあるので、求めた場合の数を4倍して合計すると、正解が得られる。それぞれの場合の数を求めるために、条件の式を変形しよう。Ａ＜Ｂ＜Ｃ＜Ｄなので、条件3′の左辺の中ではABC ( D + 1)が最小になる。したがって、条件2′と3′は次のようにまとめられる。 ABCD < X < ABC(D + 1) A, B, C, Dは整数なので、この式はさらに
と言い換えられる。つまり、A, B, Cが決まるとDは一つに決まる。ただし、そのようなA, B, C, Dは条件1を満たさないこともある。想定解法では、A, Bを全通り列挙し、それぞれについてDが存在するCの範囲を求める。 Cの範囲の求め方はｄとｃをAからDのどれに割り当てるかによって異なる。ここでは、d = A, c = Cの場合だけ説明する。このときL ≤ A + C < Rを満たす必要がある。Cの最小値を与える条件はL ≤ A + CとB < Cである。A, Bは全通り列挙するので、具体的に分かっている。したがって、二つの条件をC ≥ max( B + 1, L − A)とまとめると、右辺は計算できる。次に、Cの最大値を与える条件はＣ＜Ｄである。ＣはＤ＝Ｃ＋１のとき最大になるので、ＣはＣ(Ｃ＋１) ≤孟を満たす範囲で大きくなれる。そのようなCの最大値は二分探索で求められる。これ以外の5通りのdとcの割り当てでも同様に考えて各A, BについてCの範囲を求め、それを合計する。
問題I:  Quiz  Contest
極めて効率的なアルゴリズムを構築する必要がある、非常に難しい問題である。解法は以下のようなO(m log n log m)時間の分割統治のアルゴリズムを想定していた。参加者全体の集合をU = {1,...,n}とする。Uの任意の部分集合Sについて、Sに属する参加者が正解するα(S) = ∑ iεs α,問の並べ方α(S)!通りのうち、Sに属する参加者のみで大会を行った場合にi問目で勝負の決着がつくような並べ方の数をf (S,i) (i = 1,...,α(S))と書こう。すると、二つの重なりのない参加者の集合ＳとＴについて、f(S, ·)とf(T, ·)の値の一覧が既知ならば、f(SUT, ·)の価の一覧が次の式で計算できる。
これは、累積和などを使用して整理すると、シンプルな畳み込みに帰着でき、FFTアルゴリズムを用いるとO(α(SUT) log α(SUT))時間で計算できる。したがって、n個の単元集合{1},..., {n}から始め、α(S)の値が最小の２集合の併合を繰り返すことで、O(mlog n log m)時間でf(U,i)を計算できる。なお、ƒ({i}, j)はi = jのとき1、それ以外は0になる。次に、Uの任意の部分集合Sについて、α(U)間の並べ方の中で『Sに属する参加者が正解する問題のみを取り出して部分列を構成し、その参加者のみで大会を行った場合にも問目で決着がつく』ような並べ方のうち、全員で大会を行った場合にもSに属する参加者が勝利するような並べ方の数& g(S, i ) ( i = 1, . . ., a(S))と書こう。すると、二つの重なりのない参加者の集合SとTについて、 f(T, ·)とg(SUT, ·)が既知なら、g(S, ·)が次の式で計算できる。
これもFFTアルゴリズムを用いることでO(a(SUT) log a(SUT))時間で計算できる。したがって、 g(U,i) = 1 (i = 1,...,α( U ))から始めて、上とは逆の過程で分割を繰り返すことで、O(m log n log m)時間でg({j}, ·) (j = 1, . . ,n)を計算できる。これを用いて、参加者iが勝つ並べ方はm! · g({i}, b i )通りと計算できる。
問題J: Traveling Salesperson in an Island
多角形とその周上の点がいくつか与えられ、それらの点を全て通り、多角形の外に出ない最短の巡回路を求める問題である。この問題では、与えられた点を時計回り（または反時計回りに）に回る巡回路が最短となる。もし時計回りでない巡回路が最短であるとすれば、その巡回路では経路が交差する。その交差点で経路を入れ替えれば、経路の長さを変えずに、時計回りの巡回路が作れる。したがって、最短の時計回りの巡回路を構成すればよい。周上の2点間の最短経路は、その2点を結ぶ線分、1点と多角形の頂点を結ぶ線分、および多角形の頂点同士を結ぶ線分で構成される。これらのうち多角形の外に出ない線分を残して、最短経路を求める。
問題K: New Year Festival
イベントのスケジュールを決める問題である。イベントごとにそのイベントを開始する時刻の関数としてコストが与えられている。コスト関数は連続な区分線形関数になっており、入力ではその頂点が与えられる。また、それぞれのイベントには所要時間が設定されている。二つのイベントの開催時間が重ならないようなスケジュールのうち、コストが最小となるものを求める問題である。あるイベントが終わると、隙間を空けず、直ちに次のイベントを開始することができる。このように、隙間なく連続して行われているようなイベントの並び全体を「イベント列」と呼ぶことにしよう。一般に、スケジュールはいくつかのイベント列に分解できる。次の理由から、最適解（の一つ）では、どのイベント列についても、イベント列を構成するイベントの少なくとも一つの開始時刻が、そのイベントのコスト関数のいずれかの頂点上にある。そうでないイベント列を含む最適解があるとする。どのイベントの開始時刻も頂点上にない場合、全てのイベントの開始時刻はコスト関数が線形な区間にある。したがって、コスト関数の傾きを考えることができる。コスト関数の傾きを合計して0でなければ、イベント列全体をずらすことで、合計コストをより小さくでき、最適性に反する。傾きの合計が0であれば、合計コストを変えずに、いずれかのイベントのコスト関数の傾きが変わるまで、つまり、いずれかのイベントの開始時刻が頂点上に来るまでイベント列全体をずらすことができる。ずらしている途中で隣のイベント列とぶつかったときは、連結した列全体について同様に考えることができる。コスト関数の頂点のうち、そのイベントの開始時刻になっている頂点を「イベント付き頂点」と呼ぶことにする。時刻の早い順にイベント付き頂点を選びながら、イベント付き頂点の間にイベントをうまく配置すれば、合計コストが最小となるスケジュールが得られる。想定解法では、直前のイベント付き頂点と既に配置したイベントの集合との組を状態として、最小の合計コストを求める動的計画法を用いる。状態の遷移では、次のイベント付き頂点と、間に追加するイベント集合の選び方の全ての組合わせを考えてコストが最小のものを選ぶ。これをそのまま計算すると時間がかかるので、前計算で全ての頂点の組と、全てのイベントの選び方について、その頂点間に選んだイベントを全て配置する最小の合計コストの表（頂点間にイベントを配置するコストの表）を求めておく。この表を使えば、この動的計画法の部分はO(M²3")になる。ここで、Mは全てのコスト関数の頂点数の合計である。頂点間にイベントを配置するコストの表も次のようにO(M²3n)時間で計算できる。最初の考察から、二つの頂点から内側に向かって隙間なくイベントを配置したスケジュールの中に最適解がある。そこで、さらに、頂点とイベントの集合が与えられたとき、頂点から前（後）に向かって与えられたイベントを隙間なく配置するときの最小コストを前計算しておく。これはO(Mn2n)で計算できる。各２頂点間で、この結果を参照しながら、各イベントを前に付ける、後ろに付ける、選ばないの３通り全てを試す。これにより、選んだイベントを2頂点間に配置する最小コストが計算できる。