# 競プロ講習会第7回 Web資料
## ◎第7回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #7 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Vertual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
#### ◎公式解説
##### A～F問題
## ◎問題訳(意訳あり注意)
### ◎A. Fair Game
:::spoiler **クリックで展開**
TL:1s ML:256MB
#### ●問題
PetyaとVasyaはカードゲームを遊んでいます。$n$ 枚($n$は偶数)のカードがあり、それぞれに1つずつ整数が書かれています。
ゲームを始める前、Petyaがまず整数を1つ宣言します。次に、Vasyaがそれとは異なる整数を1つ宣言します。ゲームが始まると、各人は $n$ 枚のカードから自分の選んだ数字が書かれたカードを全て取ります。2人のどちらにも選ばれていないカードはそのまま残しておきます。
ゲームは、以下の条件を満たすとき、Fairであると見做されます。
* 誰にも取られず残されているカードが無く、2人の取ったカードの枚数が等しい。
2人が適切な数字を宣言することで、ゲームがFairとなることがあるかを答えて下さい。
#### ●入力
1行目に、$n\ (2 \le n \le 100)$ が与えられます。$n$ は偶数です。
2行目に、$n$ 個の整数 $a_1,a_2,\ ...\ a_n\ (1 \le a_i \le 100)$ が与えられます。 $a_i$ は $i$ 番目のカードに書かれている整数です。
#### ●出力
どのように2人が整数を宣言しても、Fairにならない場合は`NO`を出力してください。
そうでない場合は、1行目に`YES`を出力してください。
更に、Petya,Vasyaが宣言するべき整数を2行目に空白区切りで出力してください。
#### ●入出力例
##### 入力例1
```
4
11
27
27
11
```
##### 出力例1
```
YES
11 27
```
Petyaが11を、Vasyaが27を宣言することで、全てのカードが取られ、2人のカードの枚数が等しくなります。
##### 入力例2
```
2
6
6
```
##### 出力例2
```
NO
```
2人は同じ整数を宣言してはいけないので、Fairなゲームは不可能です。
##### 入力例3
```
6
10
20
30
20
10
20
```
##### 出力例3
```
NO
```
どう選んでも、カードが取られず残ってしまうので、Fairなゲームは不可能です。
##### 入力例4
```
6
1
1
2
2
3
3
```
##### 出力例4
```
NO
```
:::
---
### ◎B. Polycarp and Letters
:::spoiler **クリックで展開**
TL:2s ML:256MB
#### ●問題
Polycarp は小文字が好きで、大文字は嫌いです。彼は小文字と大文字のアルファベットのみからなる文字列 $s$ を受け取ります。
$A$ を文字列の位置の集合とするとき、次の条件を満たしていれば $A$ を *pretty* と呼ぶことにします。
- $A$ に含まれる位置の文字はすべて異なる小文字である
- $A$ に含まれる位置の間に大文字は存在しない(つまり、$s[j]$ が大文字かつ $a_1 < j < a_2 (a_1, a_2 \in A)$ となるような $j$ が存在しない)
位置の $pretty$ な集合について、集合に含まれる要素数の最大値を求めてください。
#### ●入力
最初の行に、整数 $n (1 \leq n \leq 200)$ として文字列 $s$ の長さが与えられます。
2行目には、小文字と大文字のアルファベットからなる文字列 $s$ が与えられます。
#### ●出力
$s$ の位置からなる $pretty$ な集合に含まれる要素数の最大値を求めてください。
#### ●入出力例
##### 入力例1
```
11
aaaaBaabAbA
```
##### 出力例1
```
2
```
この例では、求めたい位置としては $6$ と $8$、もしくは $7$ と $8$ が考えられます。位置 $6$ と $7$ には `a` が、位置 $8$ には `b` があります。
位置 $1$ と $8$ の組み合わせは、間に大文字の `B` が存在するため不適です。
##### 入力例2
```
12
zACaAbbaazzC
```
##### 出力例2
```
3
```
求めたい位置の例としては $7, 8, 11$ があります。3つの要素を含む *pretty* な集合は他にもあります。
##### 入力例3
```
3
ABC
```
##### 出力例3
```
0
```
与えられる文字列 $s$ に小文字がないため、答えは $0$ になります。
:::
---
### ◎C. Bus
:::spoiler **クリックで展開**
TL:2s ML:256MB
#### ●問題
バスが $x$ 軸の上を、 $x=0$ から $x=a$ に向かって進みます。$x=0$ から出発して $x=a$ に到着すると、すぐに $x=0$ に引き返します。そして $x=0$ に到着すると、再び $x=a$ に進むということを繰り返します。つまり、バスは $x=0$ から $x=a$ に移動した後に戻ってきます。$x=0$ から $x=a$ への移動と、 $x=a$ から $x=0$ への移動をそれぞれ *bus journey* と呼びます。合計して、バスは $k$ 回 *journey* を行う必要があります。
バスの燃料タンクの容量は $b$ リットルです。バスが $1$ 進むためには、ちょうど $1$ リットルのガソリンを消費します。バスの燃料タンクは満たされた状態で最初の *journey* を始めます。
ガソリンスタンドは $x=f$ の点に存在し、$x=0$ と $x=a$ の間にあります。 バスの経路に他のガソリンスタンドはありません。ガソリンスタンドを通過するときは、どちらの方向に進んでいても止まってガソリンを完全に補給することができます。したがって、タンクを満たすために止まった後、タンクには $b$ リットルのガソリンが含まれています。
$k$ 回の *journey* を行うためには、$x=f$ にあるガソリンスタンドで最小何回ガソリンを補給する必要があるでしょうか？最初の *journey* は $x=0$ から始まります。
#### ●入力
最初の行には、4つの整数 $a, b, f, k(0<f<a\leq 10^6, 1 \leq b \leq 10^9, 1 \leq k \leq 10^4)$ が含まれます。
それぞれ、最初のバスの終点、燃料タンクの容量、ガソリンスタンドがある点の座標、*journey* の回数です。
#### ●出力
バスが $k$ 回の *journey* を行うために燃料を補給する必要がある回数の最小値を求めてください。
もしも $k$ 回の *journey* を行う事ができなければ、`-1` を出力してください。
#### ●入出力例
##### 入力例1
```
6 9 2 4
```
##### 出力例1
```
4
```
すべての *journey* でガソリンを補給する必要があります。
##### 入力例2
```
6 10 2 4
```
##### 出力例2
```
2
```
バスは燃料補給をせずに $10$ 進むことができます。よって、最初の *journey* は補給せずに行えます。
$x=6$ にたどり着いた段階で燃料タンクに含まれるガソリンは $4$ リットルで、2回目の *journey* では $x=2$ にあるガソリンスタンドまで辿り着けます。補給したら、残り $2$ 進むことで 2回目の *journey* を終えます。
3回目の *journey* が始まるときのガソリン残量は $8$ リットルで、$x=2$ まで進んで残量が $6$ リットルのときに補給する必要があります。そして $x=6$ に到着したときの残量は $6$ リットルです。
4回目の *journey* は、ガソリン残量が $6$ リットルなので補給をせずに $x=0$ に辿り着くことができます。
##### 入力例3
```
6 5 4 3
```
##### 出力例3
```
-1
```
バスは $3$ 回の *journey* を行うことができません。
なぜなら、バスが2回目の *journey* で補給して $x=0$ に辿り着いたときの残量は $1$ リットルですが、3回目の *journey* でのガソリンスタンドまでの距離は $4$ なので補給することができません。
:::
---
### ◎D. Make a Permutation!
:::spoiler **クリックで展開**
TL:2s ML:256MB
#### ●問題
Ivanは長さ $n$ の数列 $a$ を持っています。 $a$ の各要素は1以上 $n$ 以下の整数です。
Ivanは、$a$ を以下の操作を繰り返して順列にしようと思っています。
* 2つの整数 $i,x\ (1 \le i,x \le n)$ を選び、$a_i$ を $x$ に変更する。
順列にするために必要な最小の操作回数を $q$ とます。 $q$ を求めてください。さらに、$q$ 回操作後に $a$ が順列になった時、$a$ として考えられる辞書順最小のものを求めてください。
※ この問題で順列とは、$1$ 以上 $n$ 以下の整数がすべて含まれる長さ $n$ の数列のことを指します。
※ ある条件を満たす長さ $n$ の数列の中で数列 $x$ が辞書順最小であるとは、同じ条件を満たす全ての長さ $n$ の数列$y (\neq x)$について、$x_i \neq y_i$ となる最小の $i$ において $x_i < y_i$ となることを指します。
#### ●入力
1行目に数列の長さ $n$ が与えられます。
2行目に、$a_1,a_2,\ ...\ ,a_n\ (1 \le a_i \le n)$ が与えられます。$a_i$ は数列 $a$ の $i$ 要素目を表します。
#### ●出力
1行目に、順列にするために必要な最小の操作回数 $q$ を出力してください。
2行目には、$q$ 回の操作後に $a$ が順列となった時、考えられる内で辞書順最小のものを出力してください。
#### ●入出力例
##### 入力例1
```
4
3 2 2 3
```
##### 出力例1
```
2
1 2 4 3
```
$a_1$ を1に、$a_3$ を 4にすることにより、2回の操作で順列にすることができます。さらに、操作後の順列は辞書順最小になっています。
##### 入力例2
```
6
4 5 6 3 2 1
```
##### 出力例2
```
0
4 5 6 3 2 1
```
最初から順列なので、操作する必要はありません。
##### 入力例3
```
10
6 8 4 6 7 1 6 3 4 5
```
##### 出力例3
```
3
2 8 4 6 7 1 9 3 10 5
```
:::
---
### ◎E. Fire
:::spoiler **クリックで展開**
TL:2s ML:256MB
#### ●問題
Polycarp の家が燃えています！Polycarp は今のうちに価値があるアイテムを回収したいです。
Polycarp は、$i$ 番目のアイテムを回収するのに $t_i$ 秒かかると見積もっています。また、$d_i$ 秒後には燃え尽きてしまい、彼にとって価値がなくなる見積もりです。特に、$t_i \geq d_i$ であれば、$i$ 番目のアイテムを回収することはできません。
各アイテムの価値 $p_i$ が与えられたとき、Polycarp が回収できるアイテムの集合であって、価値の総和を最大化できるものを求めてください。
Polycarp はひとつずつアイテムを回収できます。例えば、アイテム $a$ を回収した後に $b$ を回収すると、アイテム $a$ は $t_a$ 秒後に回収でき、アイテム $b$ は火事が起きてから $t_a + t_b$ 秒後に回収できます。
#### ●入力
最初の行には、整数 $n ( 1\leq n \leq 100)$ としてPolycarp の家にあるアイテムの数が与えられます。
続く $n$ 行には、それぞれ 3 つの整数 $t_i, d_i, p_i(1 \leq t_i \leq 20, 1 \leq d_i \leq 2000, 1\leq p_i \leq 20)$ が与えられます。それぞれ、アイテム $i$ を回収するのにかかる時間、アイテム $i$ が燃え尽きるまでの時間、アイテム $i$ の価値です。
#### ●出力
最初の行に、回収したアイテムの価値の総和としてあり得るものの最大値を出力してください。
2行目には、整数 $m$ として回収したアイテムの数を出力してください。
3行目には、$m$ 個の回収したアイテムの番号を Polycarp が回収した順番に出力してください。
アイテムの番号は、入力で与えられた順番に 1-indexed で考えます。複数の答えがある場合は、どれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
3
3 7 4
2 6 5
3 7 6
```
##### 出力例1
```
11
2
2 3
```
Polycarpは、任意の2つのアイテムを回収することができます。しかし、価値の総和を最大化するためには、2つ目と3つ目のアイテムを回収することになります。
最初に、$3$秒後に3つ目のアイテムを回収し、更に$2$ 秒後に2つ目のアイテムを回収できます。すると、2つ目のアイテムは火事から5秒後に回収できるので、まだ燃え尽きていません。価値の和は $5 + 6 = 11$ になります。
##### 入力例2
```
2
5 6 1
3 3 5
```
##### 出力例2
```
1
1
1
```
Polycarpは、1番目のアイテムだけ回収できます。もしも2番目のアイテムを回収しようとすると3秒かかりますが、3秒後には燃え尽きてしまいます。
:::
---
### ◎F. Cities Excursions
:::spoiler **クリックで展開**
~~TL:2s ML:256MB~~
TL:4s ML:512MB (TL・MLが厳しいため、増やしました)
#### ●問題
Berlandには、$n$ 個の街が存在します。さらに、$m$ 本の一歩通行の道があり、それぞれの道は2つの異なる街を繋いでいます。全ての異なる街のペア $(x,y)$ について、街$x$ から 街$y$ へ向かう道は高々1本しか存在し無いことが保証されます。
街 $s$ から街 $t$ までのパスは以下のように定義されます。
* ある整数 $k$ と、街の列 $p_1,p_2,\ ...\ , p_k$ が存在し、$p_1 = s$ かつ $p_k = t$ かつ、全ての $i(1 \le i <k)$ について $p_i$ から $p_{i+1}$ に向かう道が存在する。$t$ 以外の街は、複数回 $p$ に登場しても構わないが、 $t$ はちょうど1回だけ登場する。
また、街 $s$ から $t$ へ向かうパスのうち、辞書順最小のものを「理想的なパス」と呼びます。
ここで、あるパス $p$ が辞書順最小であるとは、$r_i \neq q_i$ を満たす最小の整数 $i\ (i \le \mathrm{min}(|p|,|r|))$ について、$r_i < p_i$ が成立するようなパス $r$ が存在しないことを指します。
$q$ 個の旅行プランを提供する代理店があります。 $j$ 個目のプランは、 街 $s_j$ から、街 $t_j$ へ「理想的なパス」で向かうプランです。
それぞれのプランについて、 $k_j$ 番目に訪れる街を出力してください。なお、1番目に訪れる街は $s_j$ であるとみなします。
$k_j$ 番目の街が存在しない、もしくは以下の理由で「理想的なパス」自体が存在しないことがあります。このような場合は`-1`を出力してください。
* $s_j$ から $t_j$ へ向かうパス自体が存在しない。
* 任意の $s_j$ から $t_j$ へ向かうパスについて、それよりも辞書順で小さいパスが存在する。
答として考えられる街が複数ある場合、どれを出力しても構いません。
#### ●入力
1行目に、3つの整数 $n,m,q\ (2\le n \le 3000 , 0 \le m \le 3000 , 1 \le q \le 4 \times 10^5)$ が与えられます。$n$ は街の数、 $m$ は道の数、$q$ は旅行プランの数です。
続く $m$ 行に、二つの整数 $x_i,y_i\ (1 \le x_i,y_i \le n,x \neq y)$ が与えられます。これは、街 $x_i$ から街 $y_i$ へ向かう道が存在することを表します。$i \neq j$ ならば、 $x_i \neq x_j$ もしくは $y_i \neq y_j$ であることが保証されます。
続く $q$ 行に、三つの整数 $s_j,t_j,k_j\ (1 \le s_j,t_j \le n,s_j \neq t_j , 1 \le k_i \le 3000)$ が与えられます。
$s_j,t_j$ は $j$ 番目の旅行プランの最初の街最後の街を、 $k_j$ はこのプランについて答えるべきクエリを表しています。
#### ●出力
$j$ 行目には、 $s_j$ から $t_j$ へ向かう旅行プランの $k_i$ 番目に訪れる街の番号を出力してください。
そもそも「理想的なパス」が存在せずプランを構成できなかったり、プランに $k_i$ 番目に訪れる街が存在しない場合は `-1` を出力してください。
#### ●入出力例
##### 入力例1
```
7 7 5
1 2
2 3
1 3
3 4
4 5
5 3
4 6
1 4 2
2 6 1
1 7 3
1 3 2
1 3 5
```
##### 出力例1
```
2
-1
-1
2
-1
```
:::
---
## ◎ヒント・解説
### ◎ヒント・解説に関しての諸注意
:::spoiler **クリックで展開**
各問題のポイントをヒント・解説という形で紹介しています。
コンテスト中であっても、詰まってしまったらぜひご確認ください。
コンテスト後に復習する際に活用していただいてもいいです。
序盤の問題に関しては一部実装をpython,C++で紹介しています.
pythonに関して, Codeforcesでは以下の5つの実行環境を利用できます.
・python 2.7.18
・python 3.8.10
・PyPy 2.7.13 (7.3.0)
・PyPy 3.6.9 (7.3.0)
・PyPy 3.7.10 (7.3.5, 64bit)
ヒントは、PyPy3.6.9 (7.3.0) もしくは PyPy 3.7.10 (7.3.5, 64bit) を利用することを前提に書いています. なお, Codeforcesのpython環境では, ASCIIに含まれない文字を含んだコードを提出するとエラーになることがありますので注意してください.
C++に関しては、以下のヘッダが記述されていることを前提にしています. ご注意ください.
```cpp=
#include <bits/stdc++.h>
using namespace std;
```
:::
---
### ◎A. Fair Game
:::spoiler **◎ヒント1**
カードの数字が2種類でない場合、答えは `NO` です。
:::
:::spoiler **◎ヒント2**
ある数字のカードはちょうど $n/2$ 枚入っている必要があります。
:::
:::spoiler **◎ヒント3**
配列を用意し、各カードが何枚あるかカウントしましょう。
:::
:::spoiler **◎ヒント4**
0枚、もしくは $n/2$ 枚**ではない** カードがあれば `NO`であり、逆になければ`YES`です。
:::
:::spoiler **◎解説**
以下のような処理を書けばよいです。
1. 長さが十分な配列 $b$ を用意する。要素の初期値は0。
2. 各 $i (1 \le a \le n)$ について、 $b[a_i]$ に1加える。
3. 変数 $flag$ を Trueで初期化
4. 空の配列 $nonzero$ を用意。
5. $b$ を前から見ていき、$0,n/2$ 以外があった場合 $flag$ をFalseにする。さらに、$b_i \neq 0$ の場合はnonzeroに $i$ を加える。
6. $flag$ が Trueならば `YES` と $nonzero$ の中の2つの要素を、そうでなければ `NO` を出力する。
なお、連想配列を使っても同様に書くことができます。
:::
:::spoiler **◎実装例(python3)**
```python=
n = int(input())
a = [int(input()) for i in range(n)]
b = [0] * 101
for i in range(n):
b[a[i]] += 1
nonzero = []
flag = True
for i in range(101):
if b[i] != n//2 and b[i] != 0:
flag = False
if b[i] != 0:
nonzero.append(i)
if flag:
print ("YES")
print (nonzero[0], nonzero[1])
else:
print ("NO")
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i=0; i < n ; ++i){
cin >> a[i];
}
vector<int> b(101,0);
for (int i=0; i < n ; ++i){
b[a[i]] += 1;
}
vector<int> nonzero(0);
bool flag = true;
for (int i=0; i < 101 ; ++i){
if (b[i] != n/2 && b[i] != 0){
flag = false;
}
if (b[i] != 0){
nonzero.push_back(i);
}
}
if (flag){
cout << "YES" << '\n';
cout << nonzero[0] << " " << nonzero[1] << '\n';
}else{
cout << "NO" << '\n';
}
}
```
:::
---
### ◎B. Polycarp and Letters
:::spoiler **◎大文字と小文字の判定**
大文字か小文字かの判定は次のようにしてPython、C++で行うことができます
#### **◎実装例(Python)**
```python=
s = "Aa"
s[0].isupper() # True
s[0].islower() # False
s[1].isupper() # False
s[1].islower() # True
```
#### **◎実装例(C++)**
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
string s = "Aa";
isupper(s[0]); // 0以外の値 (true等ではないことに注意)
islower(s[0]); // 0
isupper(s[1]); // 0
islower(s[1]); // 0以外の値
}
```
:::
:::spoiler **◎ヒント1**
言い換えると、大文字を含まない部分文字列に含まれる小文字の種類数になります。
:::
:::spoiler **◎ヒント2**
大文字で文字列を分割して考えましょう。
:::
:::spoiler **◎ヒント3**
小文字の種類数を求めたいので、set が使えます。
:::
:::spoiler **◎解説**
文字列を左から右に見ていき、小文字だったら set に追加、大文字であれば set を空にするという処理で解くことができます。
set は、C++とPythonのいずれでも利用でき、次のように実装できます。
:::
:::spoiler **◎実装例(Python)**
```python=
n = int(input())
s = input()
kind = set()
ans = 0
for c in s:
if c.islower():
kind.add(c)
ans = max(ans, len(kind))
else:
kind = set()
print(ans)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n;
cin >> s;
set<char> kind;
int ans = 0;
for (int i = 0; i < n; i++) {
if (islower(s[i]) != 0) { // if (islower(s[i])) でも一応大丈夫
kind.insert(s[i]);
ans = max(ans, (int)kind.size());
} else {
kind = set<char>();
}
}
cout << ans << endl;
}
```
:::
---
### ◎C. Bus
:::spoiler **◎ヒント1**
次のガソリンスタンドもしくは $k$ 回の *journey* の終了地点までの距離を計算しましょう。
:::
:::spoiler **◎ヒント2**
現在のガソリン残量を持ちながらシミュレーションしましょう。
:::
:::spoiler **◎ヒント3**
あらかじめ、$k$ 回の *journey* で移動するガソリンスタンド間の距離などをリストにまとめておくと、実装が少し楽になるかもしれません。
:::
:::spoiler **◎解説**
$k$ 回の *journey* での移動で注目するべき移動として、
1. $x=0$ から $x=f$ までの移動が1回
2. $x=f$ → $x=a$ → $x=f$ を $\lfloor \frac{k}{2} \rfloor$回
3. $x=f$ → $x=0$ → $x=f$ を $\lfloor \frac{k-1}{2} \rfloor$ 回
4. $k$ の偶奇によって $x=f$ から $x=0$ か $x=f$ から $x=a$ が1回
とまとめることができます。ただし、2. と 3. は交互に行われます。
ここで、それぞれの移動の距離をリストにまとめ、先頭から見ていくことにします。
最初のガソリンの残量を $0$ にして、1. を始める前にも補給できると考えることで実装が楽になります。
もしも、現在のガソリン残量で次の移動が行えない場合は移動前に補給するというシミュレーションでこの問題を解くことができます。
移動をあらかじめまとめておくときの、Pythonでの実装例のみ示します。
:::
:::spoiler **◎実装例(Python)**
```python=
a, b, f, k = map(int, input().split())
dist = [f]
for i in range(k // 2):
dist.append(2 * (a - f))
if (k % 2 == 1) or (i < k // 2 - 1):
dist.append(2 * f)
if k % 2 == 1:
dist.append(a - f)
else:
dist.append(f)
ans = -1 # スタート地点で補給して0からスタートするようにする
now = 0
for d in dist:
if d > now:
now = b
ans += 1
now -= d
if now < 0:
print(-1)
exit()
print(ans)
```
:::
---
### ◎D. Make a Permutation!
:::spoiler **◎ヒント1**
まず、最小の操作回数を考えましょう。
:::
:::spoiler **◎ヒント2**
$a$ の前から順にどのように操作するかを決めていきましょう。
:::
:::spoiler **◎ヒント3**
どの整数がいくつ $a$ の中にあるかを管理しましょう。
:::
:::spoiler **◎解説**
まず、最小回数は「$1$ 以上 $n$ 以下の整数のうち、 $a$ の初期状態に含まれていない整数の個数」と等しいです。
初期状態の $a$ の中に複数個含まれる各整数について、適当に1箇所を選びます。それ以外の出現位置に対して、$a$ 内に存在しない整数に置き換える操作を行うことで個の最小回数を達成できます。
例:
a = [1,2,1,2,1,3] の時、$a$ 内に存在しない整数は 4,5,6 です。
また、1,2は数列内に複数回出現します。そこで[1,2,**1**,**2**,1,3] の位置を選んだとします。ここで選ばれなかった3か所ある1,2の出現位置を4,5,6にそれぞれ置き換えます。置き換えると [5,4,**1**,**2**,6,3] となり、順列になりました。
では、辞書順最小にするにはどうしたらよいでしょうか？
初期の $a$ に存在しない整数に関しては、好きな位置に入れられるので、より小さいものを左に置けばよいです。
後は、複数回出現する整数に関して、どの位置を残すかが重要となってきます。
結論としては、以下のようなアルゴリズムで辞書順最小の数列を構築できます。
1. $cnt$ という長さ $n$ の配列を用意します。$cnt_i$ には、 $a$ の中での $i$ の出現回数を記録しておきます。以後、$a$ に対して操作を行った際は、配列 $cnt$ の値も整合性が取れるように操作しておくものとします。
2. $need$ というdequeを用意します。これには、初期の $a$ に含まれない整数を小さい順に入れておきます。
3. 前から数列 $a$ を見ていきます。現在の $need$ の最小の要素を $m$ とします。 $cnt_{a_i} > 1$ かつ、$a_i > m$ もしくは $a_j = a_i (j < i)$ となる $j$ があるならば、$a_i$ を $m$ に置き換える操作を行い、 $need$ から $m$ を取り除きます。$cnt$ の更新も忘れずにします。
以上のように配列 $cnt$ を用意して個数を管理することにより、ある数字の全ての要素を消してしまうことなく、なるべく辞書順で小さくすることができます。
:::
---
### ◎E. Fire
:::spoiler **◎ヒント1**
動的計画法(DP)で解くことができます。
:::
:::spoiler **◎ヒント2**
先に燃え尽きてしまうアイテムを先に回収するべきなので、アイテムは $d_i$ でソートしておきます。
:::
:::spoiler **◎ヒント3**
次のようなDP配列を考えてみましょう。
$$
dp[i][j] := i番目のアイテムまで見て、回収するのにかかった時間の和がjのときの価値の総和の最大値
$$
:::
:::spoiler **◎解説**
ヒント1からヒント3を前提にして解説します。
残りの考える必要が有ることは、DPの遷移と復元の方法です。
遷移は次のようになります。それぞれ、$i$ 番目のアイテムを回収するかどうかです。
- $dp[i + 1][j] = \max(dp[i+1][j], dp[i][j])$
- $dp[i + 1][j + t[i]] = \max(dp[i+1][j + t[i]], dp[i][j] + p[i])$
- ただし $j + t[i] < d[i]$
最後にどのアイテムを回収したかを復元する必要があります。
最終的に最大値を達成するときにかかった時間の総和が $T$ のとき、最後に回収したアイテムは次を満たす最大の $i$ です。
$$
dp[i][T - t[i]] + p[i] = dp[i + 1][T]
$$
`T` を `T - t[i]` に更新して、$i=n$ から $i= 0$ へのループを続ければ残りの回収したアイテムもわかります。
最初にソートを行ったので、方法によってはソート後の $i$ 番目のアイテムが元の何番目のアイテムかわかるようにしておく必要があります。
:::
---
### ◎F. Cities Excursions
:::spoiler **◎ヒント0**
以下のようなグラフを考えると分かりやすいかもしれません。
:::
:::spoiler **◎ヒント1**
「理想的なパス」に同じ頂点が2回以上含まれることはあり得ません。
同じ頂点が2回含まれる場合、サイクルが存在することになり、そのサイクルを回り続けることで、より辞書順で小さいパスを作成できるからです。
:::
:::spoiler **◎ヒント2**
ダブリングが想定解ですが…？
:::
:::spoiler **◎ヒント3**
ダブリングだと $O(n^2 \mathrm{log}n + q\mathrm{log}n)$ になります。
この解法ですが、相当定数倍が厳しいです。もう少し効率的な解が存在します。
:::
:::spoiler **◎ヒント4**
効率的な解法の方は、スタックを用いたDFS(深さ優先探索)を活用します。
:::
:::spoiler **◎解説**
ダブリング解の方は、以下の公式解説をご覧ください。
https://codeforces.com/blog/entry/54765
C++でもギリギリ、python系ではダブリングで通すのは不可能だと思われます。
ここでは、高速なDFS解について解説します。
まず、クエリを先読みしておきます。
各頂点 $s$ について、$s$ を始点としてDFSを行います。
DFSをする際、頂点番号が小さい方から先に探索します。
探索中のDFSスタックに注目すると、$s$ 始点の「理想的なパス」が全て一度はスタックの状態として現れていることが分かります。これを利用して問題を解きます。
さて、この問題が難しくなっている原因は、サイクルの存在により、「理想的なパス」が存在しない可能性がある点です。
従って、DFS中にサイクルを生成してしまった場合の処理が重要となります。
DFS中に $u \rightarrow v$ の辺を探索したとします。この時、スタックの頂点 $v$ が入っていた場合、これはサイクルになってしまいます。これ以降、$v$ がスタックから取り除かれるまでは、スタックに「理想的なパス」が入った状態になることはあり得ません。なぜなら、サイクルを回り続けることでより辞書順で小さいパスを生成できるからです。
結論として、以下のようなアルゴリズムで解くことができます。
* 全ての $s$ について、以下の操作を行う。
* $s$ 始点でスタックを用いたDFSを行う。
* DFSで、スタックの一番上に積んである頂点を $u$ とする。このとき、まだ $u \rightarrow v$ のエッジを探索していない且つ、頂点番号が最小の $v$ を見る(このような$v$がない場合、$u$をスタックから取り除く)。$v$ がスタックに現在含まれている場合、頂点 $v$ にチェックを入れておく。そうでない場合で、 $v$ が未だスタックに積まれたことがない場合のみ、$v$ をスタックに積む。
* スタックに新たな頂点 $v$ が積まれたとき、 $s_j = s, t_j = v$ のクエリを処理する。具体的には、スタックの $k_j$ 番目の値を $j$ 番目のクエリの答えにすればよい。ただし、スタックに$k_j$ 番目がない場合・**チェックが入った頂点が1つでもスタックに積まれている場合**は、答えを `-1` にする。
計算量は $O(n(n+m)+q)$ になります。
ちなみに、制約の厳しさからかpython系での正解提出は1つもなかったようで、私が初のpython系での正解者になりました。
https://codeforces.com/contest/864/submission/158971060
:::
Sign in with Wallet
Connect another wallet