Codeforces Global Round 13 問題文和訳
- A. K-th Largest Value / K-е наибольшее (500点)
- B. Minimal Cost / Минимальная стоимость (750点)
- C. Pekora and Trampoline / Pekora и батуты (1000点)
- D. Zookeeper and The Infinite Zoo / Хранительница Бесконечного Зоопарка (1250点)
- E. Fib-tree / Фиб-дерево (1750点)
- F. Magnets / Магниты (2000点)
- G. Switch and Flip / Обменяйте и переверните (2250点)
- H. Yuezheng Ling and Dynamic Tree / Yuezheng Ling и динамическое дерево (3000点)
- I. Ruler Of The Zoo / Правитель зоопарка (5000点)
A. K-th Largest Value / K-е наибольшее (500点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1 x
: に値 を代入する2 k
: 配列内の 番目に大きい値を出力する
注意点として配列内の 番目に大きい値 は次のように定義されています。
- 配列を降順*1にソートし、その 番目の要素を返す
例えば、配列 を降順にソートすると となり、その2番目の要素は となるため、この配列の2番目に大きい要素は となります。
入力
1行目には2つの整数 が与えられる、これらは配列の長さとクエリの数である。
2行目には 個の整数 が与えられる、これらは初期配列の要素である。
つづく 行には2つの整数が与えられる。1つ目の整数は で、これはクエリの種類である。
- の場合、2つ目の整数は で、これは修正する数の位置である。 に値 を代入しなければならない
- の場合、2つ目の整数は で、このとき配列の 番目に大きい値を出力しなければならない
2番目の種類の( を満たす)クエリが少なくとも1個は存在することは保証されている。
出力
各2番目の種類のクエリについて、単一の整数を出力せよ、その整数とはクエリへの答えである。
入出力例
5 5 1 1 0 1 0 2 3 1 2 2 3 2 1 2 5
1 0 1 0
注記
初期状態において、 である。
1番目の操作では、3番目に大きい値である を出力しています。
2番目の操作では、 に値 を代入していて、 は になります。
3番目の操作では、3番目に大きい値である を出力しています。
4番目の操作では、1番目に大きい値である を出力しています。
5番目の操作では、5番目に大きい値である を出力しています。
B. Minimal Cost / Минимальная стоимость (750点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
行 列の頂点(ノード)を とします。
初期状態において各 について 行目にはちょうど1つの障害物が頂点 に存在します。このグラフ上の辺を移動して(障害物を通過することはできない)頂点 から頂点 へ到達できるようにいくつかの障害物を移動させたいと思っています。辺によって隣接する障害物のない頂点に障害物を移動させるには、以下のように 枚、もしくは 枚のコインがかかります。
- 頂点 に障害物があり、頂点 もしくは が存在して、その頂点に現在障害物がない場合、 枚のコインを使うことでこの頂点に障害物を移動させることができる
- 頂点 に障害物があり、頂点 もしくは が存在して、その頂点に現在障害物がない場合、 枚のコインを使うことでこの頂点に障害物を移動させることができる
- 格子(グリッド)の外に障害物を移動させることができないことに注意せよ。例えば、 から へ障害物を移動させることはできない
よりよく理解するためには上図を参照してください。
障害物を通過することなくこのグラフ上の辺を移動して頂点 から頂点 へ到達するために使わなければならないコインの最小枚数を計算しなければなりません。
入力
1行目には単一の整数 が与えられる、これはテストケース数である。
各テストケースの1行目には3つの整数 が与えられる、これらはそれぞれグラフの行数と、縦方向と横方向に移動するために必要なコインの枚数である。
各テストケースの2行目には 個の整数 が与えられる、 は 行目の障害物は 頂点 にあることを表している。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、単一の整数を出力せよ、その整数とは障害物を通過することなくこのグラフ上の辺を移動して頂点 から頂点 へ到達するために支払わなければならないコインの最小枚数である。
問題の制約下では、そのような移動を可能にする方法が常に存在することは示すことができる。
入出力例
3 2 3 4 2 2 2 3 4 3 2 2 4 3 3 2
7 3 3
注記
1番目のサンプルでは、2つの障害物が と にあります。 にある障害物を に移動させ、そののち に移動させることができます。総コストは コインです。
2番目のサンプルでは、2つの障害物が と にあります。 にある障害物を に移動させることができます。コストは コインです。
C. Pekora and Trampoline / Pekora и батуты (1000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
ぺこら*2は何回かのパスにおいてトランポリンで跳ぶことができます。彼女は、好きなトランポリンで跳ぶことでパスを開始します。
ぺこらがトランポリン で跳んだ瞬間、このトランポリンは彼女を位置 へ打ち上げ、 は になります。つまり、 が のままとなる の場合を除いて、 は だけ小さくなります。
位置 にトランポリンがない場合、このパスは終了します。そうでなければ、ぺこらは上記と同じルールで、位置 にあるトランポリンで跳ねてパスを継続させます。
ぺこらは よりも大きな位置(トランポリンがない場所)に着地するまでパス中のジャンプを止めることはできません。可哀そうなぺこら!
ぺこらは悪戯好きな兎で全ての を に減らしてトランポリン公園を台無しにしたいと思っています。全ての を に減らすのに必要な最小パス数は何個でしょう?
入力
1行目には単一の整数 が与えられる、これはテストケース数である。
各テストケースの1行目には単一の整数 が与えられる、これはトランポリンの個数である。
各テストケースの2行目には 個の整数 が与えられる、 は 番目のトランポリンの強度である。
全てのテストケースでの の和が を超えないことは保証されている。
出力
各テストケースについて、単一の整数を出力せよ、その整数とは全ての を に減らすのにぺこらが必要とする最小パス数である。
入出力例
3 7 1 4 2 2 2 2 2 2 2 3 5 1 1 1 1 1
4 3 0
注記
1番目のテストケースでのぺこらがとることができる最適なパス列を示しています。(太字の数字がこれらのパスの間にぺこらが跳ぶ位置です。)
2番目のテストケースでの最適なパス列は下の通りです。
3番目のテストケースでは、全ての がすでに となっています。
D. Zookeeper and The Infinite Zoo / Хранительница Бесконечного Зоопарка (1250点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
無限動物園は、 とラベル附けられた無限頂点のグラフで表すことができます。 のとき、またその時に限り頂点 から頂点 への有向辺が存在します、ここで とはビットAND演算*4を表します。グラフには他の辺は存在しません。
Zookeeper*5は 個のクエリを投げてきます。 番目のクエリでは彼女は有向辺を辿っていくことで頂点 から へ着くことができるかを訊いてきます。
入力
1行目には単一の整数 が与えられる、これはクエリの個数である。
つづく 行の 行目には2つの整数 が与えられる、これがZookeeperによるクエリである。
出力
個クエリの 番目について、Zookeeperが頂点 から へ着くことができる場合、"YES
"と出力せよ。そうでない場合、"NO
"と出力せよ。
答えの大文字小文字はいかなる組み合わせでもよい。例えば、答えが"YES
"の場合、"Yes
"や"yeS
"といった出力は正解とみなされる。
入出力例
5 1 4 3 6 1 6 6 2 5 5
YES YES NO NO YES
注記
頂点 上の部分グラフを以下に示します。
E. Fib-tree / Фиб-дерево (1750点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
- 任意の整数 について
頂点の木が与えられます。木とは、サイクルのない無向連結グラフです。
頂点数が であるような が存在し*7、以下の条件のうち少なくとも1つが満たされる場合、その木をFib-treeと呼びます。
- この木は 頂点のみから成る
- 木から取り除けば2つのFib-treeとに分割できるような辺が存在する
与えられた木がFib-treeであるかどうか判別してください。
入力
1行目には単一の整数 が与えられる、これは木の頂点数である。
行が続き、それぞれの行には2つの整数 が与えられる、これは頂点 と の間の辺を表している。与えられた辺が木を形成することは保証されている。
出力
与えられた木がFib-treeである場合、"YES
"と出力せよ。そうでない場合、"NO
"と出力せよ。
答えの大文字小文字はいかなる組み合わせでもよい。例えば、答えが"YES
"の場合、"Yes
"や"yeS
"といった出力は正解とみなされる。
入出力例
3 1 2 2 3
YES
5 1 2 1 3 1 4 1 5
NO
5 1 3 1 2 4 5 3 4
YES
注記
1番目のサンプルでは、辺 を取り除くことで木をそれぞれサイズ と の つの木に分割することができます。サイズ の木はサイズ の木 つに分割することができるので、どんな木でもFib-treeとなります。
2番目のサンプルでは、どの辺を取り除くいても、サイズ と の つの木に分割します。 は任意の に対して ではないので、Fib-treeではありません。
3番目のサンプルでは、全ての木がFib-treeとなるような可能な分割方法を1つ考えます:
F. Magnets / Магниты (2000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
東風谷早苗*8は磁石で遊んでいます。その磁石の中には消磁されているものがあることに気づき、彼女はそれがどれなのか知りたいと思っています。
磁石が 個あり、これらは次の 種類のいずれかです。
N
S
-
この磁石は消磁されている
これらの磁石の種類は前もっては分からないことに注意してください。
磁石同士の力を測定できる機械を持っていて、それを最大 回用いることができます。
機械の左側に磁石をいくつか置いて、右側にもいくつか置いて、機械を起動させることができます。明らかに1つの磁石は高々1か所にしか置けません(全ての磁石を用いる必要はありません)。同じ磁石を複数のクエリで用いることができます。
そうすると、機械はこれらの磁石が生み出す力を示します。形式的には、 をそれぞれ左側にある N
とS
の磁石の数とし、 も右側にある同様のものとします。このとき、これらの磁石の力は となります。力は符号附きの値であることに注意してください。
しかし、力の絶対値が よりも真に大きいとき、機械は粉々に壊れてしまいます。
機械を壊すことなく、全てのタイプが-
である(消磁されている)磁石を見つけなければなりません。
相互入出力機(インタラクタ)は状況適用的ではないことに気を付けて下さい。磁石の種類は相互入出力の開始前に固定されていて、クエリによって変わることはありません。
種類が-
でない磁石が少なくとも つ存在し、種類が-
である磁石が少なくとも つ存在することは保証されています。
入力
1行目には単一の整数 が与えられる、 はテストケース数である。
相互入出力
各テストケースにおいて、初めに1つの整数 を読み取らなければならない、 は磁石の個数である。
全てのテストケースでの の和が を超えないことは保証されている。
そののち、機械にいくつかの磁石を入れ、出力によってクエリを作ることができる。
各クエリは3行で出力しなければなりません。
- 1行目には”
? l r
”(引用符なし)と出力せよ、 はそれぞれ左右に置く磁石の個数を表す - 2行目には 個の整数 を出力せよ、 これらは左側に置く磁石のインデックスである
- 3行目には 個の整数 を出力せよ、 これらは右側に置く磁石のインデックスである
- 同じ磁石を同一クエリ内で両側に置くことはできない。形式的には任意の について となることを保証しなければならない。しかし、一部使わないままにしておく磁石があってもよい
クエリの出力後、改行出力、出力バッファのflushを忘れないようにせよ。そうするためには次を利用せよ。
- C++の場合、
fflush(stdout)
やcout.flush()
- Javaの場合、
System.out.flush()
- Pascalの場合、
flush(output)
- Pythonの場合、
stdout.flush()
- 他の言語の場合は、ドキュメントを参照せよ
そののち、1つの整数 を読み取らなければならない、これは磁石の生み出す力である。
クエリが無効な場合(クエリ制限を超えた場合や、機械が壊れた場合、引数が無効な場合)、相互入出力機は直ちに終了することに気をつけよ。この場合、他の恣意的な結果ではなくWrong Answer
という結果を受けるためにプログラムを終了させよ。
答えに自信がある場合、次の形式で報告せよ。
- ”
! k A
”、ここで は見つけた磁石の数、 は見つかった種類-
の磁石のインデックスを表す 個の から の異なる整数の配列である。 の要素は任意の順で出力することができる - そののち、それが最後のテストケースである場合、プログラムを終了させなければなりません。そうでない場合、直ちに次のテストケースの処理を続けなければなりません。
相互入出力機は状況適用的ではないことに気を付けよ。磁石の種類は相互入出力の開始前に固定されていて、クエリによって変わることはない。
ハックケース
答案をハックするには、次の形式を用いよ。
1行目には単一の整数 を出力せよ、これはテストケース数である。
次に 個のテストケースを、それぞれ2行ずつ出力することで続けよ。
- 1行目には単一の整数 を出力せよ、これは磁石の数である
- 2行目には磁石の種類を表す
N
やS
、-
から成る長さ の文字列 を出力せよ - 各テストケースにおいて、種類が
-
でない磁石が少なくとも つ存在し、種類が-
である磁石が少なくとも つ存在することは保証しなければなりません。また、全てのテストケースでの の和が を超えないことも保証しなければなりません。
入出力例
1 4 0 1 0 0
? 1 1 3 4 ? 1 2 1 2 3 ? 1 1 1 4 ? 1 1 1 3 ! 2 3 4
注記
サンプルの空行は、相互入出力機のよりよい理解のためのものです。これらを出力する必要はありません。
このサンプルでは、磁石の種類はNN--
です。
まず、左側に3番目の磁石を置き、右側に4番目の磁石を置きます。どちらも種類は-
であるため、力は生み出されません。
次に、左側に1番目の磁石を置き、右側に2番目と3番目の磁石を置きます。3番目の磁石の種類は-
で、他の2つの磁石の種類はN
なので、生成される力は となります。
つづく2つのクエリでは、右側には種類-
の磁石しかないため、力は となります。
すると、種類-
の磁石は3番目と4番目の磁石であると判断でき、! 2 3 4
と出力して終了します。
G. Switch and Flip / Обменяйте и переверните (2250点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1回の操作で次のようなことを行えます。
- つの異なるインデックス を選ぶ
- 位置 にあるコインを入れ替える
- 位置 にある2枚のコインを裏返す(もし最初に表向きになっていれば裏向きになり、またその逆も同様)
全てを実行すると最終的にコイン が位置 で表を向いているような最大 個の操作の列を構築してください。
操作の数を最小化する必要はありません。
入力
1行目には1つの整数 が与えられる、これはコインの枚数である。
2行目には 個の整数 が与えられる。
出力
1行目には1つの整数 を出力せよ、これは行う操作の回数である。
つづく 行には2つの整数 を出力せよ、これは操作で選択する位置である。
入出力例
3 2 1 3
3 1 3 3 2 3 1
5 1 2 3 4 5
0
注記
表向きのコイン を と、裏向きのコイン を と表記します。
1番目のサンプルで行われたる一連の操作はコインを次のように変化させます。
2番目のサンプルでは、すでにコインは所定の位置あるため、交換の必要はありません。
H. Yuezheng Ling and Dynamic Tree / Yuezheng Ling и динамическое дерево (3000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
洛天依はあなたに 番目の頂点の親が について であることを伝え、 種類の 個のクエリを実行するように頼んできます。
入力
1行目には2つの整数 が与えられる、これらはそれぞれ頂点数とクエリ数である。
2行目には 個の整数 が与えられる、 は頂点 の親である。
つづく 行にはクエリが与えられる。各クエリについて1つ目の整数は or であり、クエリの種類である。
の場合、これは1番目の種類のクエリを表す。こののち、3つの整数 が続く、これらは である全ての について に を代入することを表す。
の場合、これは2番目の種類のクエリを表す。こののち、2つの整数 が続き、 のLCAを求めなければならない。
2番目の種類のクエリが少なくとも1回来ることは保証されている。
出力
各2番目の種類のクエリについて、新しい行に答えを出力せよ。
入出力例
6 4 1 2 3 3 4 2 3 4 1 2 3 1 2 5 6 2 2 3
3 3 1
注記
入出力例の木は次のようになります。
1番目の種類のクエリの後、木は変化し、次のようになります。
I. Ruler Of The Zoo / Правитель зоопарка (5000点)
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
最初、動物 が王で、他の動物が動物 を先頭に、動物 を最後尾とする待ち行列に並びます。待ち行列の先頭の動物は王に戦いを挑み、力の強い動物が勝ちます。勝者が王となり、敗者は待ち行列の最後尾に並びます。
連勝した動物が動物園全体の支配者となります。各動物の強さは何連勝しているかによって決まります。動物 の強さは 連勝中で 、 連勝中で 、 連勝中で となります。初期状態では全員が 連勝の状態です。
全ての動物について かつ が成り立ちます。また、 の値は相異なります( 個全ての値がどの組も互いに等しくない)。
言い換えると、王でない動物の強さは です。王の強さは通常 または です。例外として、最初のターンでは最初の王(動物 )の強さは です。
何回の戦闘の後、誰が新しい支配者になるでしょうか? それとも、動物たちは永遠に戦いを続け、誰も支配者にならないのでしょうか?
出力
単一行に2つの整数を出力せよ。1つ目の整数は支配者となる動物のインデックスで、2つ目の整数はその動物が支配者になるまでに行われる戦いの数である。
動物が無限に戦う場合、代わりに-1 -1
と出力せよ。
入出力例
4 5 1 2 10 8 11 9 0 3 7 4 6
-1 -1
5 11 7 12 8 6 14 2 1 10 13 0 9 5 3 4
1 7
注記
以下に2つ目のサンプルでの事象列について説明します。戦闘 において、王(動物 )の強さが であることに注意してください。動物 戦闘 で勝利し、トーナメントは戦闘 で終了します。
*1:non-increasing orderなので正確には非昇順
*2:Virtual YouTuberの兎田ぺこら
*3:実在する
*5:Хранительница Зоопарк 動物園の職員という意味だが、大文字始まりなので固有名詞のように用いられている。また、後の問題から管理人等の意味でとった方が良い
*6:伊[fiboˈnattʃi] Leonardo Fibonacci この数列で有名な人
*7:原文をそのまま訳すと「ある について頂点数が であり」
*9:中/yɛ.ʈʂəŋ liŋ/ 拼音: yuèzhèng líng 楽正綾 中国語VOCALOID
*10:中/luɔ tʰiɛn.i/ 拼音: luò tiānyī 中国語VOCALOID
*11:日本語版Wikipediaには生物用語としてのページしかないため英語版にリンクを繋げた
*12:本当は添え字は であると思われる