# 競プロ講習会第13回 Web資料
## ◎第13回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #13 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Vertual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/cea18ee61642406c3bea4af035022345b1493bb3
#### ◎公式解説
##### A〜F問題
https://codeforces.com/blog/entry/68655
## ◎問題訳(意訳あり注意)
### ◎A. Three Piles of Candies
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
AliceとBobは、キャンディーセットを3つ貰いました。
各セットに含まれているキャンディの個数はそれぞれ $a,b,c$ 個です。
2人は、キャンディーをなるべく均等に分けたいと思っています。まず、Aliceが3つのセットの内1つを選んで貰います。次に、Bobが残り2セットの内1つを選んで貰います。そして、最後に残った1つのセットの中のキャンディを2人で任意の個数ずつ分けます。最後のセット内の全てのキャンディを1人でもらっても構いません。
分け終わった時に2人の持っているキャンディの数が異なる場合、より多くのキャンディを持っている方が、もう一人と同じ数になるようにキャンディを捨てます。
AliceとBobは、なるべく多くのキャンディが欲しいと思っています。2人が適切に行動したとき、Aliceが最終的に獲得するキャンディの数として考えられる最大値を求めてください。
以上の問題が $q$ 個与えられるので、そのすべてに回答してください。
例を見ていきましょう。$a,b,c = 1,3,4$ の場合、まずAliceが3番目のセットを取ります。次に、Bobが2番目のセットを取ります。そして、1番目のセットのキャンディ1つをBobが取ります。二人の持っているキャンディの個数が等しいため、操作は終了です。この時、Aliceはキャンディを4個、Bobも4個持っている状態になります。
$a,b,c=1,10,100$ の場合、まずAliceが2番目のセットとります。次に、Bobが1番目のセットを取ります。3番目のセットから、Aliceが46個、Bobが54個取ります。この時、Aliceは56個、Bobは55個キャンディを持っています。数が違うので、Aliceがキャンディを1つ捨てます。結局、Alice,Bobはそれぞれ55個のキャンディを得ることになります。
#### ●入力
最初の行に、整数 $q (1 \le q \le 1000)$ が与えられます。続く $q$ 行に、問題が1つずつ与えられます。
各行は、$a\ b\ c (1 \le a,b,c \le 10^{16})$ の3つの整数からなります。これは各セットのキャンディの個数を表しています。
#### ●出力
$q$ 行出力してください。$i$ 行目には、$i$ 番目の問題の答えを出力してください。
#### ●入出力例
##### 入力例1
```
4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45
```
##### 出力例1
```
4
55
15000000000000000
51
```
:::
### ◎B. Odd Sum Segments
:::spoiler **クリックで展開**
TL: 3s ML: 256MB
#### ●問題
$n$ 個の整数 $a_1, a_2, \ldots, a_n$ からなる配列 $a$ が与えられます。
あなたはこの配列をちょうど $k$ 個の ***互いに重ならず空ではない区間*** であって、各区間に含まれる要素の和が奇数であるように分割してください。
与えられた配列を並び替えることはできません。
配列 $a$ に含まれる $n$ 個の整数は、それぞれ $k$ 個の区間の内ちょうど一つに含まれる必要があります。
長さ $5$ の列を $3$ つの区間に分割する例を見てみましょう(今は和が奇数であるかは考えていません)。最初の配列を `[1, 2, 3, 4, 5]` としたとき、$3$ つの空でなく重ならない区間に分けるすべての方法は次のようになります。
- `[1], [2], [3, 4, 5]`
- `[1], [2, 3], [4, 5]`
- `[1], [2, 3, 4], [5]`
- `[1, 2], [3], [4, 5]`
- `[1, 2], [3, 4], [5]`
- `[1, 2, 3], [4], [5]`
もちろん、各区間に含まれる要素の和が奇数になるようにちょうど $k$ 個の区間に分けることができない場合もあります。その場合は `"NO"` と出力してください。それ以外の場合は`"YES"` と出力した後に、条件を満たす分割方法のうち任意のものを出力してください。詳しくは 「●出力」を見てください。
あなたは、 $q$ 個の独立な質問に答える必要があります。
#### ●入力
最初の行に、一つの整数 $q (1 \leq q \leq 2 \cdot 10^5)$ として、質問の数が与えられます。その後、 $q$ 個の質問が続きます。
質問の最初の行は、2つの整数 $n, k (1 \leq k \leq n \leq 2 \cdot 10^5)$ として、それぞれ配列の要素の数と区間の数を含みます。
質問の2行目に、$n$ 個の整数 $a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9)$ が与えられます。$a_i$ は $a$ の $i$ 番目の要素です。
すべての質問の $n$ の和は $2 \cdot 10^5$ を超えないことが保証されます。
#### ●出力
各質問に対して答えを出力してください。
与えられた配列をちょうど $k$ 個の区間に条件を満たすように分割できない場合、`"NO"` と出力してください。
可能であれば、最初の行に `"YES"` と出力した後、条件を満たす分割のうち任意のものを2行目に出力してください。
分割は $k$ 個の整数 $r_1, r_2, \ldots, r_k (1 \leq r_1 < r_2 < \cdots < r_k = n)$ と表してください。 $r_j$ は $j$ 番目の区間の右端 ($j$ 個目の区間に含まれる最後の要素の添字) を表します。つまり、配列は $[1; r_1], [r_1 + 1; r_2], [r_2 + 1; r_3], \ldots, [r_{k-1}, n]$ と分割されています。
**$r_k$ は常に $n$ ですが、出力する必要があることに注意してください。**
#### ●入出力例
##### 入力例1
```
3
5 3
7 18 3 14 1
5 4
1 2 3 4 5
6 2
1 2 8 4 10 2
```
##### 出力例1
```
YES
1 3 5
NO
NO
```
:::
### ◎C. Robot Breakout
:::spoiler **クリックで展開**
TL: 3s ML: 256MB
#### ●問題
$n$ 匹のロボが研究所から逃げ出した！ あなたはロボを回収しなくてはいけません。
幸運なことに、あなたは1回だけロボット達に向かって指令を出すことができます。このチャンスを利用し、ロボを1箇所に集めて回収しましょう。
まず、あなたの住む世界は2次元平面とみなすことができます。そして、あなたは各ロボが、2次元平面のどの座標にいるのかを知っています。具体的には、$i$ 番目のロボットは、座標 $(x_i,y_i)$ にいます。なお、$x_i,y_i$ は両者必ず整数です。
あなたの出す指令は、2つの整数 $X,Y$ からなります。これは、ロボの向かう目的地を表します。あなたが指令を出したのち、各ロボは以下の4種類の移動を繰り返して目的地に向かおうとします。目的地に到達したロボットはその場で停止します。
現在ロボが居る座標を $(x_c,y_c)$ とした時…
1. $(x_c-1,y_c)$ に移動する。
2. $(x_c,y_c+1)$ に移動する。
3. $(x_c+1,y_c)$ に移動する。
4. $(x_c,y_c-1)$ に移動する。
不運なことに、ロボットのシステムには欠陥がある場合があります。具体的には、上の4種類の移動のうち、いくつかが実行できない場合があります。どのロボットがどの行動ができて、できないのかはあなたには情報として与えられます。
さて、あなたは適切に指令を出すことでロボットを1か所に集められるでしょうか。判定し、できる場合は指令の内容 $X,Y$ を求めてください。
#### ●入力
1行目に、クエリの個数 $q(1 \le q \le 10^5)$ が与えられます。続いて、$q$ 個のクエリが与えられます。
各クエリの1行目にはロボットの個数を表す整数 $n (1 \le n \le 10^5)$ が与えられます。続く $n$ 行に、各ロボットの情報が与えられます。
$i$ 行目には、 $x_i,y_i,f_{i,1},f_{i,2},f_{i,3},f_{i,4} (-10^5 \le x_i,y_i \le 10^5 , 0 \le f_{i,j} \le 1)$ の6個の整数がこの順番で空白区切りで与えられます。
$x_i,y_i$ は $i$ 番目のロボットが最初に居る座標を表しています。$f_{i,j}$ は、1の時 $i$ 番目のロボットが $j$ 種類目の移動ができるかを表しています。0の時は、できないことを表します。
全てのクエリのロボットの数の総和は $10^5$ 以下であることが保証されます。
#### ●出力
$q$ 行出力してください。
$i$ 番目のクエリについて、以下の形式で $i$ 行目に回答してください。
・どのように指令を出してもロボットを1箇所に集められない場合、`0`を出力してください。
・そうでない場合、条件を満たす指令の内容を$X,Y$として、`1 X Y` を出力してください。なお $X,Y$ は、$|X| \le 10^5 , |Y|\le 10^5$ を満たす整数である必要があります。答が複数通り考えられる場合、どれを出力しても正解となります。
#### ●入出力例
##### 入力例1
```
4
2
-1 -2 0 0 0 0
-1 -2 0 0 0 0
3
1 5 1 1 1 1
2 5 0 1 0 1
3 5 1 0 0 0
2
1337 1337 0 1 1 1
1336 1337 1 1 0 1
1
3 5 1 1 1 1
```
##### 出力例1
```
1 -1 -2
1 2 5
0
1 -100000 -100000
```
:::
### ◎D. RGB Substring
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
**D1 と D2 の違いは入力のサイズのみなのでまとめてあります。「入力」の部分で違いを示しています。**
あなたは $n$ 文字からなる文字列 $s$ を与えられます。各文字は `'R', 'G', 'B'` のいずれかです。
整数 $k$ も与えられます。あなたは、最初の文字列 $s$ に含まれる文字を最小の個数だけ書き換えて、$s$ に含まれる長さ $k$ の部分文字列として、無限長の文字列 `"RGBRGBRGB..."` の部分文字列であるものが存在するようにしてください。
文字列 $a$ が文字列 $b$ の部分文字列であるとは、ある正整数 $i$ であって $a_1 = b_i, a_2 = b_{i + 1}, a_3 = b{i + 2}, \ldots, a_{|a|} = b_{i + |a| - 1} が成り立つものが存在することをいいます。
例えば、`"GBRG", "B", "BR"` は無限に続く文字列 `"RGBRGBRGB..."` の部分文字列ですが、`"GR", "RGR", "GGG"` は違います。
あなたは $q$ 個の独立な質問に答えてください。
#### ●入力
##### **D1**
最初の行に、整数 $q (1 \leq q \leq 2000)$ として、質問の数が与えられます。その後、$q$ 個の質問が続きます。
各質問の最初の行に、2つの整数 $n, k (1 \leq k \leq n \leq 2000)$ として、文字列 $s$ の長さと部分文字列の長さがそれぞれ与えられます。
各質問の2行目に、`'R', 'G', 'B'` からなる長さ $n$ の文字列 $s$ が与えられます。
すべての質問の $n$ の和は $2000$ を超えないことが保証されます。
##### **D2**
最初の行に、整数 $q (1 \leq q \leq 2 \cdot 10^5)$ として、質問の数が与えられます。その後、$q$ 個の質問が続きます。
各質問の最初の行に、2つの整数 $n, k (1 \leq k \leq n \leq 2 \cdot 10^5)$ として、文字列 $s$ の長さと部分文字列の長さがそれぞれ与えられます。
各質問の2行目に、`'R', 'G', 'B'` からなる長さ $n$ の文字列 $s$ が与えられます。
すべての質問の $n$ の和は $2 \cdot 10^5$ を超えないことが保証されます。
#### ●出力
各質問に対して1つの整数を出力してください。
その整数は、無限長の文字列 `"RGBRGBRGB..."` の長さ $k$ の部分文字列が $s$ の部分文字列として存在するために $s$ を書き換える必要がある文字の最小個数です。
#### ●入出力例
##### 入力例1
```
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR
```
##### 出力例1
```
1
0
3
```
最初の例では、最初の文字を `'R'` にすることで部分文字列 `"RG"` を得るか、2文字目を `'R'` にして `"BR"` を得るか、3, 4, 5文字目のどれかを `'B'` に変えることで `"GB"` を得ることができます。
2つ目の例では、`"BRG"` が部分文字列として存在します。
:::
### ◎E. Connected Componet on a Chessboard
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
$b,w$ の2つの整数が与えられます。あなたは $10^9 \times 10^9$ のサイズのチェスボードを持っています。チェスボードの各マスは白・黒のどちらかで塗られており、辺を共有する2マスは異なる色で塗られています。一番左上のマスの座標を $(1;1)$ とします。この時、$(1;1)$ は白色でした。
このボードの中に $b$ 個の黒マスと $w$ 個の白マスからなる連結成分が存在するかを判定し、存在する場合は1つ求めてください。
より具体的には、辺を共有する2マスを隣接していると呼ぶとき、$b$ 個の黒マスと $w$ この白マスからなる $b+w$ 個のマスの集合 $s$ であって、集合に含まれる任意の2マスのペア $C_1,C_2$ について、$C_1$ から $C_2$ まで、「現在いるマスから隣接している、$s$ に含まれるマスへ移動する」操作を繰り返し到達可能な集合 $s$ の存在を判定し、存在する場合1つ求めてください。
#### ●入力
1行目に整数 $q (1 \le q \le 10^5)$ が与えられます。続いて、$q$ このクエリが与えられます。
各クエリは $b,w (1 \le b,w \le 10^5)$ の二つの整数からなります。これは、黒マスの数と白マスの数を表しています。
全てのクエリにおける、$b+w$ の総和は $2 \times 10^5$ 以下であることが保証されます。
#### ●出力
各クエリに答えてください。
連結成分が存在しない場合は、`NO` を出力し、次のクエリの回答へ移ってください。
存在する場合、`YES` を出力した後、$b+w$ 行出力してください。各行には、連結成分に含まれるマスの座標を `X Y` の形式で出力してください。出力する順番は何でも構いません。 ただし、$1 \le X,Y \le 10^9$ を満たす必要があることに注意してください。
#### ●入出力例
##### 入力例1
```
3
1 1
1 4
2 5
```
##### 出力例1
```
YES
2 2
1 2
YES
2 3
1 3
3 3
2 2
2 4
YES
2 3
2 4
2 5
1 3
1 5
3 3
3 5
```
:::
### ◎F. K-th Path
:::spoiler **クリックで展開**
TL: 2.5s ML: 256MB
#### ●問題
$n$ 頂点 $m$ 辺からなる重み付き連結無向グラフが与えられます。
あなたは、グラフ上の最短パスのうち短い方から $k$ 番目を出力してください。(自分自身へのパスはパスと見なさず、$i$ から $j$ と $j$ から $i$ のパスは一つとしてカウントします。)
より厳密には、$d$ を $d_{i, j}$ が頂点 $i, j (1 \leq i < j \leq n)$ 間の最短パスの長さであるような行列としたとき、$1 \leq i < j \leq n$ について全ての $d_{i, j}$ を含む配列をソートしたときの $k$ 番目の値を出力してください。
#### ●入力
最初の行に、3つの整数 $n, m, k (2 \leq n \leq 2 \cdot 10^5, n - 1 \leq m \leq \min \left( \frac{n(n-1)}{2}, 2 \cdot 10^5 \right), 1 \leq k \leq \min \left( \frac{n(n-1)}{2}, 400 \right) )$ として、グラフ上の頂点数、辺数、$k$ の値がそれぞれ与えられます。
続く $m$ 行のそれぞれに、3つの整数 $x, y, w (1 \leq x, y \leq n, 1 \leq w \leq 10^9, x \neq y)$ として、頂点 $x, y$ を結ぶ重み $w$ の辺が与えられます。
与えられたグラフが **連結** (任意の頂点対を結ぶパスが存在する) であること、自己ループ (ある頂点から自身に張られた辺) と多重辺 (各頂点対 $x, y$ について、この頂点対を結ぶ辺が2つ以上あること) が存在しないことが保証されます。
#### ●出力
1つの整数として、与えられたグラフの最短パスの長さで、小さい方から $k$ 番目を出力してください。
ある頂点から自身へのパスはカウントされず、$i$ から $j$ と $j$ から $i$ のパスは同じものとして考えます。
#### ●入出力例
##### 入力例1
```
6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5
```
##### 出力例1
```
3
```
##### 入力例2
```
7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
```
##### 出力例2
```
9
```
:::
## ◎ヒント・解説
### ◎A. Three Piles of Candies
:::spoiler **◎ヒント1(入力の受け取り方)**
まず、クエリの数 $q$ を受け取り、ループの中で各クエリについて答えていくとよいです。
なお、$a,b,c$ が非常に大きいため、C++においてはlong long型で受け取らないとオーバーフローしてしまいます。
```python=
# python
q = int(input())
for loop in range(q):
a,b,c = map(int,input().split())
# ここに処理を書く
```
```cpp=
// c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int q;
cin >> q;
for (int loop=0 ; loop<q ; ++loop){
ll a,b,c;
cin >> a >> b >> c;
//ここに、処理を書く
}
}
```
:::
:::spoiler **◎ヒント2**
いきなりコードを書くのではなく、じっくり問題を観察しましょう。
最後に残すセット(山)を3通り全探索しても良いですが…？
:::
:::spoiler **◎ヒント3**
一番大きいセットを、最後に2人で分ける場合を考えてみましょう。
なるべく均等に分けるには、どのように分けていけばいいでしょうか。
具体的に数字を設定して、分けるプロセスを手元でテストしてみましょう。
:::
:::spoiler **◎ヒント4**
あることに気が付くと、実装は非常に簡単になります。
具体的には、ヒント1のコードに1行足すだけで正解になります。
:::
:::spoiler **◎解説**
答えは、 $\lfloor \frac{(a+b+c)}{2} \rfloor$ です。
なぜかを解説していきます。
まず、$a \le b \le c$ であるとします。(なっていない場合、並べ替えます)
$a$ をAliceが、 $b$ をBobが取ります。そして、$c$ を分けていくことを考えます。
まず、Aliceにキャンディを、Bobと個数が等しくなるまで渡していきます。
$a+c > b$ なので、Bobと個数が等しくなる前にキャンディが足りなくなることはありません。
個数が等しくなったら、残りのキャンディを2こずつペアにして、AliceとBobに1こずつ渡していきます。
すると、キャンディは最大でも1個しか余らないはずです。
より踏み込むと、$a+b+c$ が奇数の時は1個キャンディがあまり、偶数の時は1個も余らないことになります。
よって答えは、 $\lfloor \frac{(a+b+c)}{2} \rfloor$ となります。
:::
:::spoiler **◎実装例(Python)**
```python=
# python
q = int(input())
for loop in range(q):
a,b,c = map(int,input().split())
print ( (a+b+c)//2 )
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
// c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int q;
cin >> q;
for (int loop=0 ; loop<q ; ++loop){
ll a,b,c;
cin >> a >> b >> c;
cout << (a+b+c)/2 << '\n';
}
}
```
:::
### ◎B. Odd Sum Segments
:::spoiler **◎ヒント1（入力の受け取り方)**
A問題と同様に $q$ を受け取った後、$q$ 回繰り返します。
空白区切りで $n$ 個の整数を受け取るのも含めると次のようになります。
```python=
# Python
q = int(input())
for loop in range(q):
n, k = map(int, input().split())
a = list(map(int, input().split()))
```
```cpp=
// C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int q;
cin >> q;
for (int loop = 0; loop < q; loop++) {
ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
}
}
```
:::
:::spoiler **◎ヒント2**
偶数は区間にいくつ含まれていても偶奇は変わりません。
:::
:::spoiler **◎ヒント3**
奇数要素の個数がいくつなら $k$ 個の区間に分割できるでしょうか。
:::
:::spoiler **◎ヒント4**
左端から和が奇数になったらそこを区間の右端にするようにして、最後に帳尻を合わせられないでしょうか。
:::
:::spoiler **◎解説**
ヒント4 の通り、左端から奇数要素が出てきたらそこまでを一つの区間にすることを繰り返します。
すると、$k-1$ 個の区間ができたときに残りの部分の和が奇数になっていたら分割できることがわかります。
ここで問題なのが、この方法で不可能だったときはどう分割しても不可能なのかどうかです。
この方法で不可能ということは、奇数の要素が $k - 1$ 個に加えて 偶数個余ったということになります。
しかし、$k$ 個の区間に分割できるときは奇数要素が $k$ 個に加えて偶数個必要で、またそのときに限ります。
したがって、この方法で不可能ならどうやっても不可能なので問題ないことがわかります。
後は安心して実装すると大丈夫です。
:::
:::spoiler **◎実装例(python3)**
```python=
q = int(input())
for loop in range(q):
n, k = map(int, input().split())
a = list(map(int, input().split()))
res = []
for i, x in enumerate(a):
if x % 2 == 1:
res.append(i + 1)
if len(res) < k or (len(res) - k) % 2 != 0:
print("NO")
else:
print("YES")
print(*res[:k - 1], n)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int q;
cin >> q;
for (int loop = 0; loop < q; loop++) {
ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> res;
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 1) {
res.push_back(i + 1);
}
}
if (res.size() < k || (res.size() - k) % 2 != 0) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
for (int i = 0; i < k - 1; i++) cout << res[i] << " ";
cout << n << endl;
}
}
}
```
:::
### ◎C. Robot Breakout
:::spoiler **◎ヒント1**
各ロボットについて、そのロボットが到達できないマスを塗っていくイメージを持ちましょう。
最後に塗られていないマスの内1つを出力すればよいです。
では、最終的に塗られていないマスの集合はどんな形をしているでしょうか？
:::
:::spoiler **◎ヒント2**
ヒント1の方針を考えたとき、塗られていないマスの集合は必ず長方形になります。
:::
:::spoiler **◎ヒント3**
長方形は、4辺の
:::
:::spoiler **◎解説**
まず、ヒントを読んでください。
1週間で、fish($a$) は3つ減ります。rabbit stew($b$) は2つ減り、chicken stakes($c$)も2つ減ります。
週の開始時点で上の3種類の内どれかが足りないと、その週を超すことはできません。
そのため、 $x = \rm{min}( \lfloor a/3 \rfloor , \lfloor b/2 \rfloor , \lfloor c/2 \rfloor )$
となります。
$y$ は、 $x$ 週間で減る食糧を $a,b,c$ から引いたのち、愚直に求めればよいです。
詳しい実装は、以下の実装の項目を参照してください。
:::
:::spoiler **◎実装例(Python)**
```python=
a,b,c = map(int,input().split())
food = "aabcacb"
ans = 0
for first_day in range(7): #最初の曜日
x = min(a//3 , b//2 , c//2)
eata = x*3
eatb = x*2
eatc = x*2
y = 0
for i in range(7): #yを愚直で求める
day = (first_day + i) % 7
if (food[day] == "a"):
eata += 1
elif (food[day] == "b"):
eatb += 1
else:
eatc += 1
if eata <= a and eatb <= b and eatc <= c:
y += 1
else:
break
ans = max(ans , 7*x + y)
print (ans)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b,c;
cin >> a >> b >> c;
string food = "aabcacb";
int ans = 0;
for (int first_day=0 ; first_day<7 ; first_day++){
int x = min( a/3 , min(b/2 , c/2) );
int eata = x*3;
int eatb = x*2;
int eatc = x*2;
int y = 0;
for (int i=0 ; i<7 ; i++){
int day = (first_day + i) % 7;
if (food[day] == 'a') eata++;
else if (food[day] == 'b') eatb++;
else eatc++;
if (eata<=a && eatb<=b && eatc<=c) y++;
else break;
}
ans = max(ans , 7*x+y);
}
cout << ans << '\n';
}
```
:::
### ◎D. RGB Substring
:::spoiler **◎ヒント0 (D2)**
Python の方は入力を `input()` で受け取ると遅いので、`input()` は次のように置き換えてください。
ただし、下の例はただの例でこの問題での入力を受け取るコードではありません。
最初の行で `import` した後、`input()` を `stdin.readline()` で置き換えればよいです。
```python=
from sys import stdin
# a, b = map(int, input().split())
a, b = map(int, stdin.readline().split())
```
:::
:::spoiler **◎ヒント1 (D1)**
二重ループを行っても $n$ の和が $2000$ 以下なので間に合います。
合計が $2000$ 以下と言われたときは、$n=2000$ の質問が1つだけの場合に AC できれば間に合うことがほとんどです。
:::
:::spoiler **◎ヒント2 (D1)**
`"RGB"` を繰り返す文字列の $i$ 番目は、`RGB = "RGB"` としたとき `RGB[i % 3]` で求められます。
`'G'` から始まる場合は `RGB[(i + 1) % 3]` のようにすればよいです。
:::
:::spoiler **◎ヒント3 (D1)**
$s$ の各位置から $k$ 文字を `"RGBRGB..."`、 `"GBRGBR..."`, `"BRGBRG..."` のそれぞれに一致させるために必要な書き換えの回数をすべて求めましょう。
その最小値が答えになります。
:::
:::spoiler **◎ヒント4 (D2)**
ヒント3で行ったことを、各位置について高速に求める方法はないでしょうか。
:::
:::spoiler **◎ヒント5 (D2)**
`RGB = "RGBRGB...", GBR = "GBRGBR...", BRG = "BRGBRG..."` とします。
$s$ の $i$ 文字目から $k$ 文字を `"RGBRGB..."` の部分文字列と一致させるのは、 RGB, GBR, BRG のどれかの $i$ 文字目から $k$ 文字と一致させるのと同じです。
:::
:::spoiler **◎ヒント6 (D2)**
2つの文字列 $s, t$ を一致させるのに必要な $s$ の書き換えの回数は、文字が異なる位置の個数に等しいです。
:::
:::spoiler **◎解説**
D1はヒント3を実装するだけなので、少し実装は複雑ですが解説を省略します。
D2については、ヒント5とヒント6を組み合わせて、文字が異なる箇所を1、同じ箇所を0とした配列の累積和を用意してあげればよいです。
例えば、`s = "BGGGG"` として `RGB = "RGBRG"` に対してのみ考えてみます。
このとき、異なる箇所だけ1にした配列は `[1, 0, 1, 1, 0]` となり、2, 3 文字目を `"GB"` にするには $0 + 1 = 1$ 文字書き換える必要があり、3, 4 文字目を `"BR"` に一致させるには $1 + 1 = 2$ 文字書き換える必要があるとわかります。
つまり、各 $i$ に対して `[i, i + k)` の和を累積和を用いて $O(1)$ で計算できればその最小値が答えになります。
左端が R, G, B の全てに対して行わないといけないことに注意しましょう。
:::
:::spoiler **◎実装例(python3)**
```python=
from sys import stdin
q = int(stdin.readline())
for loop in range(q):
n, k = map(int, stdin.readline().split())
s = stdin.readline()
RGB = "RGB"
res = k # 答えの最大値は k
for i in range(3):
# 左端が RGB[i] で $n$ 文字繰り返す文字列を作る
T = [RGB[(i + j) % 3] for j in range(n)]
diff = [0] * (n + 1)
for j in range(n):
diff[j + 1] = diff[j] + (s[j] != T[j])
for j in range(n - k + 1):
res = min(res, diff[j + k] - diff[j])
print(res)
```
:::
:::spoiler **◎実装例(C++)**
```python=
#include <bits/stdc++.h>
using namespace std;
int main() {
int q;
cin >> q;
for (int loop = 0; loop < q; loop++) {
int n, k;
string s;
cin >> n >> k;
cin >> s;
string RGB("RGB");
int res = k;
for (int i = 0; i < 3; i++) {
string T(n, 'x');
for (int j = 0; j < n; j++) T[j] = RGB[(i + j) % 3];
vector<int> diff(n + 1, 0);
for (int j = 0; j < n; j++) diff[j + 1] = diff[j] + (s[j] != T[j]);
for (int j = 0; j < n - k + 1; j++) {
res = min(res, diff[j + k] - diff[j]);
}
}
cout << res << endl;
}
}
```
:::
### ◎E. Connected Componet on a Chessboard
※ ここが前回のままになっておりました、ご迷惑おかけして申し訳ございません (10/19朝更新)
:::spoiler **◎ヒント1**
ある色がもう一色よりも多すぎる場合、答えは存在しません。
答が存在しない条件を考えてみましょう。
:::
:::spoiler **◎ヒント2**
$b = 0$ の場合、答がYESとなるような $w$ の最大値はいくつでしょうか。
$b = 1$ の場合は？
$b = 2$ の場合は？
$b = 3$ の場合は？
と考えていくと規則性が見えてきます。
:::
:::spoiler **◎ヒント3**
作れる条件が分かったら、具体的な構築方法を考えていきます。
ヒント2のように、黒に対して白をなるべくたくさん置く場合の構築方法をまず考えてみましょう。
:::
:::spoiler **◎ヒント4**
ヒント3のアイデアを拡張することで、一般の場合を解決しましょう。
ヒントは、置かなければいけない残りの白・黒の数を管理することです。
:::
:::spoiler **◎ヒント5**
盤面の端の方から始めるとはみ出してしまうリスクがあるので、真ん中あたりから始めるといいです。
:::
:::spoiler **◎解説**
$3b+1 < w$ または $3w+1 < b$ の場合、作ることができません。
逆に、 $3b+1 \ge w$ かつ $3w+1 \ge b$ の場合は作ることができます。
つまり、$b$ 個黒を取るとき、取る事ができる白の最大個数は $3w+1$ 個という事になります。
そして、$b = 3$ の時に 白をなるべくたくさん取った場合( $w=3b+1=10$ )が以下です。
数字は、採用していく順番のイメージを表しています。
まず、白をなるべくたくさん取りたいので、数字1の箇所の白を取ります。
次は、これ以上白を置けないので、仕方なく隣の黒(2)を取ります。
黒を取ると周囲3か所の白が取れるようになるので、3,4,5を取ります。
次は、白をこれ以上取れないので仕方なく6番目の黒を取ります…
6を取ったので、周囲3箇所の白が取れるようになり、7,8,9を取ります
…
といった感じで取っていくイメージを表しています。
これ以上白を置くことはできず、全体の連結性を保ちつつよりたくさん白が置けるように黒の位置を変えることもできないのでこれが最適であることが分かります。
では、一般の場合を考えてみます。
説明が難しいので、具体例で説明していきたいと思います。
例として、 $b = 6,w = 14$ の場合を考えてみます。
この場合は、以下のようにすることで目標を達成できます。
残り取るべき黒の個数を $B$, 残り取るべき白の個数を $W$ とします。
つまり、何も取っていない状態だと $B=b=6, W=w=14$ です。
まず、白をたくさん取りたいのは前の例と同じです。
ですので、まず 白(1) を取ります。この時点で $B=6,W=13$ です。
次に、$B < W$ なので白を取りたいです。しかし、1番の周りに白は存在しないため、仕方なく黒(2)を取ります。 この時点で $B=5,W=13$ です。
この時点で、$B < W$ なので次は白を取りたいです。2番の上がちょうど白マスなのでここを取ります。この時点で $B=5, W=12$ です。
$B < W$ なので白を取りたいです。2番の下が白マスなので、ここを取ります。この時点で $B=5,W=11$ です。
$B < W$ なので白を取りたいです。2番の右が白マスなので、ここを取ります。この時点で $B=5,W=10$ です。
$B < W$ なので白を取りたいですが、今まで取ったマスの周囲に白マスはもうありません。ですから、仕方なく5の隣の黒(6)を取ります。
この時点で $B=4,W=11$ です。
…
…
$B < W$ なので白を取りたいです。14番の上が白マスなので、ここを取ります。この時点で $B=2,W=3$ です。
$B < W$ なので白を取りたいです。14番の下が白マスなので、ここを取ります。この時点で $B=2,W=2$ です。
はい！！！この時点で $B = W$ となったので、ここからは右にまっすぐ取っていきます。すると、白黒が交互に取られるので、いつかは $B=W=0$ の瞬間がやってきます。$B=W=0$になったら、取る操作を終了すれば、上のような答えを構築することができます。
:::
### ◎F. K-th Path
:::spoiler **◎ヒント1**
$k$ は最大 $400$ と小さいです。
:::
:::spoiler **◎ヒント2**
短い方から $k$ 番目のパスまでに使われないことが確定している辺はないでしょうか。
:::
:::spoiler **◎解説**
短い方から $k$ 本以外の辺は、最短 $k$ 個のパスに使われることはありません。
なので、辺を重みでソートして小さい方から $k$ 本とそれらにつながっている頂点だけを取り出せば、
頂点数がたかだか $2k$ のグラフになるので全点対最短路をダイクストラ法で計算すると
計算量は $O(k^2 \log k)$ になり間に合います。
:::
Sign in with Wallet
Connect another wallet