JOIG2021/2022 春合宿
Day1 – JOIG ツアー(JOIG Tour)
解説： 米内山 匠実

問題概要
 東西に伸びる直線上に J, O, I, G の4種類の文字が 𝑁 個置いてある。各文字には座標(西からの距離)が定まっている。
 クエリが 𝑄 個与えられる。𝑗 番目のクエリは以下の通り。
・座標 𝑆𝑗 と 𝑇𝑗 が与えられる。𝑆𝑗 , ‘J’, ’O’, ’I’, ‘G’, 𝑇𝑗 の順に巡る経路の最短距離を求めよ。J~G の各文字はどこにあるものでも良い。

制約(満点を狙う場合)
 置いてある文字の数 𝑁 ≤ 100000
 クエリの個数 𝑄 ≤ 100000
 各文字の座標、及び始点と終点 𝑆𝑗 , 𝑇𝑗 は 1015 以下(とにかく大きい) 各文字は1つ以上存在
 各文字の座標は相異なる&昇順に与えられる

 (𝑆𝑗 , 𝑇𝑗 ) の組み合わせは各クエリで異なる例(入出力例1)
クエリ12

S1

‘J’ ‘O’ ‘G’ ‘I’ ‘O’
1T 1
合計: 72‘G’‘J’

例(入出力例1)
クエリ2S‘J’ ‘O’ ‘G’ ‘I’ ‘O’12
合計: 121

T3

‘G’
5‘J’

考え方①
 全探索
考えられる全ての経路のうち最短のものを求めたい。
→ 経路を全探索！
 J, O, I, G の選び方を全て調べる
それぞれの文字の個数を 𝑁𝐽 , 𝑁𝑂 , 𝑁𝐼 , 𝑁𝐺 とすると、それらの積の通り数だけ選び方がある。
 それぞれの選び方について、経路の長さを考える

始点と終点と各文字の位置が決まるから、各経路の長さは簡単！
その経路のうちの最短を求めればOK。

考え方①
 J, O, I, G の選び方を全て調べる
それぞれの文字の個数を 𝑁𝐽 , 𝑁𝑂 , 𝑁𝐼 , 𝑁𝐺 とすると、それらの積の通り数だけ選び方がある。
小課題1を考えると……
全ての文字の個数は合わせて 𝑁 ≤ 80
→ 選び方は高々 204 通りくらい。

クエリの数は Q ≤ 10 なので、小課題1は解ける。

考え方②
 全探索では、小課題2以降は間に合わない……

→ 全てを探索する必要はあるのか？
 【重要】求めたいのは最短経路のみ
 それぞれの文字にたどり着くための最短経路をメモしながら進めばいい。

考え方②23

3

‘J’

‘O’

2

S
4

‘I’

‘J’

‘O’

77

‘G’

‘I’
8T

8

‘G’

JからO,I,Gの順に見ていく考え方② 文字の種類ごとに分けておく。
 J を見る時はそれぞれ 𝑆 からの距離を記録
 O を見る時は、「ある J を経由した時の距離」を全ての J について探索し、最短を記録
 I を見る時は、「ある O を経由した時の距離」を全ての O について探索し、最短を記録
 G を見る時は、「ある I を経由した時の距離」を全ての I について探索し、最短を記録
 最後に、全ての G について、そこまでの最短と 𝑇 からの距離を合わせて最短を決定。

考え方②
 計算量？
1クエリごとに、全ての J-O、O-I、I-G の組み合わせを調べることになる。(それぞれ 𝑂(𝑁 2 ) )それと、 𝑆 から各 ’J’、各 ’G’ から 𝑇 までの組は 𝑂(𝑁)→ 合わせて 𝑂(𝑁 2 )クエリ 𝑄 個だと 𝑂(𝑁 2 𝑄) ……小課題3まで解けた！

(J-O、O-I、I-G の組は実際は 𝑁 2 より結構少ない)考え方➂ ここまで考えてきたのって、グラフっぽい？
 J-O, O-I, I-G 間をグラフの辺と見なし、各文字+始点終点をグ
ラフの頂点と見なせば……
233‘J’‘O’2S4‘I’

‘J’

‘O’

77‘G’

‘I’
8T8‘G’

考え方➂
 ここまで考えてきたのって、グラフっぽい？
 J-O, O-I, I-G 間をグラフの辺と見なし、各文字+始点終点をグ
ラフの頂点と見なせば……

33‘J’
‘O’

2S2‘J’

‘O’

4

‘I’

77‘G’

‘I’
8T

8‘G’

考え方➂
 グラフの最短経路と言えば……ダイクストラ！
 ということで、頂点と辺を設定し、ダイクストラをする。
 クエリごとに始点と終点の頂点は決める必要があるが、それ以外は同じグラフである。
 頂点は(始点と終点を除き) 𝑂(𝑁) 個、辺は 𝑂 𝑁 2
 よって、始点と終点を決めた1回の探索では 𝑂(𝑁 2 ) 結局改善にはならない……

考え方➂の補足
 最短経路をグラフ化して考えるアプローチは、しばしば新たな解法の筋道になる。
 ダイクストラの計算量は 𝑂(𝐸 + 𝑉 log𝐸) ただし 𝑉 は頂点数、𝐸は辺数。
 今回は辺が多いので 𝐸 がネックになった。
 グラフ化してダイクストラをするのではなく、単純にDPをすれば O(log𝐸) の分を省ける場合もある。
 結論：柔軟に考えよう！

考え方④
 グラフで考えると 𝑂(𝑁 2 ) の辺を用意することになった。

でも……動き方ってそんなにたくさん考える必要あるの？

考え方④
 例えば小課題5のような状況(J しか選ぶ余地がない)で考えると分かりやすい。

S
‘J’

‘J’

‘J’

‘J’

‘O’
‘I’
‘G’T

考え方④
 例えば小課題5のような状況(J しか選ぶ余地がない)で考えると分かりやすい。
途中の別の ’J’ を見ればいい

東側で一番近い‘J’ (東隣の‘J’)だけ考えればOK!

こんな動き方は考えなくて良いS
‘J’

‘J’

‘J’

‘J’

‘O’‘I’‘G’T

考え方④ 例えば小課題5のような状況(J しか選ぶ余地がない)で考えると分かりやすい。
 「𝑆 から見て西隣の ’J’ か、東隣の ’J’ を選ぶ、2つの場合だけ考えればいい」ことに気付けば小課題5は解ける。
 西隣 or 東隣の ’J’ は二分探索(lower_bound, upper_bound)で求められる。(後で補足)
 計算量は1クエリあたり 𝑂(log𝑁) であり、全体で 𝑂(𝑄 log𝑁) なので小課題5の制約に間に合う。

考え方④
 小課題6も同様。𝑇 から見て西隣の ’G’ か東隣の ’G’ かだけ考えればいい。

S
‘J’

‘J’

東隣がなければ無視

‘J’
‘O’
‘I’

‘G’

‘G’T

考え方④
 小課題6も同様。𝑇 から見て西隣の ’G’ か東隣の ’G’ かだけ考えればいい。
 𝑆 側の選び方と 𝑇 側の選び方は互いに独立なので、それぞれ最小となるものを選べばいい。
 計算量は1クエリあたり 𝑂(log𝑁) であり、全体で 𝑂(𝑄 log𝑁) なので小課題6の制約に間に合う。

考え方④
 西隣・東隣だけでいい、という考え方を発展させる。
 小課題7のように、’I’ も ’G’ も選べる場合は、𝑇 から見て西隣と東隣の2つの ’G’ について、さらに西隣の ’I’ と東隣の ’I’ を考えればいい！

S‘J’
‘O’
‘I’

‘I’

‘I’ ‘I’‘G’‘I’‘G’ ‘G’T考え方④ 西隣・東隣だけでいい、という考え方を発展させる。
 小課題7のように、’I’ も ’G’ も選べる場合は、𝑇 から見て西隣と東隣の2つの ’G’ について、さらに西隣の ’I’ と東隣の ’I’ を考えればいい！
 考えるべきは 𝑇 からの4通りの「隣の隣」までの行き方と 𝑆 からの2通りの「隣」までの行き方。
 これも計算量は1クエリあたり 𝑂(log𝑁) であり、全体で𝑂(𝑄 log𝑁) なので制約に間に合う。

考え方④
 ここまで来れば、同様に考えて……
 満点解法𝑆 から両隣の ’J’ までの経路長を求め、さらにその2つの ’J’ について、両隣の ’O’ までの経路長を求め、さらにその4つの ’O’ について、両隣の ’I’ までの経路長を求め、さらにその8つの ’I’ について、両隣の ’G’ までの経路長を求め、その16通りの ’G’ について、𝑇 までの経路長を求め、以上16通りで最も短かったものを出力すれば良い考え方④
 西隣・東隣を求めるパート→ lower_bound, upper_bound で 𝑂(log𝑁) 1回のクエリでは、16通り(定数倍程度)の経路しか考えず、その経路は西隣・東隣を4回求めるだけでいいから、計算量は𝑂(log𝑁)
 𝑄 回のクエリでは、𝑂(𝑄 log𝑁) →十分間に合う実装
 lower_bound, upper_bound について
Vector や set などのデータ構造には、ある値以上となる最小の要素を二分探索で求める標準機能が備わっている。それがlower_bound である。また、ある値を超えるものを知りたいならupper_bound が使える。

説明すると長くなるし、説明はネットにたくさん転がっているので、そちらを参照してもらいたい。
キーワード：イテレータ (位置を指し示すもの)

実装//例えば、Sの西隣・東隣を探索するコード
long long S;
vector<long long> J;//配列Jには、文字Jの入っている位置が記録されているとしよう
auto it = lower_bound(J.begin(),J.end(),S);
long long L,R;
if(it == J.begin()) L = -1; //西隣が存在しないelse{it--;
L = *it;}it = upper_bound(J.begin(),J.end(),S);
if(it == J.end()) R = LLONG_MAX; //東隣が存在しない
else R = *it;

実装
 ちなみに、自力で二分探索を実装するのもあり自分で書けることもそれはそれで重要。
 二分探索を諦めても点はもぎ取れる
想定解のうち二分探索だけできなくても、小課題4は取れる！
 16通りを全探索する方法についてbit演算を用いることもできるが、西隣か東隣かという2択が4つあるので4重ループにしたり、for文をあきらめて愚直に16行書いても良い。

余談
・二分探索(lower_bound, upper_bound)を扱えるようになろう。
・テクニックが追い付かないなら、部分点を取ろう。

・「結局一番近いところだけ調べればいい」という考え方は頻出。

得点分布
3210041440100