A. Depot Rearrangement

TL: 2 s
ML: 64 MB

ある会社は

N

個の店舗を運営しており，各店舗で

M

個の相異なる商品を販売している．この会社はある

1

つの大きなデポを有しており，商品は配達される前にこのデポで箱詰めされる．各店舗が受け取る各商品の個数は同じである．

さて，この会社は商品をコンテナに箱詰めし、どの商品が入っているかがわかるようにラベル付けする．商品は

1

から

M

までの識別番号で番号付けされている．そして，箱詰めが終了したとき，デポには

N \times M

個のコンテナが存在し，各商品について，ちょうど

N

個のコンテナにその商品のラベルが貼られている．デポは狭い建物にあるため，コンテナは

1

列に配置されている．

配達の速度を上げるため，デポの管理者はコンテナを並べ替えようとしている．商品の店舗への配達は各店舗についてただ

1

つのトラックにより行われ，各トラックは各商品のコンテナを

1

個ずつ運送するため，適切なコンテナの配置が必要となる．列の先頭

M

個のコンテナには相異なるラベルが貼られている必要があり，続く

M

個のコンテナにも相異なるラベルが貼られている必要があり，以降も同様である．

残念なことに，列の最後尾にはコンテナを保持しておけるフリースペースがただ

1

つしかない．このため，コンテナの並べ替えは，コンテナをフリースペースに移動させることを繰り返して行われる必要がある．並べ替えの後，フリースペースは列の最後尾にある必要がある．

あなたの目的は，コンテナの移動回数が最小となるように並べ替えを実現することである．

課題

コンテナの移動回数が最小となる並べ替えの手順を求めるプログラムを作成せよ．

入力

標準入力の

1

行目には

2

個の整数

N

と

M

が書かれており，

N

(1 ≦ N ≦ 400)

は店舗の個数を，

M

(1 ≦ M ≦ 400)

は商品の個数を表す．

2

行目には

N \times M

個の整数が書かれており，コンテナの初期配置を表す．各商品の識別番号

x

(1 ≦ x ≦ M)

はこの行にちょうど

N

回ずつ登場する．

出力

標準出力の

1

行目には，並べ替えに必要なコンテナの移動回数の最小値を表す整数

S

が書かれる (小課題 A)．続く

S

行は並べ替えの手順を示している (小課題 B)．各行には

2

つの整数

x

y

が書かれ，位置

x

のコンテナが位置

y

に移動されることを表す．
コンテナの位置は

1

から

N \times M + 1

までの整数で番号付けされており，初め，位置

N \times M + 1

はフリースペースである (すなわちどのコンテナもこの場所にはない)．コンテナの位置

x

から位置

y

への移動は，それまでの移動により位置

y

がフリースペースとなっていたときに限り有効である．
小課題 A のみを解く場合，

1

行目のみを出力すれば十分である．

複数の解が存在する場合は，そのうちどれを出力してもよい．

入出力例

入力例	出力例
`5 6` `4 1 3 1 6 5 2 3 2 3 5 6 2 1 4 5 6 4 1 3 2 4 5 5 1 2 3 4 6 6`	`8` `9 31` `18 9` `10 18` `4 10` `31 4` `30 31` `24 30` `31 24`

配点

1

テストケースにつき

5

点であり，満点は

100

点である．

(テストケース
$1$ 〜
$3$ )
$N, M ≦ 10$
(テストケース
$4$ )
$N ≦ 100, M ≦ 10$
(テストケース
$5, 6$ )
$N, M ≦ 201$
(テストケース
$7, 8$ )
$N, M ≦ 300$
(テストケース
$9$ 〜
$12$ )
$M ≦ 160$
(テストケース
$13$ 〜
$20$ ) 追加の制約はない．

小課題 A のみに正解した場合，配点の

40 %

を得ることができる．

B. Workshop

TL: 4 s
ML: 1024 MB

N

人の魔法使いたちが集まって親睦を深め，お互いの魔法を共有する宴会を開こうとしている．この宴会では，

1

日中ゲームを行う．

ゲームは巨大な会議室で行われる．この会議室には

N

個の席がある円卓がある．各席や各魔法使いはそれぞれ区別されない．魔法使いたちはゲームの進行中 何も発言しない．

ゲームは以下の

3

ステップで行われる．

朝、魔法使いたちは円卓の周りに座る．各席にはそれぞれ，何も書かれていない紙
$1$ 枚と，
$0$ 以上
$N - 1$ 以下の整数が書かれた紙
$1$ 枚が置かれている．各紙に書かれた整数は 互いに異なる．魔法使いたちは，自分の紙に書かれた整数と，円卓で自分の右隣に座る人の紙に書かれた整数を見ることができる．これをもとに、魔法使いたちは，何も書かれていない紙に
$0$ 以上
$10^{9}$ 未満の整数を書く．なお，この整数は他の魔法使いに見られないよう気を付けながら書く．その後，今整数を書いた紙を折り畳んで席の上に置き，はじめから整数が書かれていた紙を持って会議室を去る．
昼，魔法使いたちは円卓の周りに座る．各席にはそれぞれ，何も書かれていない紙
$1$ 枚と，朝に自分が整数を書いた紙
$1$ 枚が置かれている．魔法使いたちは，自分の紙に書かれた整数と，円卓で自分の 左隣および右隣 に座る人の紙に書かれた整数を見ることができる．これをもとに，魔法使いたちは，何も書かれていない紙に
$0$ 以上
$10^{9}$ 未満の整数を書く．なお，この整数は他の魔法使いに見られないよう気を付けながら書く．その後、今整数を書いた紙を折り畳んで席の上に置き，朝に自分が整数を書いた紙を持って会議室を去る．
夜，魔法使いたちは円卓の周りに座る．各席にはそれぞれ，何も書かれていない紙
$1$ 枚と，昼食時に自分が整数を書いた紙
$1$ 枚が置かれている．魔法使いたちは，自分の紙に書かれた整数と，円卓で自分の 左隣および右隣 に座る人の紙に書かれた整数を見ることができる．これをもとに，魔法使いたちは，何も書かれていない紙に
$0$ 以上
$40$ 未満の整数を書く．なお，この整数は他の魔法使いに見られないよう気を付けながら書く．その後、今整数を書いた紙を折り畳んで席の上に置き，昼に自分が整数を書いた紙を持って会議室を去る．

会議室を去ると，手に持っている紙は魔法の力によって消え，魔法使いたちは会議室で行ったすべての行動を忘れる．魔法使いたちが朝，昼，夜に座る席の位置は同じである．

魔法使いたちは

N

の値を知らないが，

N

は

10

以上

100 000

以下であるという事実を知っている．

ゲームが終了した後，イベント運営のスタッフは席の上に置かれた紙を全て整理する．魔法使いたちがゲームに勝利するためには、円卓上の隣り合った席にある紙に書かれた数字が互いに異なる必要がある．また，ゲームが終了した時点で（すなわち夜が終わった後に），紙に書かれた数ができるだけ小さな値であると良い．

魔法使いたちはゲームの進行中には何も話せないが，ゲームが始まる前に共通の戦略を相談することができる．あなたは魔法使いたちのために，最終的にできるだけ小さい数を紙に書けるような戦略を考案する必要がある．

実装の詳細

あなたは以下の関数を実装する必要がある．

void init()

この関数はただ一度だけ，他のすべての関数が呼び出される前に呼び出される．
その後の関数呼び出しに必要な前処理やグローバル変数の設定がある場合は，この関数内で実装することができる．

int morning(int my_num, int right_num)

my_num: 朝，魔法使いの紙に書かれた整数
right_num: 朝，右隣の魔法使いの紙に書かれた整数
この関数は，魔法使いが朝に何も書かれていない紙に書くべき整数を返す必要がある．返り値は
$0$ 以上
$10^{9}$ 未満でなくてはいけない．
この関数の返り値は，my_num と right_num の値にのみ依存する必要がある．
この関数は最大で
$2 000 000$ 回呼び出される．

int afternoon(int left_num, int my_num, int right_num)

left_num: 昼，左隣の魔法使いの紙に書かれた整数
my_num: 昼，魔法使いの紙に書かれた整数
right_num: 昼，右隣の魔法使いの紙に書かれた整数
この関数は，魔法使いが昼に何も書かれていない紙に書くべき整数を返す必要がある．返り値は
$0$ 以上
$10^{9}$ 未満でなくてはいけない．
この関数の返り値は，left_num と my_num と right_num の値にのみ依存する必要がある．
この関数は最大で
$2 000 000$ 回呼び出される．

int evening(int left_num, int my_num, int right_num)

left_num: 夜，左隣の魔法使いの紙に書かれた整数
my_num: 夜，魔法使いの紙に書かれた整数
right_num: 夜，右隣の魔法使いの紙に書かれた整数
この関数は，魔法使いが夜に何も書かれていない紙に書くべき整数を返す必要がある．返り値は
$0$ 以上
$40$ 未満でなくてはいけない．
この関数の返り値は， left_num と my_num と right_num の値にのみ依存する必要がある．
この関数は最大で
$2 000 000$ 回呼び出される．

コードの提出時に，入出力関数を実行しないようにすること．

morning，afternoon，evening 関数の返り値は，与えられたパラメータのみに依存する必要がある．これらの関数を同じパラメータ値で複数回呼び出したときに異なる値を返した場合，ゲームの勝敗とは無関係に誤った結果として扱われる．各テストケースは，

1

つまたは複数の独立したゲームから成り立っている．morning，afternoon，evening 関数が順番に呼び出されることは保証されていないが，関数の返り値をもとに，課題で示された方法に従ってゲームが進行することは保証されている．

各テストケースについて，あなたのプログラムは

2

回実行される．コンテストシステム上での実行時間は，

2

回のプログラム実行の実行時間の合計によって測定され、メモリ使用量も同様に

2

回のプログラム実行のメモリ使用量の合計によって測定される．制限時間と制限メモリは、2回の実行結果の合算を基準に設定されている．morning，afternoon，evening 関数の呼び出し回数の制約も、2回の実行での呼び出し回数の合計を基準にしている．

実際の提出時には，最悪の場合でも採点プログラムが通常

2

秒以内で実行されると仮定しても構わない．

制約

$10 ≦ N ≦ 100 000$
各テストケースにおいて，morning 関数は最大で
$2 000 000$ 回呼び出される．
各テストケースにおいて，afternoon 関数は最大で
$2 000 000$ 回呼び出される．
各テストケースにおいて，evening 関数は最大で
$2 000 000$ 回呼び出される．

小課題

(
$5$ 点)
$N ≦ 40$
(
$95$ 点) 追加の制約はない．

もしテストケースのいずれかで，morning，afternoon，evening 関数の返り値をもとにゲームが進行されても魔法使いたちが勝利できない場合，この小課題の点数は

0

点となる．

小課題

2

には部分点がある．この小課題に関して，evening 関数の返り値の最大値に
$1$ を加えたものを

m

とする．この部分点に関して，あなたの点数は以下の表の通りである．

条件	点数
$10 ≦ m ≦ 40$	$46 - m$
$m = 9$	$38$
$m = 8$	$41$
$m = 7$	$46$
$m = 6$	$52$
$m = 5$	$64$
$m = 4$	$76$
$m ≦ 3$	$95$

入出力例

N = 10

であり，朝それぞれの魔法使いの紙に書かれた整数が反時計回りに

[3, 8, 7, 0, 2, 4, 5, 9, 6, 1]

であった場合を考えよう．

採点プログラムは以下のような呼び出しを行う．

morning(8, 7) = 1
morning(6, 1) = 4
morning(1, 3) = 6
morning(3, 8) = 0
morning(7, 0) = 2
morning(0, 2) = 3
morning(2, 4) = 2
morning(4, 5) = 3
morning(5, 9) = 1
morning(9, 6) = 2

このとき，朝が終わった後にそれぞれの魔法使いの紙に書かれた整数は

[0, 1, 2, 3, 2, 3, 1, 2, 4, 6]

となっている．この値に基づき，採点プログラムは以下のような呼び出しを行う．

afternoon(2, 3, 2) = 3
afternoon(1, 2, 3) = 2
afternoon(2, 4, 6) = 2
afternoon(3, 2, 3) = 1
afternoon(2, 3, 1) = 5
afternoon(0, 1, 2) = 4
afternoon(6, 0, 1) = 3
afternoon(3, 1, 2) = 3
afternoon(4, 6, 0) = 1
afternoon(1, 2, 4) = 0

このとき，昼が終わった後にそれぞれの魔法使いの紙に書かれた整数は

[3, 4, 2, 3, 1, 5, 3, 0, 2, 1]

となっている．この値に基づき，採点プログラムは以下のような呼び出しを行う．

evening(5, 3, 0) = 0
evening(4, 2, 3) = 0
evening(1, 3, 4) = 0
evening(3, 1, 5) = 0
evening(0, 2, 1) = 0
evening(2, 3, 1) = 1
evening(1, 5, 3) = 1
evening(3, 0, 2) = 1
evening(2, 1, 3) = 1
evening(3, 4, 2) = 1

このとき，夜が終わった後にそれぞれの魔法使いの紙に書かれた整数は

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

となっている．どの隣接する

2

つの数も異なるため，この場合魔法使いたちはゲームに勝利する。

m

の値は

2

である．

各関数の呼び出し順序は、実際のテーブルの配置順序とは無関係であることに留意すること．採点プログラムは morning 関数の引数が固定された順列であり，afternoon および evening 関数の引数がmorning および afternoon 関数の返り値として定義されることを満たす範囲で，関数の呼び出し順序をランダムに混ぜることができる．また、これ以外にも morning afternoon evening 関数が互いに通信できないようにするための様々な仕組みが実装されているかもしれない．

採点プログラムのサンプル

採点プログラムのサンプルは，最初の行でテストケースの数

T

を入力する．その後，

T

回次のような情報を入力する．

$1$ 行目:
$N$
$2$ 行目:
$A [0] A [1] \dots A [N - 1]$

A [i]

はゲームが開始される前にテーブルに配置された紙に書かれた整数を，任意の位置から反時計回りの順序で並べた配列である．

0 ≦ A [i] ≦ N - 1

であり、すべての

A [i]

は互いに異なると仮定される。採点プログラムのサンプルは入力の正当性を確認しない．

採点プログラムのサンプルは，各テストケースに対して次のように出力する．

もし morning 関数の返り値が
$0$ 以上
$10^{9}$ 未満でない場合、
$1$ 行目に Wrong Answer [1] を出力する．
もし afternoon 関数の返り値が
$0$ 以上
$10^{9}$ 未満でない場合、
$1$ 行目に Wrong Answer [2] を出力する．
もし evening 関数の返り値が
$0$ 以上
$40$ 未満でない場合、
$1$ 行目に Wrong Answer [3] を出力する．
もし evening 関数の返り値がテーブル上の隣り合う
$2$ つの位置に対して同じ値を返す場合，
$1$ 行目に Wrong Answer [4] を出力する．
それ以外の場合，
$2$ 行を出力する．
$1$ 行目には Correct! と書かれている．
$2$ 行目には m = 10 のようにすべてのテストケースの
$m$ の値が書かれている．

Wrong Answer を出力した場合、採点プログラムのサンプルは即座に終了する．Sample grader は実際の採点プログラムとは異なる可能性があることに注意すること．

C. Ringroad 2

TL: 2 s
ML: 1024 MB

KOI 市は

N

個の交差点と

N - 1

本の双方向に移動可能な道路で構成されており，任意の異なる

2

個の交差点間を道路のみを使用して移動することができる．つまり、都市の道路ネットワークは木構造を形成している．道路は

2

次元平面上にあり，

2

本の道路が端点以外の位置で交差することはない．各道路には

0

以上の整数の重みが存在する．

数十年前までは小さな都市であった KOI 市も，人々が流入し，規模が大きくなるにつれて急速に拡大し始めた．急速に拡大が進む中，市長は行政上の便宜のために交差点に

0

以上

N - 1

以下の番号を割り当てた．この番号システムは，次のような性質を満たす．

交差点
$0$ は都市の中心であり，
$2$ つ以上の道路と隣接することが保証されている．
交差点に割り当てられた番号は，交差点
$0$ を根とする木の先行順序（Preorder）の
$1$ つである．
すべての交差点について，隣接する交差点の中で最も番号の小さい交差点を考える．この交差点を基準にして，反時計回りに隣接する交差点の番号を並べたとき，番号は増加する．

多くの人々が KOI 市に流入する中で，交通渋滞の問題が悪化している．市長はこれを解決するために，交通インフラの脆弱な都市を外周の循環道路で結ぶことにした。KOI 市にあるすべての交差点のうち，ただ

1

つの道路と隣接する交差点の番号を昇順に並べたリストを

V [0], V [1], \dots, V [K - 1]

とする．市長は，すべての

0 ≦ i ≦ K - 1

に対して、交差点

V [i]

と交差点

V [(i + 1) mod K]

を双方向に移動可能な道路で接続した．各道路の重みは

0

以上の整数

W [i]

である．番号システムの特性から，

2

つの道路が端点以外の位置で交差しないように外周の循環道路を構築できることがわかる．

KOI 市を拠点とする悪名高い犯罪組織 Dlalswp は、市民に多大な被害をもたらしている．市長は犯罪組織 Dlalswp を摘発するために情報員を投入した．情報員たちの情報によれば，犯罪組織 Dlalswp は 奇数長の単純なサイクル を犯罪地域として設定し，そのサイクルを巡って犯罪行為を行っている．

悪名高い犯罪組織 Dlalswp を摘発するため，市長は全ての奇数長の単純なサイクルに対して，少なくとも

1

本以上の辺に警察が配置されているようにしたいと考えている．各辺に警察を配置するために必要なコストは，辺の重みと同じである．あなたは市長が目標を達成するために必要なコストの最小値を計算する必要がある．

実装の詳細

あなたは以下の関数を実装する必要がある．

long long place_police(vector<int> P, vector<long long> C, vector<long long> W)

この関数は一度だけ呼び出される．
$P$ : 長さ
$N - 1$ の整数配列であり，外周の循環道路を建設する前の KOI 市の道路ネットワークを表している．すべての
$i$ （
$0 ≦ i ≦ N - 2$ ）について，交差点
$P [i]$ と交差点
$i + 1$ を結ぶ道路が存在する．
$C$ : 長さ
$N - 1$ の整数配列であり，すべての
$i$ （
$0 ≦ i ≦ N - 2$ ）について，交差点
$P [i]$ と交差点
$i + 1$ を結ぶ道路の重みは
$C [i]$ である．
$W$ : 長さ
$K$ の整数配列であり，すべての
$i$ （
$0 ≦ i ≦ K - 1$ ）について，交差点
$V [i]$ と交差点
$V [(i + 1) mod K]$ を結ぶ道路の重みは
$W [i]$ である．
この関数は、すべての奇数長の単純サイクルに少なくとも
$1$ 人の警察が配置されるように，KOI 市の道路に警察を配置するための最小コストを返さなければならない．

コードの提出時に，入出力関数を実行しないようにすること．

制約

$4 ≦ N ≦ 100 000$
すべての
$i$
$(0 ≦ i ≦ N - 2)$ について，
$0 ≦ P [i] ≦ i$ である．
すべての
$i$
$(0 ≦ i ≦ N - 2)$ について，
$0 ≦ C [i] ≦ 10^{12}$ である．
すべての
$i$
$(0 ≦ i ≦ K - 1)$ について，
$0 ≦ W [i] ≦ 10^{12}$ である．

小課題

(
$6$ 点)

$K ≦ 5$

(
$8$ 点)

すべての
$i$
$(0 ≦ i ≦ N - 2)$ について，
$P [i] = 0$ である．

(
$5$ 点)

すべての
$i$
$(0 ≦ i ≦ N - 2)$ について，
$C [i] ≦ 10^{6}$ である．
すべての
$i$
$(0 ≦ i ≦ K - 1)$ について，
$W [i] = 10^{12}$ である．
$K$ は偶数である．

(
$15$ 点)

すべての
$i$
$(0 ≦ i ≦ N - 2)$ について，
$C [i] ≦ 10^{6}$ である．
すべての
$i$
$(0 ≦ i ≦ K - 1)$ について，
$W [i] = 10^{12}$ である．

(
$57$ 点)

$4$ 本以上の道路に隣接する交差点は存在しない．

(
$9$ 点)

追加の制約はない．

入出力例1

N = 4

，

P = [0, 0, 0]

，

C = [9, 8, 0]

，

W = [9, 9, 9]

の場合を考えよう．

採点プログラムは以下のような呼び出しを行う．

place_police([0, 0, 0], [9, 8, 0], [9, 9, 9])

KOI 市の様子は下図のようになっている．

KOI 市には，

{0, 1, 2}, {0, 2, 3}, {0, 3, 1}, {1, 2, 3}

の計

4

つの奇数長の単純サイクルがある．市長が交差点

(0, 3)

を結ぶ重み

0

の道路と，交差点

(1, 2)

を結ぶ重み

9

の道路に警察を配置する場合，すべての奇数長の単純サイクルについて警察が配置された道路が少なくとも

1

本以上存在することになる．この配置のコストは

0 + 9 = 9

であり，これよりも低いコストで目標を達成することはできない．

よって，関数は

9

を返す必要がある．

入出力例2

N = 11

，

P = [0, 0, 2, 3, 3, 2, 0, 7, 7, 9]

，

C = [9, 8, 0, 7, 1, 6, 0, 7, 1, 6]

，

W = [1000000000000, \dots, 1000000000000]

の場合を考えよう．

W

の長さは

6

であり，すべての要素は

10^{12}

である．

採点プログラムは以下のような呼び出しを行う．

place_police([0, 0, 2, 3, 3, 2, 0, 7, 7, 9],
[9, 8, 0, 7, 1, 6, 0, 7, 1, 6],
[1000000000000, ..., 1000000000000])

KOI 市の様子は下図のようになっている．

市長が交差点

(2, 3)

を結ぶ重み

0

の道路と，交差点

(0, 7)

を結ぶ重み

0

の道路と，交差点

(3, 5)

を結ぶ重み

1

の道路に警察を配置する場合，すべての奇数長の単純サイクルについて警察が配置された道路が少なくとも

1

本以上存在することになる．この配置のコストは

0 + 0 + 1 = 1

であり，これよりも低いコストで目標を達成することはできない．

よって，関数は

1

を返す必要がある．

採点プログラムのサンプル

採点プログラムのサンプルは以下の形式で入力を受け取る．

$1$ 行目:
$N$
$2 + i$ 行目
$(0 ≦ i ≦ N - 2)$ :
$P [i] C [i]$
$1 + N$ 行目:
$W [0] W [1] \dots W [K - 1]$

採点プログラムのサンプルは以下の形式で次の内容を出力する．

$1$ 行目: police_place 関数の返り値．

採点プログラムのサンプルと実際の採点プログラムは異なる場合があることに注意すること．