← 返回题目列表

AtCoder · joiopen2025_c

C. 心灵感应

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

テレパシー (Telepathy) - 原题 PDF 第 1 页
原题PDF第1页
テレパシー (Telepathy) - 原题 PDF 第 2 页
原题PDF第2页
テレパシー (Telepathy) - 原题 PDF 第 3 页
原题PDF第3页
テレパシー (Telepathy) - 原题 PDF 第 4 页
原题PDF第4页
テレパシー (Telepathy) - 原题 PDF 第 5 页
原题PDF第5页
テレパシー (Telepathy) - 原题 PDF 第 6 页
原题PDF第6页
テレパシー (Telepathy) - 原题 PDF 第 7 页
原题PDF第7页
可复制的 PDF 提取文本
The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy

                 テレパシー(Telepathy)



  Aitana とBruno はボリビアの国立公園を訪れた.国立公園にはN 個の地点があり,2 地点を結ぶ道路が

N −1 本ある.どの地点からどの地点へもいくつかの道路をたどって移動できるようになっている.

  Aitana とBruno は国立公園で歩いているときにはぐれてしまった.これから,彼らは同じ地点に同じタ

イミングで到達して再会しなければならない.しかし,彼らはアマゾンの深い熱帯雨林の中にいるため,通

信を行うことはできない.そんな彼らが唯一頼れるものは,それぞれが持っている国立公園の道路の構造を

表した地図である.彼らはあらかじめ地図上の各地点に0, 1, . . . , N −1 のラベルを付けていたが,2 人のラ

ベル付けは異なるかもしれない.

 これから再会のための移動を開始する.Aitana とBruno は1 ターンごとに「今いる地点と道路で直接結

ばれている地点のうちひとつに移動する」「今いる地点にとどまる」のどちらかの行動を2 人同時に行う.

  Aitana とBruno が再会する戦略を実装したプログラムを作成せよ.この問題では,Aitana の現在地から

Bruno の現在地に移動するために通る道路の本数の最小値をd として,6d ターン以内で再会すれば満点が

得られる.道路の途中で同じ場所に来ても再会とはみなされないことに注意せよ.

 この問題では,1 回のプログラムの実行でQ 個のシナリオについて解かなければならない.


問題の詳細

 このセクションでは問題をより厳密に説明する.国立公園のN 個の地点には0 からN −1 のID が割り
当てられており,j 番目(0 ≦j ≦N −2) の道路はID がu j の地点とID がv j の地点を結んでいる.ID がi
(0 ≦i ≦N −1) の地点には,Aitana の地図にはラベルpi が,Bruno の地図にはラベルqi が書かれている.
ここで,(p0, p1, . . . , pN−1) および(q0, q1, . . . , qN−1) は0 からN −1 までの整数の並び替えである.
  Aitana が知っている情報は,各j = 0, 1, . . . , N −2 についてラベルAj の地点とラベルBj の地点を結ぶ道
路があること,Aitana が現在ラベルS の地点にいることである.ここでのラベルはAitana の地図のラベル
付けに基づく.すなわち,j 番目(0 ≦j ≦N −2) の道路はラベルpuj の地点とラベルpv j の地点を結ぶこ
とになり,Aitana の現在地のID をs としてS = ps となる.ただし,道路が順番通りに与えられるとは限
らず,同じ道路についてもuj, v j に対応するラベルの順に与えられるとは限らない.同様に,Bruno が知っ
ている情報は,各j = 0, 1, . . . , N −2 についてラベルC j の地点とラベルDj の地点を結ぶ道路があること,
Bruno が現在ラベルT の地点にいることである.ここでのラベルはBruno の地図のラベル付けに基づく.
特に,Bruno の現在地のID をt としてT = qt となる.
 この情報を頼りに,Aitana とBruno が今後10N ターンでどのように動くかを独立に決める.すなわち,
Aitana は彼女の移動方法を表すラベルの列x0, x1, . . . , x10N を,Bruno は彼の移動方法を表すラベルの列
y0, y1, . . . , y10N を,それぞれ独立に決めることになる.これは以下の条件を満たす必要がある.





                      テレパシー– 1 / 7

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy


    • x0 = S であり,各k (1 ≦k ≦10N) に対して(Aitana の地図における)ラベルxk−1, xk の地点は同じ

   か互いに道路で直接結ばれた地点である.

    • y0 = T であり,各k (1 ≦k ≦10N) に対して(Bruno の地図における)ラベルyk−1, yk の地点は同じ

   か互いに道路で直接結ばれた地点である.

Aitana とBruno は,xk とyk が同じ地点を指す最小のk のターン数で再会することになる.この値をk∗と
したとき,k∗≦6d であれば満点が得られる.


実装の詳細

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

 あなたの提出するファイルはtelepathy.cpp という名前である.#include プリプロセッサ指令によっ

てtelepathy.h を読み込み,以下の関数を実装していなければならない.

    • vector<int> Aitana(int N, vector<int> A, vector<int> B, int S, int subtask)

    この関数ではAitana の戦略を実装する.この関数は,各シナリオについて1 回ずつ,合計Q 回呼び

   出される.

    ◦引数N は,国立公園の地点の個数N である.

     ◦引数A, B は長さN −1 の配列であり,各j (0 ≦j ≦N −2) について,A[j], B[j] は道路が結ぶ
         2 地点のラベルA j, Bj である.
    ◦引数S は,Aitana の現在地のラベルS である.

     ◦引数subtask は,テストケースが満たす小課題の番号(1, 2, 3 のいずれか)である.
     ◦戻り値は,Aitana の移動方法を表す配列[x0, x1, . . . , x10N] である.
    ◦戻り値の配列の長さは10N + 1 ちょうどでなければならない.これが満たされない場合は,不正

        解[1] と判定される.
    ◦各k (0 ≦k ≦10N) について,0 ≦xk ≦N −1 が満たされなければならない.これが満たされな
      い場合は,不正解[2] と判定される.
      ◦x0 = S でなければならない.これが満たされない場合は,不正解[3] と判定される.
    ◦各k (1 ≦k ≦10N) について,ラベルxk−1, xk の地点は同じか互いに道路で直接結ばれた地点で
     なければならない.これが満たされない場合は,不正解[4] と判定される.

   なお,以上の説明における「ラベル」はAitana の地図におけるラベル付けに基づく.

    • vector<int> Bruno(int N, vector<int> C, vector<int> D, int T, int subtask)

    この関数ではBruno の戦略を実装する.この関数は,各シナリオについて関数Aitana が呼び出され

   た直後に1 回ずつ,合計Q 回呼び出される.

    ◦引数N は,国立公園の地点の個数N である.

     ◦引数C, D は長さN −1 の配列であり,各j (0 ≦j ≦N −2) について,C[j], D[j] は道路が結ぶ



                      テレパシー– 2 / 7

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy


         2 地点のラベルC j, D j である.
    ◦引数T は,Bruno の現在地のラベルT である.

     ◦引数subtask は,テストケースが満たす小課題の番号(1, 2, 3 のいずれか)である.
     ◦戻り値は,Bruno の移動方法を表す配列[y0, y1, . . . , y10N] である.
    ◦戻り値の配列の長さは10N + 1 ちょうどでなければならない.これが満たされない場合は,不正

        解[5] と判定される.
    ◦各k (0 ≦k ≦10N) について,0 ≦yk ≦N −1 が満たされなければならない.これが満たされな
      い場合は,不正解[6] と判定される.
      ◦y0 = T でなければならない.これが満たされない場合は,不正解[7] と判定される.
    ◦各k (1 ≦k ≦10N) について,ラベルyk−1, yk の地点は同じか互いに道路で直接結ばれた地点で
     なければならない.これが満たされない場合は,不正解[8] と判定される.

   なお,以上の説明における「ラベル」はBruno の地図におけるラベル付けに基づく.

  Aitana とBruno が10N ターン以下で再会できなかった場合,すなわち各k (0 ≦k ≦10N) について,
Aitana のラベルxk が指す地点とBruno のラベルyk が指す地点が異なる場合は,不正解[9] と判定される.


重要な注意

    • 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.採点時に

    は,このプログラムはAitana 側,Bruno 側として2 個のプロセスとして実行されるので,Aitana 側

     とBruno 側でプログラム中のグローバル変数を共有することはできない.

    • あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもや

   りとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.


コンパイル・実行の方法


 作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウン

ロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサ

ンプルも含まれている.

 採点プログラムのサンプルは1 つのファイルからなる.そのファイルはgrader.cpp である.作成した

プログラムをテストするには,grader.cpp, telepathy.cpp, telepathy.h を同じディレクトリに置き,

次のようにコマンドを実行する.

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





                      テレパシー– 3 / 7

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy


 なお,アーカイブの中に含まれているcompile.sh というファイルを代わりに実行してもよい.その場

合,次のようにコマンドを実行する.

     ./compile.sh

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

 実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムの

サンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に

結果を出力する.


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

 採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.ここで,シナリオには0 から

Q −1 までの番号が付けられている.また,subtask は小課題の番号である.

      subtask

    Q

   (シナリオ0 のデータ)

   (シナリオ1 のデータ)
                                 ...

   (シナリオQ −1 のデータ)



 各シナリオのデータは以下の形式で読み込む.


    N

       u0 v0
       u1 v1
                                 ...

      uN−2 vN−2
       p0 p1 . . . pN−1
       q0 q1 . . . qN−1

       s t

 各変数の意味については,問題文の問題の詳細セクションを参照せよ.Aitana とBruno の地図の情報を

直接与えるわけではないことに注意すること.





                      テレパシー– 4 / 7

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy


  関数Aitana, Bruno に引数として与えられる道路の情報のシャッフル方法は,実行ごとに結果が変わら

ない擬似乱数を用いて一様に無作為に選ばれる.シードの値を変更したい場合は

     ./grader 20250615

のように1 個目の引数に整数値を与えて実行せよ.


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


 採点プログラムのサンプルは,各シナリオごとに標準出力へシナリオの番号とともに以下の情報を出力す

る(引用符は実際には出力されない).合計でQ 行出力する.

    • 正解の場合,Aitana とBruno が再会するまでのターン数k∗とAitana の現在地からBruno の現在地

   に移動するために通る道路の本数の最小値d がその順で“Case #0: Accepted 5 2” のように出力

   される.

    • 不正解の場合,不正解の種類が“Case #0: Wrong Answer [1]” のように出力される.


採点に関する注意


 実際の採点プログラムの特定のシナリオの入力は,プログラムの実行前に決まっておらず,それ以前のシ

ナリオの入力に対する関数Aitana, Bruno の戻り値に応じて決定される.


制約

 この問題では,1 回のプログラムの実行で201 個以下のシナリオについて解かなければならない,すなわ

ち1 ≦Q ≦201 を満たす.各シナリオは以下の制約を満たす.

    • 2 ≦N ≦200.
    • (p0, p1, . . . , pN−1) は0 からN −1 までの整数の並び替えである.
    • (q0, q1, . . . , qN−1) は0 からN −1 までの整数の並び替えである.
    • 0 ≦u j ≦N −1 (0 ≦j ≦N −2).
    • 0 ≦v j ≦N −1 (0 ≦j ≦N −2).
    • どの地点からどの地点へもいくつかの道路をたどって移動できる.

    • 0 ≦s ≦N −1.

    • 0 ≦t ≦N −1.

    • s , t.





                      テレパシー– 5 / 7

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy



小課題

    1. (40 点) (p0, p1, . . . , pN−1) = (q0, q1, . . . , qN−1) = (0, 1, . . . , N −1).
    2. (40 点) u j = j,vj =  j + 1 (0 ≦j ≦N −2).
    3. (20 点) 追加の制約はない.

 なお,小課題3 では,関数Aitana, Bruno の引数subtask が1, 2 のケースも対象になることに注意せよ.


得点の決定方法

  Aitana とBruno が再会するまでのターン数をk∗とし,Aitana の現在地からBruno の現在地に移動する
ために通る道路の本数の最小値をd とする.また,小課題のすべてのシナリオにわたるk∗ の最大値をα と                                                                                                         d
する.

 小課題に含まれるテストケースで1 つでも不正解があった場合,その小課題のあなたの得点は0 点とな

る.そうでない場合,小課題のあなたの得点は以下のように決定される(複数の条件を満たす場合,得点の

高い方が適用される).

    • 小課題のすべてのシナリオでk∗≦10N を満たすとき,配点の15%
    • 小課題のすべてのシナリオでk∗≦max(10d, N) を満たすとき,配点の25%
    • 小課題のすべてのシナリオでk∗≦10d を満たすとき:

     ◦9 < α ≦10 のとき,配点の40%

     ◦6 < α ≦9 のとき,配点の⌊100 −20(α −6)⌋%

     ◦α ≦6 のとき,配点の100%





                      テレパシー– 6 / 7

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)

                                                                  JOI Open Contest

                                                                            June 15, 2025


                                                                           telepathy



やり取りの例


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

なお,以下の表では戻り値は一部省略しているが,長さ31 の配列を返さなければならない.


  入力例1 関数の呼び出しの例

              Aitana の呼び出し・戻り値             Bruno の呼び出し・戻り値

   2        Aitana(3, [0, 1], [1, 2], 1, 2)

   1        [1, 0, 0, 1, 2, ..., 2]

   3                                         Bruno(3, [1, 0], [2, 0], 2, 2)

   0 1                                       [2, 2, 0, 0, 1, ..., 1]

   1 2

   2 1 0

   2 0 1

   1 0

 この例では,国立公園の道路の構造およびAitana, Bruno の地図は以下の図のようになっている.


               Aitana の地図                                          Bruno の地図

                                                               ID          ID          ID
                     Aitana の現在地                 0       1       2             Bruno の現在地

           2      1      0        国立公園の道路の構造            2      0      1



  Aitana は各ターンで(彼女の地図における)ラベル1, 0, 0, 1, 2, . . . , 2 の地点にいるように移動する.Bruno

は(彼の地図における)ラベル2, 2, 0, 0, 1, . . . , 1 の地点にいるように移動する.初めて場所が一致するのは

3 ターン目が終わった直後である.このとき,Aitana は彼女の地図でラベル1 の地点におり,Bruno は彼の

地図でラベル0 の地点にいるため,両者は同じ地点にいる.





                      テレパシー– 7 / 7