# 競プロ講習会第17回 Web資料
## ◎第17回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #17 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Virtual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/c1343b00a384ad35c0fc21912041236ae6a73c14v
#### ◎公式解説
##### A〜H問題
https://codeforces.com/blog/entry/51846
## ◎問題訳(意訳あり注意,F問題まで)
### ◎A. Fake NP
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Tavak と Seyyed は親友です。 Seyyed はおかしな人で、最長路問題の代わりに次の問題を解くよう Tavak に言いました。
$l$ と $r$ が与えられます。 $l$ から $r$ のすべての整数について、1を除く約数を書き出していきます。もっとも多く書かれた整数を求めてください。
この問題が NP ではないことを示すために解いてください。
#### ●入力
1行目に、2つの整数 $l, r (2 \leq l \leq r \leq 10^9)$ が与えられます。
#### ●出力
一つの整数として、約数としてもっとも多く現れる整数を出力してください。
答えが複数存在する場合、どれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
19 29
```
##### 出力例1
```
2
```
$19$ から $29$ の間の、 $2$ で割り切れる整数は $\{ 20, 22, 24, 26, 28 \}$ です。
##### 入力例2
```
3 6
```
##### 出力例2
```
3
```
$3$ で割り切れる整数は $\{3, 6\}$ です。
:::
### ◎B. 3-palindrome
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Kevianは、各文字が 'a' , 'b' , 'c' のいずれかである、長さ $n$ の文字列を作りました。彼は回文が嫌いなので、この文字列の任意の位置から連続する長さ3の部分文字列を抜き出したとき、回文ではありません。
例えば、"abc" , "abca" などはこの条件を満たし、 "aba" は満たしません。このような文字列のうち、'c' を含む個数が最小の物を1つ求めてください。
#### ●入力
最初の行に、整数 $n (1 \le n \le 2 \times 10^5)$ が与えられます。これは、Kevianが作る文字列の長さです。
#### ●出力
条件を満たす文字列を1つ出力してください。
答が複数ある場合、いずれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
2
```
##### 出力例1
```
aa
```
##### 入力例2
```
3
```
##### 出力例2
```
bba
```
:::
### ◎C. Find Amir
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
数年前、安全上の理由で Sajjad は他の学校に転校しました。今、同じ学校の親友だった Amir を見つけたいと思っています。
$n$ 個の $1$ から $n$ と番号付けられた学校があります。学校間を移動することはできますが、そのためにはチケットを購入する必要があります。学校 $i$ から $j$ に移動するチケットの価格は $(i + j) \bmod (n + 1)$ で、何回でも使用することができます。
Sajjad がすべての学校を訪れるためにチケットを買う方法として、コストが最小になるものを見つけてあげてください。開始時と終了時の学校はどの学校でも構いません。
#### ●入力
最初の行に、整数 $n(1 \leq n \leq 2 \cdot 10^5)$ として、学校の数が与えられます。
#### ●出力
一つの整数として、すべての学校を訪れるために必要なチケットの最小コストを出力してください。
#### ●入出力例
##### 入力例1
```
2
```
##### 出力例1
```
0
```
2つの学校の間のチケットを買うと、コストは $(1 + 2) \bmod (2 + 1) = 0$ になります。
##### 入力例2
```
10
```
##### 出力例2
```
4
```
:::
### ◎D. Minimum number of steps
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
'a' と 'b' からなる文字列があり、この文字列に対して操作をしていきます。1回のステップでは、部分文字列 "ab" を1つ選び、 "bba" に置き換えます。 部分文字列として "ab" を含まなくなったら、操作は終了です。操作を終了するまでのステップ数として考えられる最小値を求め、$10^9+7$ で割った余りを出力してください。
#### ●入力
1行目に、'a','b' のみからなる、長さ $1$ 以上 $10^6$ 以下の文字列が与えられます。
#### ●出力
最少のステップ数を $10^9+7$ で割った余りを出力してください。
#### ●入出力例
##### 入力例1
```
ab
```
##### 出力例1
```
1
```
"ab" → "bba" となります。
##### 入力例2
```
aab
```
##### 出力例2
```
3
```
"aab" → "abba" → "bbaba" → "bbbbaa" となります。
:::
### ◎E. Ice cream coloring
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
Isart と Modsart が面白い問題を解こうとしているときに、Kasra がやってくると同時に「一日中詰まっていたこの問題解ける？」と尋ねてきました。
$n$ 頂点からなる木 $T$ と、 $1$ から $m$ に番号付けられた $m$ 種類のアイスクリームがあります。各頂点 $i$ には $s_i$ 種類のアイスクリームがあります。 $i (1 \leq i \leq m)$ 種類目のアイスクリームを含む頂点からなる部分グラフは連結になっています。
$T$ の頂点に $u, v$ 両種類のアイスクリームを含むものがあるときに限り、2頂点 $u, v (1 \leq u, v, \leq m, u \neq v)$ の間に辺を張るようにして、$m$ 頂点からなる新しいグラフ $G$ を作ります。
このとき、隣接する2頂点が同じ色にならないように $G$ の頂点に色を塗るために必要な色数の最小値を求めてください。
頂点の空集合は連結な部分グラフをなしているとこの問題では考えます。
いつも通り、Modsart は解こうとしていた問題を放置したくはないため、Isart は新しい問題を解くことをあなたにお願いしてきました。
pythonを利用している人は、Pypyを使用し、入出力も高速に行うことをおすすめします。
少し早い入力の受け取り方は A問題のヒント1に載せてあります。
#### ●入力
最初の行に、2つの整数 $n, m (1\leq n, m\leq 3\cdot10^5)$ として $T$ の頂点数とアイスクリームの種類数が与えられます。
続く $n$ 行の $i$ 行目には、一つの整数 $s_i (0 \leq s_i \leq 3 \cdot 10^5)$ と、$s_i$ 個の異なる整数が与えられます。$s_i$ 個の整数はそれぞれ $1$ から $m$ の整数で、$i$ 番目の頂点に含まれるアイスクリームの種類です。$s_i$ の和は $5 \cdot 10^5$ を超えません。
続く $n-1$ 行には、2つの整数 $u, v (1 \leq u, v \leq n)$ として木 $T$ の辺が結ぶ2つの頂点の添字が与えられます。
#### ●出力
一行目には、一つの整数 $c$ を出力してください。 $c$ は $G$ の頂点に色を塗るために必要な色の種類数の最小値です。
二行目には $m$ 個の整数を出力してください。 $i$ 番目の整数は $i$ 番目の頂点の色で、色は $1$ から $c$ の間の整数である必要があります。
答が複数通りある場合、どれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
3 3
1 1
2 2 3
1 2
1 2
2 3
```
##### 出力例1
```
2
1 1 2
```
1つ目の種類のアイスクリームは、最初の頂点にしか現れていないので好きな色で塗ることができます。
2つ目と3つ目のアイスクリームは2つ目の頂点に同時に現れているため、違う色で塗る必要があります。
##### 入力例2
```
4 5
0
1 1
1 3
3 2 4 5
2 1
3 2
4 3
```
##### 出力例2
```
3
1 1 1 2 3
```
2,4,5番目のアイスクリームを違う色で塗る必要があります。
:::
### ◎F. Expected diameter of a tree
:::spoiler **クリックで展開**
TL: 3s ML: 256MB
#### ●問題
$n$ 頂点、$m$ 辺の森(サイクルの無い無向グラフ)があります。辺は全て長さ1です。
このグラフに対する $q$ 個のクエリに、あなたは答えなくてはいけません。各クエリは、2つの頂点 $v,u$ からなります。$V$ を $v$ を含む連結成分の頂点の集合、$U$ を $u$ を含む連結成分の頂点の集合としたとき、以下の指示に従って、値を出力します。
- $V=U$ の時、 -1 を出力。
- そうでないとき、$a \in V,b \in U$ となる $a,b$ を無作為に選び、$a,b$ 間に辺を引いたと仮定した時、$v$ を含む連結成分(木となります)の直径 $d$ の期待値を出力。
なお、木の直径とは、木の中の2頂点間距離のうち、最大の物を指します。
与えられるグラフは森であることに注意してください。各クエリは独立であり、前のクエリによって後ろのクエリが影響を受けることはありません。
#### ●入力
最初の行に、3つの整数 $n,m,q (1 \le n,m,q \le 10^5)$ が与えられる。$n$ は頂点の数、 $m$ は辺の数、 $q$ はクエリの数である。
続く $m$ 行に、二つの整数 $u_i,v_i (1 \le u_i,v_i \le n)$ が与えられます。これは、$u_i,v_i$ 間に辺が存在することを示しています。与えられるグラフ全体は、森であることが保証されます。
続く $q$ 行に、二つの整数 $u_i,v_i (1 \le u_i,v_i \le n)$ が与えられます。これは、$i$ 番目のクエリを表しています。
#### ●出力
$q$ 行出力してください。 $i$ 行目には、$i$ 番目のクエリの答えを出力してください。
解答は、ジャッジの答との絶対差、または相対差が $10^{-6}$ を超えないとき、正解となります。より具体的には、あなたの答えが $a$ , ジャッジの答えが $b$ の時、 $\frac{|a-b|}{\mathrm{max}(1,b)} \le 10^{-6}$ ならば正解となります。
#### ●入出力例
##### 入力例1
```
3 1 2
1 3
3 1
2 3
```
##### 出力例1
```
-1
2.0000000000
```
頂点1,3が同じ連結成分です。そのため、最初のクエリの答えは-1となります。
2つ目のクエリは、辺を引く際に、1-2間に引く場合、2-3間に引く場合の2通りが考えられます。どちらの場合も、辺を引いた後の直径は2のため、答えは2です。
##### 入力例2
```
5 2 3
2 4
4 3
4 2
4 1
2 5
```
##### 出力例2
```
-1
2.6666666667
2.6666666667
```
最初のクエリの答えは、明らかに-1です。
2つ目のクエリは、1-2,1-3間に引いた場合は直径3、1-4間に引いた場合は直径2なので、$\frac{3+3+2}{3} \approx 2.666666666$ です。
:::
## ◎ヒント・解説
### ◎A. Fake NP
:::spoiler **◎ヒント1(高速な入力の受け取り方)**
python では `input()` よりも高速に入力を受け取る方法があります。この問題では必要ないですが、場合によっては必要になることがあります。
```python=
# python
from sys import stdin
l, r = map(int, stdin.readline().split())
```
C++ では main 関数の最初の2行を加えると入出力が早くなります。
`getline` を併用したり、インタラクティブ問題ではうまく動かないことがあるので気をつけてください。
```cpp=
// c++
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int l, r;
cin >> l >> r;
}
```
:::
:::spoiler **◎ヒント2**
$l$ から $r$ までのすべての約数を調べていると間に合いません。
:::
:::spoiler **◎ヒント3**
ある整数 $d$ が $l$ から $r$ の約数に現れる回数はだいたい $\frac{r - l + 1}{d}$ ぐらいになります。
:::
:::spoiler **◎ヒント4**
$l = r$ のケースに注意しましょう。
:::
:::spoiler **◎解説**
ほとんどのケースで $2$ が最も多く約数として現れます。
$l = r$ で $l$ が $2$ で割り切れない時のみ、$l$ の約数を出力すればよいです。
$l$ 自身が $l$ の約数なので $l$ を出力するのが簡単です。
:::
:::spoiler **◎実装例(Python)**
```python=
from sys import stdin
l, r = map(int, stdin.readline().split())
if l == r:
print(l)
else:
print(2)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int l, r;
cin >> l >> r;
if (l == r) {
cout << l << endl;
} else {
cout << 2 << endl;
}
}
```
:::
### ◎B. 3-palindrome
:::spoiler **◎ヒント1**
$n = 4,n = 5$ の場合を考えてみましょう。
:::
:::spoiler **◎ヒント2**
え…？と思うかもしれませんが、かなりギャグ問題ですので、自信を持って実装しましょう。
:::
:::spoiler **◎解説**
`aabbaabbaabbaa...` といったように、`aabb` を繰り返すことで答えになります。
実装の際は、$i$ 文字目 $(0 \le i < n)$ について、$i$ を 4で割った余りが 0,1 ならば'a'、そうでなければ'b' を配置していけばよいです。
:::
:::spoiler **◎実装例(python3)**
```python=
n = int(input())
ans = ["a" if i%4 <= 1 else "b" for i in range(n)]
print ("".join(ans))
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string ans = "";
for (int i = 0 ; i < n ; ++i){
if (i % 4 <= 1) ans += "a";
else ans += "b";
}
cout << ans << '\n';
}
```
:::
### ◎C. Find Amir
:::spoiler **◎ヒント1**
コストが小さいチケットから使っていきたいです。
特に、コストが 0 のものを全部使うとどうなるでしょうか。
:::
:::spoiler **◎ヒント2**
問題は、最小全域木を求める問題になります。
ただし、実際に最小全域木のアルゴリズムを動かす必要はありません。
:::
:::spoiler **◎解説**
最小全域木のアルゴリズムを考えると、小さい辺から繋いでいくことになります。
コスト 0 の辺は $x$ と $n + 1 - x$ を結ぶもので、これをすべて用いると $\left\lceil \frac{n}{2} \right\rceil$ 個の連結成分になります。
連結成分に小さい方の番号で番号付けすると、例えばコスト 1 の辺で 1番と 2番の連結成分が $n + 1 - 1$ と $2$ を結ぶことで連結になります。
残りのコスト 1 の辺を使っていくと、$(2, 3), (3, 4), \ldots, (\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{n}{2} \right\rceil - 1)$ というペアの連結成分を結ぶことができます。
$n = 8$ の例が次の画像で、青がコスト０、オレンジがコスト1です。
これらで全域木になっていることがわかるので、コスト1の辺を使う個数が答えになります。
全域木の辺の数は $n - 1$ で、コスト0の辺の数が $\left\lfloor \frac{n}{2} \right\rfloor$ なので、答えは $n - 1 - \left\lfloor \frac{n}{2} \right\rfloor$ になります。
これは $\left\lfloor \frac{n - 1}{2} \right\rfloor$ に等しくもあります。
:::
:::spoiler **◎実装例(Python)**
```python=
n = int(input())
print((n - 1) // 2)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
cout << (n - 1) / 2 << endl;
}
```
:::
### ◎D. Minimum number of steps
:::spoiler **◎ヒント1**
最終状態は、`bbb...bbbaaa...aaa` のようになります。
:::
:::spoiler **◎ヒント2**
最終状態は、一意に定まります。
:::
:::spoiler **◎ヒント3**
最終状態までのステップ数も、実は一意に定まります。
:::
:::spoiler **◎ヒント4**
各 'b' の文字は、その前にある 'a' の個数によって、最終状態でいくつに増えるかが決定されます。
:::
:::spoiler **◎解説**
最終状態は、`bbb...bbbaaa...aaa` のようになります。
'a' の個数は、操作によって変化しません。
一方で、'b'は左にあった'a'が右に移動する度に2倍に増えます。
'aaab'があったら、'a'を1つ右に移動すると 'aabba', もう一つ移動すると 'abbbbaa', もう一つ移動すると 'bbbbbbbbaaa' となります。
結論として、初期状態の文字列に含まれる 'b' は、それより左側に 'a' が $k$ 個ある時、最終状態では $2^k$ 文字に増えます。これを利用し、文字列を左端から走査していくことで、最終状態の文字数が分かります。
また、1回の操作で1文字分だけ文字列は長くなるので、(最終状態の文字数)-(最初の文字数)が操作回数となります。
詳しくは実装例をご覧ください。
:::
:::spoiler **◎実装例(python3)**
```python=
mod = 10**9+7
s = input()
final_len = 0
acnt = 0
for c in s:
if c == "a":
acnt += 1
final_len += 1
else:
final_len += pow(2,acnt,mod)
final_len %= mod
print ((final_len-len(s)) % mod)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
int main() {
string s;
cin >> s;
ll final_len = 0;
ll pow_two_acnt = 1;
for (char c : s){
if (c == 'a'){
pow_two_acnt *= 2;
pow_two_acnt %= mod;
final_len += 1;
final_len %= mod;
}else{
final_len += pow_two_acnt;
final_len %= mod;
}
}
ll ans = ( final_len - s.size() ) % mod;
cout << ans << endl;
}
```
:::
### ◎E. Ice cream coloring
:::spoiler **◎ヒント1**
$T$ 上で、ある種類のアイスクリームが含まれる頂点は連結な部分グラフを成すことに注意してください。
:::
:::spoiler **◎ヒント2**
少なくとも、ある頂点が含むアイスクリームの種類数の最大値の分だけ色の種類数は必要です。
:::
:::spoiler **◎ヒント3**
ヒント2の色数で塗り分けることができます。
:::
:::spoiler **◎ヒント4**
どの頂点にも含まれていないアイスクリームがあるかもしれません。
:::
:::spoiler **◎解説**
$T$上でDFSを行いながら、貪欲に塗っていくことができます。
貪欲に塗る方法は、今見ている頂点に含まれるアイスクリームで既に色が決まっているもの以外を決まっているものと被らないように適当に塗るだけです。
これでうまくいく理由は問題文に書かれているヒント1の性質が関係しています。
ヒント1の性質がないと次のようなグラフがあり、上の頂点に含まれるアイスクリームを塗った後に左の子に行って4番と5番のアイスを青と緑で塗ることができます。
その後、右の子に行くと既に塗っている3番と5番が同じ色になっていて、彩色の条件を満たすことができません。
しかし、ヒント1の性質があるとき、子の両方が5番を含むなら親にも5番のアイスクリームが含まれており、3番と5番は違う色で塗られているはずなので条件を満たすことができます。
左の子にのみ含まれていて、親にも含まれていない場合はその頂点の子孫に3番が再び登場しない限りは問題なく、性質から左の子に3番が含まれていない以上子孫に現れることがないので大丈夫です。
色を貪欲に塗る際、今の頂点に含まれるアイスクリームで使われていない色を調べるのをうまくやらないと間に合いません。少し工夫すると線形でできますが、実装の簡単さからC++のみの実装例では set を用いて $\log$ をつけています。
python では線形で実装しないと間に合わないかもしれません。
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<int>> ice(n);
vector<vector<int>> G(n);
int max_size = 1;
for (int i = 0; i < n; i++) {
int s;
cin >> s;
max_size = max(max_size, s);
ice[i].resize(s);
for(int j = 0; j < s; j++) {
cin >> ice[i][j];
ice[i][j]--;
}
}
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v; u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> res(m, -1);
set<int> rest;
for (int i = 0; i < max_size; i++) rest.insert(i + 1);
auto dfs = [&](auto &&dfs, int u, int p = -1) -> void {
for (auto &c : ice[u]) {
if (res[c] != -1) rest.erase(res[c]);
}
for (auto &c : ice[u]) {
if (res[c] == -1) {
res[c] = *rest.begin();
rest.erase(rest.begin());
}
}
for (auto &c : ice[u]) {
rest.insert(res[c]);
}
for (auto &v : G[u]) {
if (v == p) continue;
dfs(dfs, v, u);
}
};
dfs(dfs, 0);
cout << max_size << endl;
for (int i = 0; i < m; i++) {
cout << (res[i] == -1 ? 1 : res[i]) << " ";
}
cout << endl;
}
```
:::
### ◎F. Expected diameter of a tree
:::spoiler **◎ヒント1**
同じ連結成分のペアについて、2回以上聞かれた際は、以前の結果を流用することで高速化できます。
:::
:::spoiler **◎ヒント2**
サイズ $x,y$ の連結成分のペアについて、 $\mathrm{O}(x\ \mathrm{log}y)$ で解く方法が存在します。
:::
:::spoiler **◎解説**
まず、サイズ $x,y(x \le y)$ の連結成分のペアについて、 $\mathrm{O}(x\ \mathrm{log}y)$ で解く方法について述べます。
連結成分 $U,V$ の頂点数がそれぞれ $x,y$ で、直径がそれぞれ $d_U,d_V$ であるとします。
$u \in U,v \in V$ であるような頂点 $u,v$ について、$f_u,f_v$ を連結成分内における最遠点までの距離と定義します。
この時、$U,V$ からそれぞれ無作為に頂点を1つずつ選び、繋いだ時の直径の期待値は以下の式のようになる。
$\frac{\displaystyle \sum_{u \in U} \displaystyle \sum_{v \in V} \mathrm{max}(f_u+f_v+1,d_U,d_V) }{xy}$
この式の分母の計算において、$u$ を決め打った際を考える。$f_v$ を降順にあらかじめソートしておき、別で累積和を取っておく。すると、$f_u+f_v+1 > \mathrm{max} (d_U,d_V)$ となるような $v$ の個数と、$f_v$ の総和が二分探索により$O(log y)$ で計算できる。よって、$u$ を全探索することで、期待値を $O(x\mathrm{log}y)$ で計算できる。
$x < √n$ であるようなクエリは、当然 $q$ 個未満しか飛んでこないため、 このようなクエリに関して、全体の計算量は$O(q √n \mathrm{log} n)$ である。
一方、$x \ge √n$ であるようなクエリに関しては、一度計算した連結成分のペアについて、前の計算結果を流用することで $O(n√n \mathrm{log} n)$ で解くことができる。これは、$√n$ 以上のサイズを持つ連結成分が最大でも $√n$ 個しか存在しないことから導出できる。
結論として、計算量は $O(q √n \mathrm{log} n + n√n \mathrm{log} n)$ である。
:::
:::spoiler **◎実装例(C++)**
AtCoder Library を利用しています。
https://codeforces.com/contest/805/submission/181531093
:::
Sign in with Wallet
Connect another wallet