AT_joi2026final_c.マルチコミュニケーション 2 (Multi Communication 2)

K 理事長は JOI ファイナルステージの参加者にゲームを用意した． K 理事長は各マスに非負整数が書かれた $ N \times N $ マスの表 $ A $ を隠し持っている． $ A $ の上から $ i + 1 $ 行目 ( $ 0 \leqq i \leqq N - 1 $ )，左から $ j + 1 $ 列目 ( $ 0 \leqq j \leqq N - 1 $ ) のマスに書かれた非負整数を $ A_{i,j} $ とする． ここで， $ A $ は以下の条件を満たす．

• $ 0 \leqq i \leqq N - 1 $ を満たす各 $ i $ に対して， $ A_{i,i} = 0 $ ．
• $ 0 \leqq i < j \leqq N - 1 $ を満たす各 $ i, j $ に対して， $ A_{i,j} = A_{j,i} $ ．

頂点 $ i $ と頂点 $ j $ の間 ( $ 0 \leqq i < j \leqq N - 1 $ ) の辺の重みが $ A_{i,j} $ であるような $ N $ 頂点の重み付き無向グラフの最小全域木の重みを $ X $ とする． すなわち， $ X $ は以下の手順で求められる値である．参加者全員で協力して $ X $ の値を求めることがこのゲームの目標である．

1. $ x = 0 $ とする．
2. $ N $ 頂点の無向グラフ $ G $ を考える． $ G $ の頂点には $ 0, 1, \dots, N - 1 $ の番号が付けられている．はじめ， $ G $ には辺が張られていない．
3. 以下の操作を $ N - 1 $ 回繰り返す． $ N - 1 $ 回の操作が終了した後の $ x $ の値を $ X $ とする．
   1. 現在いくつかの辺を通って頂点 $ 0 $ から到達可能である $ G $ の頂点を近い頂点， それ以外の $ G $ の頂点を遠い頂点と呼ぶ． 近い頂点 $ i $ と遠い頂点 $ j $ の組 $ (i, j) $ を， $ A_{i,j} \times N^2 + i \times N + j $ の値が最小になるように選ぶ． 近い頂点と遠い頂点がそれぞれ $ 1 $ つ以上存在し， $ (i, j) $ が一意に定まることが証明できる．
   2. 頂点 $ i $ と頂点 $ j $ を結ぶ辺を $ G $ に追加する．
   3. $ x \gets x + A_{i,j} $ と更新する．

$ R = \lfloor 5120 / N \rfloor $ と定義する ( $ \lfloor x \rfloor $ は $ x $ を超えない最大の整数を表す)． JOI ファイナルステージには $ R \times N $ 人の参加者がおり， $ N $ 人ずつ $ R $ 個のグループに分けられている． 各グループには $ 0 $ から $ R-1 $ までの番号が付けられており，グループ $ r $ ( $ 0 \leqq r \leqq R-1 $ ) の参加者にはそれぞれ $ (r, 0), (r, 1), \dots, (r, N-1) $ の番号が付けられている．

ゲームは以下のラウンドをラウンド $ 0, 1, 2, \dots $ の順に最大 $ R $ 回繰り返すことで行われる． ゲーム中は参加者同士でコミュニケーションを取ることはできないが，事前に戦略を共有することができる．

ラウンド $ r $ ( $ 0 \leqq r \leqq R-1 $ ) は以下の手順で行われる．

• $ i = 0, 1, \dots, N-1 $ の順に，K 理事長と参加者 $ (r, i) $ は以下のやりとりを行う．
  1. K 理事長は，参加者 $ (r, i) $ に以下の情報を与える．
     • 参加者の番号 $ (r, i) $
     • 表 $ A $ の $ i + 1 $ 行目の情報 $ A_{i,0}, A_{i,1}, \dots, A_{i,N-1} $
     • 前のラウンドの各参加者から参加者 $ (r, i) $ に送られた， $ 0 $ 以上 $ 2^{64} $ 未満の整数 $ B_{r,i,0}, B_{r,i,1}, \dots, B_{r,i,N-1} $
       • $ r > 0 $ の場合，これらの整数は以下で説明するやりとり 3 において決定される．
       • $ r = 0 $ の場合，便宜上 $ B_{r,i,0} = B_{r,i,1} = \dots = B_{r,i,N-1} = 0 $ とする．
  2. 参加者 $ (r, i) $ が $ X $ の値を求めることができたなら，K 理事長に $ X $ の値を回答する．ある参加者が回答を行ったら，その時点でゲームは終了する．
  3. 参加者 $ (r, i) $ は，各 $ j = 0, 1, \dots, N-1 $ について，参加者 $ (r+1, j) $ に送る $ 0 $ 以上 $ 2^{64} $ 未満の整数 $ B_{r+1,j,i} $ を決定し，K 理事長に伝える． $ r = R - 1 $ のとき参加者 $ (r+1, j) $ は存在しないが，その場合でも $ B_{r+1,j,i} $ を決定し，K 理事長に伝える必要がある．

回答した $ X $ の値が間違っている場合や，ラウンド $ R - 1 $ までに誰も $ X $ の値を回答しなかった場合，ゲームは失敗となる． ラウンド $ R - 1 $ までに正しい $ X $ の値を回答した場合ゲームは成功となり，行われたラウンド数 (ラウンド $ r $ に回答を行った場合，ラウンド数は $ r + 1 $ ) が少ないほど高い評価を得られる．

できるだけ少ないラウンド数でゲームを成功させるような，参加者たちの戦略を実装せよ．

null

null

実装の詳細

あなたの回答プログラムは，multi.h を #include プリプロセッサ指令で読み込み，以下の関数を実装しなければならない．

• std::vector<unsigned long long> strategy(int N, int r, int i, std::vector<unsigned long long> A, std::vector<unsigned long long> B)
  • 引数 N は表 $ A $ の行および列の個数 $ N $ を表す．
  • 引数 r, i は参加者の番号 $ (r, i) $ を表す．
  • 引数 A は長さ $ N $ の非負整数列であり，A[j] ( $ 0 \leqq j \leqq N - 1 $ ) は表 $ A $ の上から $ i + 1 $ 行目，左から $ j + 1 $ 列目のマスに書かれた非負整数 $ A_{i,j} $ を表す．
  • 引数 B は長さ $ N $ の非負整数列であり，B[j] ( $ 0 \leqq j \leqq N - 1 $ ) は参加者 $ (r-1, j) $ から参加者 $ (r, i) $ に送られた $ 0 $ 以上 $ 2^{64} $ 未満の整数 $ B_{r,i,j} $ を表す． $ r = 0 $ の場合は $ \texttt{B[j]} = 0 $ である．
  • この関数は，引数 A, B の情報が与えられたときに参加者 $ (r, i) $ のする行動を表す，長さが $ 1 $ または $ N $ である非負整数列を返さなければならない． 返り値の非負整数列の長さが $ 1 $ でも $ N $ でもない場合，不正解[1] と判定される．
    • $ X $ の値が $ x $ であると回答する場合，この関数は長さ $ 1 $ の非負整数列 $ (x) $ を返さなければならない．回答した値が間違っている場合，不正解[2] と判定される．
    • 回答を行わない場合，この関数は長さ $ N $ の非負整数列 $ B' $ を返さなければならない．
      • 各 $ j = 0, 1, \dots, N-1 $ について， $ B'[j] $ は参加者 $ (r, i) $ が参加者 $ (r+1, j) $ に送る整数 $ B_{r+1,j,i} $ を表す． これは $ 0 $ 以上 $ 2^{64} $ 未満の整数でなければならない． $ r = R - 1 $ のとき参加者 $ (r+1, j) $ は存在しないが，その場合でも $ B' $ の長さは $ N $ でなければならないことに注意せよ．
    • ラウンド $ R - 1 $ が終わるまでに，いずれかの参加者が回答を行わなければならない．どの参加者も回答を行わなかった場合，不正解[3] と判定される．
  • **この関数の返り値は引数のみから決定しなければならない．**特に，以前の strategy の呼び出しや実行時の乱数によって返り値が変化してはならないことに注意せよ． この関数が同じ引数に対して異なる値を返した場合，不正解[4] と判定される．
  • 与えられる引数は，ある表 $ A $ と提出された関数 strategy を使用してゲームを行った際に実際に表れるものであることが保証される． ただし，ラウンド $ 0, 1, \dots, R - 1 $ の順に呼び出されるとは限らないことに注意せよ．
  • 採点プログラムは 1 回の実行で 1 回以上のゲームを行う． $ 1 $ 回の実行において，この関数は最大 $ 10,240 $ 回呼び出される．

重要な注意

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

---

小課題

1. ( $ 5 $ 点) $ N \leqq 64 $ ， $ A_{i,j} \leqq 1 $ ( $ 0 \leqq i \leqq N - 1 $ ， $ 0 \leqq j \leqq N - 1 $ )．
2. ( $ 10 $ 点) $ A_{i,j} \leqq 1 $ ( $ 0 \leqq i \leqq N - 1 $ ， $ 0 \leqq j \leqq N - 1 $ )．
3. ( $ 15 $ 点) $ N \leqq 64 $ ．
4. ( $ 40 $ 点) $ A_{i,j} < 2^{20} $ ( $ 0 \leqq i \leqq N - 1 $ ， $ 0 \leqq j \leqq N - 1 $ )．
5. ( $ 15 $ 点) $ A_{i,j} < 2^{40} $ ( $ 0 \leqq i \leqq N - 1 $ ， $ 0 \leqq j \leqq N - 1 $ )．
6. ( $ 15 $ 点) 追加の制約はない．

採点基準

ある小課題のテストケースの中で， $ 1 $ つでも 不正解[1] 〜 [4] と判定されたものや， 実行時間制限超過，メモリ制限超過，実行時エラーと判定されたものがあった場合，その小課題の得点は $ 0 $ 点となる． それ以外の場合，その小課題のすべてのゲームにわたる，行われたラウンド数の最大値を $ S $ として，その小課題の得点は以下のように決定される．

小課題 3 の場合

• $ S $ にかかわらず，その小課題の配点の $ 100% $ ． $ S > 6 $ である場合，コンテストサイトにおいて「出力は部分的に正しい」と表記されることがあるが，得点には影響しない．

小課題 3 以外の場合

• $ S \leqq 6 $ のとき，その小課題の配点の $ 100% $ ．
• $ 7 \leqq S \leqq 9 $ のとき，その小課題の配点の $ (100 - 20 \cdot (S - 6))% $ ．
• $ 10 \leqq S \leqq 19 $ のとき，その小課題の配点の $ (40 - S)% $ ．
• $ 20 \leqq S $ のとき，その小課題の配点の $ 20% $ ．

コンパイル・実行の方法

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

採点プログラムのサンプルは $ 1 $ つのファイルからなる. そのファイルは grader.cpp である． 作成したプログラムをテストするには， これらのファイル grader.cpp, multi.cpp, multi.h を同じディレクトリに置き，次のようにコマンドを実行する．

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

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

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

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

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

採点プログラムのサンプルは $ 1 $ 回の実行で $ 1 $ 回以上のゲームを行う．

まず，採点プログラムのサンプルは標準入力からゲームの回数 $ T $ を受け取る． その後， $ T $ 回にわたって，以下の形式で表 $ A $ の情報を読み込む．

$ N $ $ A_{0,1} $ $ A_{0,2} $ $ A_{0,3} $ $ \cdots $ $ A_{0,N-1} $ $ A_{1,2} $ $ A_{1,3} $ $ \cdots $ $ A_{1,N-1} $ $ \vdots $ $ A_{N-2,N-1} $

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

採点プログラムのサンプルは標準出力へ $ T $ 行出力する． $ t $ 行目 ( $ 1 \leqq t \leqq T $ ) には $ t $ 回目のゲームの結果を以下の形式で出力する (引用符は実際には出力されない)．

• ゲームが成功した場合，そのゲームで行われたラウンド数が Accepted: 22 のように出力される．
• いずれかの不正解の条件に当てはまった場合，不正解の種類が Wrong Answer [4] のように出力される．

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

やりとりの例

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

Sample Explanation 1

ラウンド $ 0 $ では以下のやりとりが行われる．

• 参加者 $ (0, 0) $ は $ X $ の値を回答せず，参加者 $ (1, 0) $ に $ B_{1,0,0} = 0 $ を，参加者 $ (1, 1) $ に $ B_{1,1,0} = 1 $ を，参加者 $ (1, 2) $ に $ B_{1,2,0} = 2 $ を送る．
• 参加者 $ (0, 1) $ は $ X $ の値を回答せず，参加者 $ (1, 0) $ に $ B_{1,0,1} = 3 $ を，参加者 $ (1, 1) $ に $ B_{1,1,1} = 4 $ を，参加者 $ (1, 2) $ に $ B_{1,2,1} = 5 $ を送る．
• 参加者 $ (0, 2) $ は $ X $ の値を回答せず，参加者 $ (1, 0) $ に $ B_{1,0,2} = 6 $ を，参加者 $ (1, 1) $ に $ B_{1,1,2} = 7 $ を，参加者 $ (1, 2) $ に $ B_{1,2,2} = 8 $ を送る．

どの参加者も $ X $ の値を回答しなかったので，ゲームは次のラウンドに進む．

ラウンド $ 1 $ では以下のやりとりが行われる．

• 参加者 $ (1, 0) $ は参加者 $ (0, 0) $ から $ B_{1,0,0} = 0 $ を，参加者 $ (0, 1) $ から $ B_{1,0,1} = 3 $ を，参加者 $ (0, 2) $ から $ B_{1,0,2} = 6 $ を受け取り， $ X = 3 $ であると回答する． $ X $ の値を回答したため，この時点でゲームは終了する．

正しい $ X $ の値を回答したため，ゲームは成功となる．このゲームで行われたラウンド数は $ 2 $ である．

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

コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応する． また，コンテストサイトからダウンロードできるアーカイブの中には，さらなる入力例 sample-02-in.txt, sample-03-in.txt, sample-04-in.txt が存在する． sample-02-in.txt はすべての小課題の制約を満たし， sample-03-in.txt は小課題 $ 3, 4, 5, 6 $ の制約を満たし， sample-04-in.txt は小課題 $ 4, 5, 6 $ の制約を満たす．

Constraints

• $ 2 \leqq N \leqq 256 $ ．
• $ 0 \leqq A_{i,j} < 2^{48} $ ( $ 0 \leqq i \leqq N - 1 $ ， $ 0 \leqq j \leqq N - 1 $ )．
• $ A_{i,i} = 0 $ ( $ 0 \leqq i \leqq N - 1 $ )．
• $ A_{i,j} = A_{j,i} $ ( $ 0 \leqq i < j \leqq N - 1 $ )．
• $ N, A_{i,j} $ ( $ 0 \leqq i \leqq N - 1 $ ， $ 0 \leqq j \leqq N - 1 $ ) は整数である．