A - いっしょ (Together)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある 1 本の道に N 匹のビーバーがいる.この道は数直線と見なされ,i 番目 (1 \leqq i \leqq N) のビーバーは座標 X_{i} にいる.

ビーバーは皆寂しがりやなため,自分と同じ座標に他のビーバーが 1 匹以上いると嬉しくなる.

ビーバーを適切に移動させることによって,移動距離の総和をできるだけ小さくしつつ,全員が同時に嬉しくなるようにしたい.なお,移動しないビーバーがいても良い.

N 匹のビーバーの座標が与えられたとき,ビーバーを移動させて全員が同時に嬉しい状態を作るための,ビーバーの移動距離の総和の最小値を求めるプログラムを作成せよ.

なお,この問題の制約の下では,答えは必ず整数になることが証明できる.

入力

入力は以下の形式で標準入力から与えられる.

N
X_{1} X_{2} \cdots X_{N}

出力

ビーバーを移動させて全員が同時に嬉しい状態を作るための,ビーバーの移動距離の総和の最小値を標準出力に 1 行で出力せよ.

制約

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq X_{i} \leqq 10^{9} (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (17 点) N = 4.
  2. (20 点) X_{i} = i (1 \leqq i \leqq N).
  3. (35 点) N \leqq 100,X_{i} \leqq 100 (1 \leqq i \leqq N).
  4. (28 点) 追加の制約はない.

入力例 1

4
1 2 3 4

出力例 1

2

例えば以下のように移動することで,全員が同時に嬉しくなる.

  • 1 番目のビーバーが座標 1 から座標 2 まで移動する.
  • 3 番目のビーバーが座標 3 から座標 4 まで移動する.

このとき,移動距離の総和は 2 であり,移動距離の総和をこれ以上小さくすることはできないため,2 を出力する.

この入力例はすべての小課題の制約を満たす.

入力例 2

5
1 9 8 2 7

出力例 2

3

例えば以下のように移動することで,全員が同時に嬉しくなる.

  • 1 番目のビーバーが座標 1 から座標 2 まで移動する.
  • 5 番目のビーバーが座標 7 から座標 8 まで移動する.
  • 2 番目のビーバーが座標 9 から座標 8 まで移動する.

このとき,移動距離の総和は 3 であり,移動距離の総和をこれ以上小さくすることはできないため,3 を出力する.

この入力例は小課題 3, 4 の制約を満たす.

入力例 3

10
9 20 5 10 8 1 10 19 15 4

出力例 3

10

この入力例は小課題 3, 4 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day1
B - バームクーヘン 2 (Baumkuchen 2)

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

葵はパーティーを開催しようと計画している.このパーティーには葵を含めた K 人が参加予定であり,参加者には 1 から K までの番号が付けられている.

パーティーでは K 人で 1 個のバームクーヘンを食べる.バームクーヘンは円筒形のお菓子である.K 人に分けるために,葵は半径方向に刃を K 回入れて,これを K 個の等しい大きさのピースに切り分けなければならない.ただしこのバームクーヘンは本物の木材のように固いので,刃を入れるのは簡単ではない.そのためこのバームクーヘンにはあらかじめ K \times L 個の切れ込みが均等に入っており,葵は切れ込みがある位置でのみ切ることができる.切れ込みに 1 から KL まで時計回りに番号をふったとき,整数 i (1 \leqq i \leqq KL - 1) に対し,切れ込み i と切れ込み i + 1 の間の部分をパーツ i と呼ぶ.また,切れ込み KL と切れ込み 1 の間の部分をパーツ KL と呼ぶ.

葵は以下の手順に沿って,バームクーヘンを分けようとしている.

  1. K 個の切れ込みに沿ってバームクーヘンを切り,L 個のパーツからなるピース K 個に分ける.
  2. 各参加者にピースを 1 個ずつ割り当てる.ただし,1 個のピースが 2 人以上の参加者に割り当てられてはいけない.

現在,葵はバームクーヘンを分ける手順を決めていない.これから,Q 回にわたり参加者が要望を葵に伝える.j 回目 (1 \leqq j \leqq Q) に葵に伝える要望は,以下のようなものである.

  • 各参加者にピースを割り当てた後に,パーツ X_{j} を含むピースが参加者 Y_{j} に割り当てられているようにしたい.

ただし,すでに要望で指定されたパーツが新たに指定されることはない.

葵は,各要望が伝えられた時点において,その時点までのすべての要望を満たすような手順が何通りあるかを求めたい.ここで,2 つの手順が異なるとは,割り当てられている参加者が異なるようなパーツがあることとする.

バームクーヘンと参加者の要望の情報と素数 P が与えられたとき,各要望が伝えられた時点において,その時点までのすべての要望を満たすような手順の個数を P で割った余りを求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

K L
P
Q
X_{1} Y_{1}
X_{2} Y_{2}
\vdots
X_{Q} Y_{Q}

出力

標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,j 回目の要望が伝えられた時点において,その時点までのすべての要望を満たすような手順の個数を P で割った余りを出力せよ.

制約

  • 2 \leqq K \leqq 200\,000.
  • 1 \leqq L \leqq 200\,000.
  • 10^{8} < P < 10^{9}.
  • P は素数である.
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq X_{j} \leqq KL (1 \leqq j \leqq Q).
  • X_{j} \ne X_{k} (1 \leqq j < k \leqq Q).
  • 1 \leqq Y_{j} \leqq K (1 \leqq j \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (13 点) K \leqq 8,L \leqq 10,Q \leqq 10.
  2. (14 点) K \leqq 100,L \leqq 100,Q \leqq 100.
  3. (18 点) K \leqq 400,L \leqq 400,Q \leqq 400.
  4. (17 点) K \leqq 2\,500,L \leqq 2\,500,Q \leqq 2\,500.
  5. (28 点) K \leqq 10.
  6. (10 点) 追加の制約はない.

入力例 1

3 2
998244353
2
1 2
6 2

出力例 1

4
2

1 回目の要望はパーツ 1 を含むピースが参加者 2 に割り当てられているようにしたいというものである.この時点までのすべての要望を満たすような手順の個数は 4 通りである.例えば,以下のような手順が考えられる.

  1. 切れ込み 1, 3, 5 に沿ってバームクーヘンを切り分ける.
  2. 参加者 1 にパーツ 3, 4 からなるピースを割り当てる.参加者 2 にパーツ 1, 2 からなるピースを割り当てる.参加者 3 にパーツ 5, 6 からなるピースを割り当てる.

2 回目の要望はパーツ 6 を含むピースが参加者 2 に割り当てられているようにしたいというものである.この時点までのすべての要望を満たすような手順の個数は 2 通りである.例えば,以下のような手順が考えられる.

  1. 切れ込み 2, 4, 6 に沿ってバームクーヘンを切り分ける.
  2. 参加者 1 にパーツ 4, 5 からなるピースを割り当てる.参加者 2 にパーツ 6, 1 からなるピースを割り当てる.参加者 3 にパーツ 2, 3 からなるピースを割り当てる.

この入出力例はすべての小課題の制約を満たす.

入力例 2

8 10
304623133
10
8 8
6 8
51 1
36 5
10 7
38 5
68 3
57 4
76 3
19 2

出力例 2

50400
40320
5760
960
48
48
12
0
0
0

この入出力例はすべての小課題の制約を満たす.

入力例 3

10 8
446958661
10
26 5
49 9
37 6
10 1
15 3
29 5
69 2
2 1
25 5
12 1

出力例 3

2903040
322560
40320
5760
600
240
48
0
0
0

この入出力例は小課題 2, 3, 4, 5, 6 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day1
C - ボードゲーム (Board Game)

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

K 人用のボードゲームがある.このボードゲームのボードには 1 から N までの番号のついた N 個のマスと,1 から M までの番号のついた M 本の道があり,道 j (1 \leqq j \leqq M) はマス U_j と V_j の間を双方向に接続している.

N 個のマスには 再行動マス と 停止マス との 2 種類がある.その情報は 0, 1 からなる長さ N の文字列 S によって与えられ,S の i 文字目 (1 \leqq i \leqq N) が 0 ならばマス i は再行動マス,S の i 文字目が 1 ならばマス i は停止マスである.

このボードゲームは 1 から K までの番号がついた K 人のプレイヤーで遊ぶ.各プレイヤーは自分の駒を 1 つ持っており,各プレイヤーの駒を指定されたマスの上に置いてゲームを開始する.はじめプレイヤー p (1 \leqq p \leqq K) の駒はマス X_p に置く.なお,1 つのマスに複数のプレイヤーの駒を置くことも可能である.

ゲームはプレイヤー 1 から始めて番号順に自分のターンをプレイするという形で進行する.プレイヤー p が自分のターンをプレイし終わると,次はプレイヤー p+1(ただし p=K ならばプレイヤー 1)のターンとなる.各プレイヤーは,自分のターンのときに次のような行動を行う:

  1. 自分の駒が置かれているマスと道で接続されているマスをひとつ選び,選んだマスに自分の駒を移動させる.
  2. 移動先のマスが再行動マスならば 1. に戻り,自分のターンを継続する.移動先のマスが停止マスならば自分のターンを終了する.

このボードゲームの日本代表である JOI 君たち K 人は,ゲームを協力して高速に攻略する方法を研究している.現在研究しているのは次の問題である:

プレイヤー 1 の駒がマス T に置かれている状態にするために必要な,K 人合計での駒の移動回数の最小値はいくつか.なお,ターンの途中であっても,プレイヤー 1 の駒がマス T に置かれれば条件が満たされたものとみなす.

ボードゲームのボードの情報と各プレイヤーの駒の初期配置が与えられた場合に,各 T=1,2,\ldots,N に対して,この問題の答えを計算するプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N M K
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S
X_1 X_2 \cdots X_K

出力

標準出力に N 行出力せよ.T 行目 (1 \leqq T \leqq N) には,プレイヤー 1 の駒がマス T に置かれている状態にするために必要な,K 人合計での駒の移動回数の最小値を出力せよ.


制約

  • 2 \leqq N \leqq 50\,000.
  • 1 \leqq M \leqq 50\,000.
  • 2 \leqq K \leqq 50\,000.
  • 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq M).
  • (U_j,V_j) \neq (U_k,V_k) (1 \leqq j < k \leqq M).
  • どのマスからどのマスへも,結ばれている道を何本か辿って到達できる.
  • S は 0, 1 からなる長さ N の文字列である.
  • 1 \leqq X_p \leqq N (1 \leqq p \leqq K).
  • N,M,K は整数である.
  • U_j,V_j は整数である (1 \leqq j \leqq M).
  • X_p は整数である (1 \leqq p \leqq K).

小課題

  1. (7 点) 停止マスは存在しない.
  2. (12 点) 停止マスの個数は 1 個である.
  3. (12 点) 停止マスの個数は 2 個である.
  4. (23 点) N \leqq 3\,000,M \leqq 3\,000,K \leqq 3\,000.
  5. (23 点) K=2.
  6. (7 点) K \leqq 100.
  7. (12 点) N \leqq 30\,000,M \leqq 30\,000,K \leqq 30\,000.
  8. (4 点) 追加の制約はない.

入力例 1

5 5 2
1 2
2 3
2 4
3 5
4 5
00000
1 5

出力例 1

0
1
2
2
3

はじめプレイヤー 1 の駒はマス 1 に置かれているので,T=1 に対する答えは 0 である.

T=2 のとき,1 回目の移動で,プレイヤー 1 の駒をマス 1 からマス 2 に移動させることができる.したがって T=2 に対する答えは 1 である.

T=3 のとき,次のような 2 回の移動でプレイヤー 1 の駒をマス 3 に置くことができる.

  • 1 回目の移動では,プレイヤー 1 の駒をマス 1 からマス 2 に移動させる.マス 2 は再行動マスであるから,プレイヤー 1 のターンが継続される.
  • 2 回目の移動では,プレイヤー 1 の駒をマス 2 からマス 3 に移動させる.

1 回以下の移動でプレイヤー 1 の駒をマス 3 に置くことはできないため,T=3 に対する答えは 2 である.

同様に T=4 に対する答えは 2,T=5 に対する答えは 3 であることが確かめられる.

この入力例は小課題 1,4,5,6,7,8 の制約を満たす.


入力例 2

5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

出力例 2

0
1
4
4
5

例えば T=3 のとき,次のような 4 回の移動でプレイヤー 1 の駒をマス 3 に置くことができる.

  • 1 回目の移動では,プレイヤー 1 の駒をマス 1 からマス 2 に移動させる.マス 2 は停止マスであるから,次はプレイヤー 2 のターンとなる.
  • 2 回目の移動では,プレイヤー 2 の駒をマス 5 からマス 3 に移動させる.マス 3 は再行動マスであるから,プレイヤー 2 のターンが継続される.
  • 3 回目の移動では,プレイヤー 2 の駒をマス 3 からマス 2 に移動させる.マス 2 は停止マスであるから,次はプレイヤー 1 のターンとなる.
  • 4 回目の移動では,プレイヤー 1 の駒をマス 2 からマス 3 に移動させる.

3 回以下の移動でプレイヤー 1 の駒をマス 3 に置くことはできないため,T=3 に対する答えは 4 である.

この入力例は小課題 2,4,5,6,7,8 の制約を満たす.


入力例 3

5 5 2
1 2
2 3
2 4
3 5
4 5
01100
1 5

出力例 3

0
1
3
3
4

この入力例は小課題 3,4,5,6,7,8 の制約を満たす.


入力例 4

8 7 5
1 3
5 7
4 6
2 6
2 3
7 8
1 5
10011010
4 6 4 7 1

出力例 4

4
2
3
0
10
1
17
24

この入力例は小課題 4,6,7,8 の制約を満たす.


入力例 5

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

出力例 5

0
1
4
5
6
7
8
8
4
1
13
9

この入力例は小課題 4,6,7,8 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day1
D - 三色灯 (Tricolor Lights)

Time Limit: 2 sec / Memory Limit: 1024 MiB

AtCoder での提出方法

配布ファイル.

C++ を使用する場合

C++ を使用する場合,Anna.h,Bruno.h を include し,すべての関数を 1 つのファイル内で実装してください.

標準入出力やファイルへの入出力を使用しないでください.

その他の言語を使用する場合
  • ジャッジ
  • argv[1] を 0 として起動されたあなたのプログラム(Anna 側)
  • argv[1] を 1 として起動されたあなたのプログラム(Bruno 側)

の 3 つのプログラムが同時に実行されます.実行時間・使用メモリはこれらの合計で計測されます.

Anna 側

argv[1] が 0 のとき,Anna 側として振る舞ってください.

anna

以下の形式で入力を受け取ってください.

N
S

以下の形式で出力してください.

t
l

Bruno 側

argv[1] が 1 のとき,Bruno 側として振る舞ってください.

init

以下の形式で入力を受け取ってください.

Q
N
l
bruno

以下の形式で入力を受け取ってください.

u

bruno の戻り値を 1 行で出力してください.

その他

  • 各出力の後には必ず flush をしてください.
  • 出力の形式が正しくない場合や不正解の条件に当てはまったとき,与えられる入力は WA になります.この場合,ただちにプログラムを終了してください.

配点 : 100 点

問題文

賭け事の達人である Anna と Bruno の 2 人組は,ディーラーのディ太郎を相手にゲームで勝負することとなった.

ゲーム中,Anna と Bruno は別々の部屋に隔離され,ディ太郎を介してのみやりとりができる.

このゲームでは横一列に並んだ N 個のライトを用いる.これらのライトには左から順に 1 から N までの番号が付けられている.これらのライトは赤,緑,青のうち,いずれかの色に点灯させることができる.

Anna は,ゲーム開始時にこれらのライトそれぞれについて赤,緑,青のいずれかの色に点灯させる.また,ディ太郎により,それぞれのライトについて 1 つの 禁止色 が定められており,これは長さ N の文字列 S によって表される.S の i 文字目 (1 \leqq i \leqq N) を S_i とすると,ライト i の禁止色は,S_i が R のとき赤,G のとき緑,B のとき青である.Anna はライト i をそのライトの禁止色に点灯させることができない.例えば,S_1 が R であるならば,Anna はライト 1 について,緑か青のいずれかの色に点灯させなければならない.ディ太郎がそれぞれのライトについて定めた禁止色の情報は,Anna には伝えられるが,Bruno には伝えられない.

Anna はそれぞれのライトを点灯させたのち,1 \leqq l \leqq \min(N,130) を満たす整数 l を選び,ディ太郎に伝える.ディ太郎は,Bruno にライトの個数 N と,Anna が選んだ整数 l を伝える.その後,Q 回のラウンドを行う.j 回目 (1 \leqq j \leqq Q) のラウンドは,以下のように進行する.

  1. ディ太郎は 1 以上 N - l+1 以下の整数 a_j を選び,ライト a_j,a_j+1,\ldots,a_j+l - 1 について点灯している色の並びを Bruno に見せる.
  2. Bruno は,見せられた色の並びをもとに,1 つの整数をディ太郎に伝える.この整数が a_j と一致すれば,このラウンドで Anna と Bruno は勝利する.

ただし,ディ太郎は,Anna が点灯させたライトの色の並びや整数 l に応じて,a_1,a_2,\ldots,a_Q の選び方を変える可能性がある.

Anna と Bruno が Q 回すべてのラウンドで勝利するための戦略を実装したプログラムを作成せよ.


実装の詳細

あなたは 2 つのファイルを提出しなければならない.

1 つ目のファイルは Anna.cpp という名前である.このファイルは Anna の戦略を実装したファイルであり,以下の関数を実装していなければならない.また,#include プリプロセッサ指令によって Anna.h を読み込むこと.

  • std::pair<std::string, int> anna(int N, std::string S) この関数は,最初に 1 回だけ呼び出される.
    • 引数 N は,ライトの個数 N である.
    • 引数 S は,ディ太郎が定めた禁止色を表す長さ N の文字列 S である.
    • 戻り値は,Anna がそれぞれのライトに点灯させる色を表す長さ N の文字列 t,整数 l のペアである.t の i 文字目 (1 \leqq i \leqq N) を t_i とすると,Anna が i 番目のランプを色 t_i に点灯させることを意味する.t_i は,R のとき赤,G のとき緑,B のとき青を意味する.
    • 文字列 t の長さは N でなければならない.これが満たされない場合,不正解 [1] と判定される.
    • 文字列 t の各文字は R または G または B でなければならない.これが満たされない場合,不正解 [2] と判定される.
    • 文字列 t の i 文字目 (1 \leqq i \leqq N) は S の i 文字目と異ならなければならない.これが満たされない場合,不正解 [3] と判定される.
    • l は 1 以上 \min(N,130) 以下でなければならない.これが満たされない場合,不正解 [4] と判定される.

2 つ目のファイルは Bruno.cpp という名前である.このファイルは Bruno の戦略を実装したファイルであり,以下の関数を実装していなければならない.また,#include プリプロセッサ指令によって Bruno.h を読み込むこと.

  • void init(int N, int l) この関数は,最初に 1 回だけ呼び出される.
    • 引数 N は,ライトの個数 N である.
    • 引数 l は,Anna が指定した整数 l である.
  • int bruno(std::string u) この関数は,関数 init が呼び出された後に,合計で Q 回呼び出される.j 回目 (1 \leqq j \leqq Q) の呼び出しは,ゲームにおける j 回目のラウンドの手順 1. および手順 2. に相当する.
    • 引数 u は R, G, B からなる長さ l の文字列で,ライト a_j,a_j+1,\ldots,a_j+l - 1 に点灯している色の並びを表す.u の k 文字目 (1 \leqq k \leqq l) を u_k とすると,Anna が a_j+k - 1 番目のランプに点灯させた色は,u_k が R のとき赤,G のとき緑,B のとき青である.
    • 戻り値は,Bruno が答える整数である.
    • 戻り値は,a_j と一致していなければならない.これが満たされない場合,不正解 [5] と判定される.

重要な注意

  • 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.ただし,提出された 2 つのプログラムは,採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので,各ファイル内のすべてのグローバル変数と内部関数を無名名前空間内で宣言して,他のファイルとの干渉を避ける必要がある.採点時には,このプログラムは Anna 側,Bruno 側として 2 個のプロセスとして実行されるので,Anna 側と Bruno 側でプログラム中のグローバル変数を共有することはできない.
  • あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムのサンプルが,公式サイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.cpp である.作成したプログラムをテストするには,grader.cpp,Anna.cpp,Bruno.cpp,Anna.h,Bruno.h を同じディレクトリに置き,次のようにコマンドを実行する.なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.

g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

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

採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.

N
S
Q
a_1 a_2 \cdots a_Q

採点プログラムのサンプルは,実際の採点プログラムと異なり,初めから固定された答えを持つ必要がある.a_j (1 \leqq j \leqq Q) は,ディ太郎が j 回目のラウンドで選ぶ整数 a_j を表す.あなたが書いたプログラムにおいて Anna が選んだ整数 l に対して,1 \leqq a_j \leqq N - l+1 を満たさなければならない.

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

採点プログラムのサンプルは標準出力へ以下の情報を出力する(引用符は実際には出力されない).

  • 正解の場合,Anna が選んだ整数 l が “Accepted: 130” のように出力される.
  • 不正解の場合,不正解の種類が “Wrong Answer [1]” のように出力される.

実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.

採点に関する注意

実際の採点プログラムは,Anna が点灯させたライトの色の並びや選んだ整数 l に応じて a_1,a_2,\ldots,a_Q を定める.特に,Bruno が答えた整数によって a_1,a_2,\ldots,a_Q の値を変えることはない.


制約

  • 1 \leqq N \leqq 500\,000.
  • 1 \leqq Q \leqq 10\,000.
  • S は R, G, B からなる長さ N の文字列である.
  • N,Q は整数である.

採点に関する注意

特定のテストケースについて,実際の採点プログラムは適応的 (adaptive) である.これは,採点プログラムは Anna が点灯させたライトの色の並びや選んだ整数 l に応じて a_1, a_2, \ldots, a_Q の選び方を変える可能性があることを意味する.

小課題

  1. (10 点) N \leqq 131.
  2. (10 点) N \leqq 250.
  3. (10 点) N \leqq 380.
  4. (20 点) N \leqq 7000.
  5. (50 点) 追加の制約はない.この小課題では,以下に従い得点が決定される.
    • この小課題のすべてのテストケースにおける,Anna が選んだ整数 l の最大値を l^{\ast} とする.
    • このとき,小課題の得点は以下のように決定される.
l^{\ast} の値 得点
61 < l^{\ast} \leqq 130 15 点
41 < l^{\ast} \leqq 61 25 点
34 < l^{\ast} \leqq 41 30+2\times(41 - l^{\ast}) 点
28 < l^{\ast} \leqq 34 44+1\times(34 - l^{\ast}) 点
l^{\ast} \leqq 28 50 点

やりとりの例

採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.

入力例 1

8
RGGBRBBG
2
3 1

関数の呼び出しの例

呼び出し 戻り値
anna(8, "RGGBRBBG") ("BBRGBGRR", 5)
init(8, 5)
bruno("RGBGR") 3
bruno("BBRGB") 1

このやりとりの例において,Anna はライトの個数 N=8,禁止色を表す文字列 S= {}"RGGBRBBG" を受け取り,それぞれのライトに点灯させる色を表す文字列 t として "BBRGBGRR",整数 l として 5 を指定し,ディ太郎に伝える.その後,ディ太郎は Bruno に整数 N=8,l=5 を伝える.

1 回目のラウンドでは,ディ太郎は a_1=3 としている.Bruno はライト 3,4,5,6,7 に点灯している色の並びを表す文字列 u= {}"RGBGR" を受け取り,a_1 である 3 を答える.

入力例 1 はすべての小課題の制約を満たす.コンテストサイトからダウンロードできるファイルのうち,sample-01-in.txt は入力例 1 に対応する.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day1
E - カードゲーム 3 (Card Game 3)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

JOI 君は,カードゲームで遊んでいる.このカードゲームでより多くの得点を得ることが JOI 君の目標である.

このゲームでは,はじめに N 枚の色付きのカードを受け取る.それぞれのカードには 1 から N までの番号が付けられており,カード i (1 \leqq i \leqq N) には整数 A_{i} が書かれている.また,カードの色は 1 以上 N 以下の整数として表され,カード i の色は C_{i} である.

ゲームを開始する時点での得点は 0 ポイントである.その後,次の操作を 0 回以上繰り返すことで得点を得る.

  • 色の異なる 2 枚のカード i, j を選び,A_{i} + A_{j} ポイントを得点に加算する.選んだカードのうち 1 枚を選んで捨てる.捨てたカードは,それ以降の操作において選ぶことができない.

JOI 君が受け取るカードに関する情報が与えられたとき,JOI 君の最終的な得点としてありうる最大値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

N
A_{1} C_{1}
A_{2} C_{2}
\vdots
A_{N} C_{N}

出力

標準出力に,JOI 君の最終的な得点としてありうる最大値を表す整数を 1 行で出力せよ.

制約

  • 2 \leqq N \leqq 500\,000.
  • -10^{9} \leqq A_{i} \leqq 10^{9} (1 \leqq i \leqq N).
  • 1 \leqq C_{i} \leqq N (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (13 点) C_{1} = 1,C_{i} = 2 (2 \leqq i \leqq N).
  2. (22 点) N \geqq 3,C_{1} = 1,C_{2} = 1,C_{i} = 2 (3 \leqq i \leqq N),A_{i} \geqq 0 (1 \leqq i \leqq N).
  3. (10 点) N \geqq 3,C_{1} = 1,C_{2} = 1,C_{i} = 2 (3 \leqq i \leqq N).
  4. (28 点) C_{i} \leqq 2 (1 \leqq i \leqq N).
  5. (27 点) 追加の制約はない.

入力例 1

4
5 1
3 2
-1 1
4 2

出力例 1

20

例えば,以下のように 3 回の操作を行うことで最終的な得点を 20 ポイントにすることができる.

はじめ,得点は 0 ポイントである.

1 回目の操作ではカード 1, 2 を選び,8 ポイントを得点に加算する.選んだカードのうち,カード 2 を選んで捨てる.

2 回目の操作ではカード 3, 4 を選び,3 ポイントを得点に加算する.選んだカードのうち,カード 3 を選んで捨てる.

3 回目の操作ではカード 1, 4 を選び,9 ポイントを得点に加算する.選んだカードのうち,カード 1 を選んで捨てる.

最終的な得点を 21 ポイント以上にすることはできないため,20 を出力する.

この入力例は小課題 4, 5 の制約を満たす.

入力例 2

4
3 1
2 2
-5 2
-1 2

出力例 2

7

この入力例は小課題 1, 4, 5 の制約を満たす.

入力例 3

5
3 1
1 1
9 2
2 2
5 2

出力例 3

35

この入力例は小課題 2, 3, 4, 5 の制約を満たす.

入力例 4

8
825766307 4
-97420452 1
675295693 6
662995109 1
-751453145 7
646290641 7
378394053 5
288845388 6

出力例 4

7583311436

この入力例は小課題 5 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day2
F - チョコレートを増やせ (Increase Chocolates)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

オランダではチョコレートが有名である.オランダのとあるチョコレート店では現在キャンペーンを行っており,チョコレートとの交換に使えるチケットが,チョコレート 1 つにつき 1 枚付けられている.

チケットは N 種類の交換規則によってチョコレートと交換することができる.i 番目 (1 \leqq i \leqq N) の交換規則を使うと,店員に A_{i} 枚のチケットを渡したとき,B_{i} 個のチョコレートを受け取ることができる.ここで,A_{i} > B_{i} が成り立つ.交換規則は好きな順で何回でも使うことができ,交換で受け取るチョコレートにもチケットが付いている.

あなたは,交換規則を駆使して,できるだけ少ない個数のチョコレートを購入して,EGOI の参加者に 1 個ずつチョコレートを配りたいと考えている.ただし,あなたははじめチョコレートもチケットも持っておらず,購入と交換以外の方法でチョコレートやチケットを受け取ることはできない.また,参加者に配るチョコレートにチケットが付いている必要はない.

EGOI の参加者は M 人いるが,何人かはチョコレートが苦手かもしれない.そこで,各 k = 1, 2, \ldots, M について,k 個以上のチョコレートを用意するために購入する必要があるチョコレートの個数の最小値が知りたい.

交換規則と EGOI の参加人数 M の情報が与えられたとき,各 k = 1, 2, \ldots, M について,k 個以上のチョコレートを用意するために購入する必要があるチョコレートの個数の最小値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

N M
A_{1} B_{1}
A_{2} B_{2}
\vdots
A_{N} B_{N}

出力

標準出力に M 行で出力せよ.k 行目 (1 \leqq k \leqq M) には,k 個以上のチョコレートを用意するために購入する必要があるチョコレートの個数の最小値を出力せよ.

制約

  • 1 \leqq N \leqq 500.
  • 1 \leqq M \leqq 100\,000.
  • 1 \leqq B_{i} < A_{i} < M (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (15 点) M \leqq 500,N = 1.
  2. (15 点) M \leqq 500,A_{1} - B_{1} = A_{2} - B_{2} = \cdots = A_{N} - B_{N}.
  3. (30 点) M \leqq 500.
  4. (40 点) 追加の制約はない.

入力例 1

2 12
3 1
5 2

出力例 1

1
2
3
3
4
5
5
6
6
7
8
8

例えば,6 個のチョコレートを購入し,以下のように交換規則を使うことで,9 個のチョコレートを用意することができる.

  • はじめ,チョコレートが 6 個,チケットが 6 枚ある.
  • 2 番目の交換規則を使う.チケット 5 枚を渡し,チョコレート 2 個とチケット 2 枚を受け取る.チョコレートが 8 個,チケットが 3 枚になる.
  • 1 番目の交換規則を使う.チケット 3 枚を渡し,チョコレート 1 個とチケット 1 枚を受け取る.チョコレートが 9 個,チケットが 1 枚になる.

購入するチョコレートの数が 5 個以下のとき,最終的なチョコレートの数を 9 個以上にすることはできないため,9 行目には 6 を出力する.

この入力例は小課題 3, 4 の制約を満たす.

入力例 2

1 10
4 3

出力例 2

1
2
3
4
4
4
4
5
5
5

この入力例はすべての小課題の制約を満たす.

入力例 3

3 10
3 1
5 3
4 2

出力例 3

1
2
3
3
4
4
5
5
5
6

この入力例は小課題 2, 3, 4 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day2
G - 島巡り (Island Hopping)

Time Limit: 2 sec / Memory Limit: 1024 MiB

AtCoder での提出方法

配布ファイルは こちら.

C++ を使用する場合

island.h を include し,関数 solve を実装したソースコードを提出すること.

その他の言語を使用する場合

solve の呼び出しに相当する入力が,以下の形式で与えられる.

N L

終了時に,0 0 を 1 行で出力すること.

query(v, k) の呼び出しに相当する出力は,以下の形式で行うこと.

v k

その後,query の戻り値が 1 行で与えられる.

answer(x, y) の呼び出しに相当する出力は,x < y として,以下の形式で行うこと.

-x y

その後,0 が 1 行で与えられる.

  • 各出力の後には必ず flush をすること.
  • 出力の形式が正しくない場合や不正解の条件に当てはまった場合,与えられる入力は -1 になる.この場合,ただちにプログラムを終了すること.

配点 : 100 点

問題文

JOI 国には N 個の島があり,1 から N までの番号が付けられている.また,JOI 国には N - 1 本の航路があり,1 から N - 1 までの番号が付けられている.航路 j (1 \leqq j \leqq N - 1) は島 A_j と島 B_j を双方向に結んでいる.どの島からどの島へも,いくつかの航路を乗り継ぐことで移動できる.

葵は JOI 国での旅行を計画している.しかし,葵は JOI 国の航路について知らない.そこで,JOI 国に住んでいるビ太郎と以下のようなやりとりを行うことにした.

  1. 葵は 1 以上 N 以下の整数 v と 1 以上 N - 1 以下の整数 k をビ太郎に伝える.
  2. ビ太郎は島 v 以外の N - 1 個の島のうち,島 v から k 番目に近い島の番号を葵に伝える.具体的には,整数 i (1 \leqq i \leqq N,i \neq v) について \operatorname{dist}(v, i) を島 v から島 i に移動する際に必要な航路の数の最小値としたとき,ビ太郎は \operatorname{dist}(v, i) \times N + i が k 番目に小さくなるような整数 i を葵に伝える.

葵はビ太郎とのやりとりを通じて,どの島とどの島を結ぶ航路があるのかを知りたい.しかし,葵は忙しいので,ビ太郎とのやりとりを L 回までしかできない.

JOI 国の島の数とビ太郎とのやりとりをできる回数が与えられたとき,どの島とどの島を結ぶ航路があるのかを求める葵の戦略を実装したプログラムを作成せよ.


実装の詳細

あなたは 1 つのファイルを提出しなければならない.

あなたの提出するファイルは island.cpp という名前である.island.cpp は #include プリプロセッサ指令によって island.h を読み込み,以下の関数を実装していなければならない.

  • void solve(int N, int L) この関数は各テストケースにおいて 1 回だけ呼び出される.
    • 引数 N は JOI 国の島の数 N である.
    • 引数 L は葵がビ太郎とのやりとりをできる回数 L である.

island.cpp 内では以下の関数を呼び出すことができる.

  • int query(int v, int k) この関数を用いて,ビ太郎に質問を行う.
    • 引数 v は,1 以上 N 以下でなければならない.これが満たされていない場合,不正解 [1] と判定される.
    • 引数 k は,1 以上 N - 1 以下でなければならない.これが満たされていない場合,不正解 [2] と判定される.
    • 戻り値は,島 v 以外の N - 1 個の島のうち,島 v から k 番目に近い島の番号である.より正確な定義については,問題文を参照せよ.
    • 関数 query を L 回を超えて呼び出してはならない.L 回を超えて呼び出した場合,不正解 [3] と判定される.
  • void answer(int x, int y) この関数を用いて,JOI 国の航路の情報を解答する.
    • 引数 x と引数 y は,ある航路が結ぶ 2 つの島の番号である.
    • 引数 x と引数 y は,1 以上 N 以下でなければならない.これが満たされていない場合,不正解 [4] と判定される.
    • 島 x と島 y を結ぶ航路が存在しなければならない.すなわち,x = A_j,y = B_j もしくは x = B_j,y = A_j となる整数 j (1 \leqq j \leqq N - 1) が存在しなければならない.これが満たされていない場合,不正解 [5] と判定される.
    • 同じ航路の情報を累計で 2 回以上解答してはならない.これが満たされていない場合,不正解 [6] と判定される.
    • 関数 answer はちょうど N - 1 回呼び出される必要がある.関数 solve の実行の終了時に関数 answer の呼び出し回数が N - 1 回でなかった場合,不正解 [7] と判定される.

重要な注意

  • 内部での使用のために他の関数を実装したり,グローバル変数を宣言することは自由に行える.
  • あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.cpp である.作成したプログラムをテストするには,これらのファイル grader.cpp, island.cpp, island.h を同じディレクトリに置き,次のようにコマンドを実行する.なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.

g++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意せよ.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

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

採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.

N L
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}

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

採点プログラムのサンプルは標準出力へ以下の情報を出力する(引用符は実際には出力されない).

  • 正解の場合,関数 query の呼び出し回数が “Accepted: 2024” のように出力される.
  • 不正解の場合,不正解の種類が “Wrong Answer [4]” のように出力される.

実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.

採点に関する注意

すべてのテストケースについて,実際の採点プログラムは適応的 (adaptive) ではない.これは,採点プログラムは初めから固定された答えを持つということを意味する.


制約

すべての入力データは以下の条件を満たす.

  • 3 \leqq N \leqq 300.
  • 1 \leqq A_j \leqq N (1 \leqq j \leqq N - 1).
  • 1 \leqq B_j \leqq N (1 \leqq j \leqq N - 1).
  • A_j \neq B_j (1 \leqq j \leqq N - 1).
  • どの島からどの島へも,いくつかの航路を乗り継ぐことで移動できる.
  • 入力される値はすべて整数である.

小課題

  1. (4 点) N = 3,L = 9.
  2. (6 点) L = N^2,どの島についてもその島から 1 本の航路で移動できる島は 2 つ以下である.
  3. (10 点) L = 2N,どの島についてもその島から 1 本の航路で移動できる島は 2 つ以下である.
  4. (11 点) L = N^2,島 1 から 1 本の航路で移動できる島は 3 つである.島 1 以外の他のどの島についてもその島から 1 本の航路で移動できる島は 2 つ以下である.
  5. (21 点) L = 3N,島 1 から 1 本の航路で移動できる島は 3 つである.島 1 以外の他のどの島についてもその島から 1 本の航路で移動できる島は 2 つ以下である.
  6. (14 点) L = N^2.
  7. (19 点) L = 3N.
  8. (15 点) L = 2N.

やりとりの例

採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.

入力例 1

4 16
1 2
2 4
4 3

関数の呼び出しの例

呼び出し(採点プログラム) 呼び出し(提出プログラム) 戻り値
solve(4, 16)
query(2, 1) 1
query(3, 1) 4
answer(2, 4)
query(2, 2) 4
answer(2, 1)
query(3, 2) 2
query(2, 1) 1
answer(3, 4)

島 2 から島 1,島 3,島 4 へ移動するのに必要な航路の数の最小値はそれぞれ 1, 2, 1 である.例えば,島 2 から島 3 へは航路 2,航路 3 をこの順に乗り継ぐことで移動できる.

島 2 以外の島 i を \operatorname{dist}(2, i) \times N + i が小さい順に並び替えると島 1,島 4,島 3 となる.したがって,関数 query(2, 1) の戻り値は 1 となる.また,関数 query(2, 2) の戻り値は 4 となる.

入力例 1 は小課題 2, 6 の制約を満たす.コンテストサイトからダウンロードできるファイルのうち,sample-01-in.txt は入力例 1 に対応する.


入力例 2

5 25
5 2
3 1
1 4
1 5

関数の呼び出しの例

呼び出し(採点プログラム) 呼び出し(提出プログラム) 戻り値
solve(5, 25)
query(1, 3) 5
query(1, 4) 2
answer(3, 1)
query(2, 4) 4
query(3, 1) 1
query(3, 2) 4
answer(1, 5)
answer(4, 1)
answer(2, 5)

島 1 から島 2,島 3,島 4,島 5 へ移動するのに必要な航路の数の最小値はそれぞれ 2, 1, 1, 1 である.例えば,島 1 から島 2 へは航路 4,航路 1 をこの順に乗り継ぐことで移動できる.

島 1 以外の島 i を \operatorname{dist}(1, i) \times N + i が小さい順に並び替えると島 3,島 4,島 5,島 2 となる.したがって,関数 query(1, 3) の戻り値は 5 となる.また,関数 query(1, 4) の戻り値は 2 となる.

入力例 2 は小課題 4, 6 の制約を満たす.コンテストサイトからダウンロードできるファイルのうち,sample-02-in.txt は入力例 2 に対応する.

コンテストサイトからダウンロードできるファイルに含まれる sample-01-in.txt,sample-02-in.txt は,採点プログラムのサンプルの入力として用いることができる.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day2
H - 卓球 (Table Tennis)

Time Limit: 1 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

JOI 国で卓球の大会が行われた.大会には 1 から N までの番号が付けられている N 匹のビーバーが出場し,総当たりのリーグ戦が行われた.

あなたはビ太郎から大会の試合結果について以下の情報を聞いた.

  • どの試合も引き分けではなかった.
  • 三すくみとなるような 3 匹のビーバーの選び方はちょうど M 通りであった.ただし,3 匹のビーバー i, j, k (1 \leqq i < j < k \leqq N) が三すくみであるとは,以下の 2 つの条件のうちちょうど 1 つが成り立つことをいう.
    • ビーバー i がビーバー j に勝利し,ビーバー j がビーバー k に勝利し,ビーバー k がビーバー i に勝利した.
    • ビーバー i がビーバー k に勝利し,ビーバー k がビーバー j に勝利し,ビーバー j がビーバー i に勝利した.

あなたはビ太郎から聞いた情報が正確か分からないため,聞いた情報に合致するような大会の試合結果が存在するか考えることにした.

ビ太郎から聞いた情報が与えられたとき,情報に合致する試合結果が存在するか判定し,もし存在するならばそのような試合結果を 1 つ求めるプログラムを作成せよ.


入力

1 つのテストケースは Q 個のシナリオからなり,シナリオには 1 から Q までの番号が付けられている.各シナリオに対して,以下の値が定められている.

  • 大会に参加したビーバーの数 N.
  • 三すくみとなるような 3 匹のビーバーの選び方 M.

ここで,入力は以下の形式で標準入力から与えられる.

Q
(シナリオ 1 に対する入力)
(シナリオ 2 に対する入力)
\vdots
(シナリオ Q に対する入力)

また,それぞれのシナリオに対する入力は,以下の形式で与えられる.

N M

出力

標準出力に,シナリオ 1, 2, \ldots, Q の順に以下の形式で出力せよ.

あるシナリオについて,情報に合致する試合結果が存在する場合,以下の形式で出力せよ.

Yes
S_2
S_3
\vdots
S_N

ここで,S_i (2 \leqq i \leqq N) は 0 または 1 からなる i - 1 文字の文字列である.S_i の j 文字目 (1 \leqq j \leqq i - 1) が 0 のときビーバー i がビーバー j に敗北したことを,1 のときビーバー i がビーバー j に勝利したことを示す.情報に合致する試合結果が複数存在する場合は,そのうちどれを出力してもよい.

あるシナリオについて,情報に合致する試合結果が存在しない場合,No と出力せよ.


制約

  • 1 \leqq Q.
  • 3 \leqq N \leqq 5\,000.
  • 0 \leqq M \leqq \dfrac{1}{6}N(N - 1)(N - 2).
  • Q 個のシナリオにおける N の値の合計は 5\,000 以下である.
  • 入力される値はすべて整数である.

小課題

  1. (5 点) M = 0.
  2. (12 点) M \leqq N - 2.
  3. (15 点) M \leqq \dfrac14(N - 1)^2.
  4. (10 点) Q 個のシナリオにおける N の値の合計は 7 以下である.
  5. (23 点) Q 個のシナリオにおける N の値の合計は 20 以下である.
  6. (19 点) Q 個のシナリオにおける N の値の合計は 150 以下である.
  7. (8 点) Q 個のシナリオにおける N の値の合計は 600 以下である.
  8. (8 点) 追加の制約はない.

入力例 1

2
3 1
4 4

出力例 1

Yes
0
10
No

この入力例は Q = 2 個のシナリオからなる.

この出力例におけるシナリオ 1 の試合結果ではビーバー 1 がビーバー 2 に勝利し,ビーバー 2 がビーバー 3 に勝利し,ビーバー 3 がビーバー 1 に勝利した.したがって,3 匹のビーバー 1, 2, 3 は三すくみである.この他に 3 匹のビーバーを選ぶ方法はないので,三すくみとなるような 3 匹のビーバーの選び方はちょうど 1 通りである.

シナリオ 1 に対応する出力として,他に以下のようなものが考えられる.

Yes
1
01

シナリオ 2 では情報に合致する試合結果は存在しない.したがって,No と出力する.

この入力例は小課題 4, 5, 6, 7, 8 の制約を満たす.


入力例 2

1
5 3

出力例 2

Yes
0
11
001
0101

この出力例におけるシナリオ 1 の試合結果ではビーバー 1 がビーバー 4 に勝利し,ビーバー 4 がビーバー 3 に勝利し,ビーバー 3 がビーバー 1 に勝利した.したがって,3 匹のビーバー 1, 3, 4 は三すくみである.この他に三すくみとなるような 3 匹のビーバーの選び方として,ビーバー 2, 3, 4 を選ぶ方法とビーバー 3, 4, 5 を選ぶ方法がある.したがって,三すくみとなるような 3 匹のビーバーの選び方はちょうど 3 通りである.

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす.


Source Name

JOIG 2023/2024 春季トレーニング Contest Day2