# 競プロ講習会第12回 Web資料
## ◎第12回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #12 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Vertual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/f5e0933c5649b27626d7a34019d7d0886866b156
#### ◎公式解説
##### A〜G問題
https://codeforces.com/blog/entry/66586
## ◎問題訳(意訳あり注意)
### ◎A. Restoring Three Numbers
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Polycarp は3つの正整数 $a, b, c$ を言い当てた後に秘密にしていましたが、黒板に4つの整数を適当な順番で書きました。
4つの整数は、各ペアの和である3つと全整数の和である1つからなります。
つまり、黒板には $a+b, a+c, b+c, a+b+c$ がランダムに並んでいます。
この4つの整数から、$a, b, c$ を推測してください。推測した整数は任意の順番で出力してください。
$a, b, c$ のうち、いくつかの整数は等しい可能性もあることに注意してください。
#### ●入力
最初の行に、4つの整数 $x_1, x_2, x_3, x_4 (2 \leq x_i \leq 10^9)$ として、黒板にランダムな順に書かれた整数が与えられます。
与えられた整数 $x_1, x_2, x_3, x_4$ に対して、答えが存在することが保証されます。
#### ●出力
黒板に書かれた整数が $a+b, a+c, b+c, a+b+c$ の適当な順番であるような正整数 $a, b, c$ を任意の順番で出力してください。
複数の答えが存在する場合、いずれを出力しても構いません。
答えが存在することは保証されています。
#### ●入出力例
##### 入力例1
```
3 6 5 4
```
##### 出力例1
```
2 1 3
```
##### 入力例2
```
40 40 40 60
```
##### 出力例2
```
20 20 20
```
##### 入力例3
```
201 101 101 200
```
##### 出力例3
```
1 100 100
```
:::
### ◎B. Make Them Equal
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
$n$ 個の整数からなる数列 $a_1, a_2, \ldots, a_n$ が与えられます。
あなたは、任意の正整数 $D (D \geq 0)$ を選んだ後、各 $a_i$ に対して次の操作のいずれかを行えます。
- $D$ を1回だけ足す。つまり、$a_i := a_i + D$ とする。
- $D$ を1回だけ引く。つまり、$a_i := a_i - D$ とする。
- $a_i$ を変化させず、そのままにする。
操作の後、$a_i$ が負になってもよいです。
あなたの目標は、操作を適切に行うことですべての $a_i$ が等しくなるような ***最小の非負整数 $D$*** を選ぶことです。
そのような $D$ を出力するか、存在しない場合は $-1$ を出力してください。
例えば、配列 `[2, 8]` に対しては $D = 3$ が最小で、$D$ を $2$ に加え、$D$ を $8$ から引くと `[5, 5]` となります。
`[1, 4, 7, 7]` の場合も、$D = 3$ が最小で、$1$ に足して $7$ から引くことで `[4, 4, 4, 4]` が得られます。
#### ●入力
1行目に、1つの整数 $n (1 \leq n \leq 100)$ として、$a$ の要素数が与えられます。
2行目に、$n$ 個の整数 $a_1, a_2, \ldots, a_n (1 \leq a_i \leq 100)$ として、数列 $a$ が与えられます。
#### ●出力
1つの整数として、操作を行うことで数列のすべての要素が等しくなるような ***最小の非負整数 $D$*** を出力してください。
そのような $D$ が存在しない場合は $-1$ を出力してください。
#### ●入出力例
##### 入力例1
```
6
1 4 4 7 4 1
```
##### 出力例1
```
3
```
##### 入力例2
```
5
2 2 5 2 5
```
##### 出力例2
```
3
```
##### 入力例3
```
4
1 3 3 7
```
##### 出力例3
```
-1
```
##### 入力例4
```
2
2 8
```
##### 出力例4
```
3
```
:::
### ◎C. Gourmet Cat
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Polycarp は猫を1匹買っていてとても美食家です。 曜日によって、食べるものの種類が決まっています。
- 月曜日、木曜日、日曜日は **魚** を食べる
- 火曜日、土曜日は **うさぎのシチュー** を食べる
- 残りの曜日は **チキンステーキ** を食べる
Polycarp は旅行に行く予定で、リュックに荷造りを終えました。 リュックには、
- $a$ 日分の魚料理
- $b$ 日分のうさぎのシチュー
- $c$ 日分のチキンステーキ
が含まれています。
Polycarp は、追加で購入しなくても猫が食べたいものができるだけ長く残るような曜日に出発します。
Polycarp が最適な曜日に出発したとき、追加の食べ物を買わなくても、猫が食事できる最大の日数を出力してください。
#### ●入力
1行目に、3つの整数 $a, b, c (1 \leq a, b, c \leq 7 \cdot 10^8)$ として、魚料理、うさぎのシチュー、チキンステーキが何日分リュックの中にあるかがそれぞれ与えられます。
#### ●出力
Polycarp が最適な曜日に出発したとき、追加の食べ物を買わなくても、猫が食事できる最大の日数を出力してください。
#### ●入出力例
##### 入力例1
```
2 1 1
```
##### 出力例1
```
4
```
日曜日に出発するのが最適です。この場合、日曜日と月曜日に魚料理を食べ、火曜日はうさぎのシチュー、水曜日はチキンステーキを食べるので、4日後にすべての食料が食べ尽くされます。
##### 入力例2
```
3 2 2
```
##### 出力例2
```
7
```
どの曜日に Polycarp が出発しても、ちょうど1週間分の食料がリュックに入っています。
##### 入力例3
```
1 100 1
```
##### 出力例3
```
3
```
水曜日、土曜日、日曜日以外ならどの曜日でも出発できます。
この場合、最初の3日で3種類の異なる料理を食べた後、 $99$ 日分のうさぎのシチューがリュックの中に余っていますが、4日目に猫が食べたいものはありません。
##### 入力例4
```
30 20 10
```
##### 出力例4
```
39
```
:::
### ◎D. Walking Robot
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
x軸上の $X = 0$ の点にロボットがいて、$X = n$ の点まで歩く必要があります。あなたは、このロボットの移動を操作することができて、ロボットはバッテリーとソーラーパネル付きの蓄電池を搭載しています。
道のりの $i$ 番目の区間 ($X = i-1$ から $X = i$ まで) は、日光にさらされているかいないかのどちらかです。配列 $s$ は、どの区間が日光にさらされているかを表していて、$i$ 番目の区間は $s_i = 1$ ならさらされていて、$s_i = 0$ なら日陰です。
ロボットは容量が $b$ のバッテリーが1つと、容量が $a$ の蓄電池が1つ搭載しています。各区間で、次の地点にいくまでどちらのエネルギー源を使うか選ぶことができます。バッテリーを使う場合、残量はちょうど1減ります (バッテリー残量が0であれば使うことはできません)。蓄電池を使う場合も同様で、残量はちょうど1減り、残量が0であれば使うことはできません。
もしも現在の区間が ***日光にさらされていて*** 、***バッテリーを使用して*** 移動している場合、蓄電池の残量は 1 増えます。もちろん、残量は容量よりも多くなることはありません。
区間を通過するときに蓄電池を使用している場合、日光にさらされているかどうかに関わらず残量は1減ります。
$X = n$ まで歩くことが常に可能ではないため、できる限り遠くまで移動させたいです。適切にロボットを操作したとき、最大でいくつの区間を通過することができるかを求めてください。
#### ●入力
1行目に、3つの整数 $n, b, a (1 \leq n, b, a \leq 2 \cdot 10^5)$ として、ロボットの目的地、バッテリー容量、蓄電池容量がそれぞれ与えられます。
2行目に、$n$ 個の整数 $s_1, s_2, \ldots, s_n (0 \leq ) が与えられます。 $s_i$ は $i$ 番目の区間が日光にさらされている場合は $1$、そうでない場合は $0$ です。
#### ●出力
1つの整数として、適切にロボットを操作したときに通過できる区間の最大数を出力してください。
#### ●入出力例
##### 入力例1
```
5 2 1
0 1 0 1 0
```
##### 出力例1
```
5
```
最初の区間は蓄電池を使うと、残量は $b = 2, a = 0$ になります。
2つ目の区間はバッテリーを使うと、日光にさらされているため $b = 1, a = 1$ になります。
3つ目の区間は蓄電池を使い $b = 1, a = 0$、4つ目の区間はバッテリーで $b = 0, a = 1$、最後の区間は蓄電池を使うことで通過することができます。
##### 入力例2
```
6 2 1
1 0 0 1 0 1
```
##### 出力例2
```
3
```
バッテリー2回、蓄電池1回を任意の順番で使うと、最大数の区間を通過することができます。
:::
### ◎E. Two Teams
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
$n$ 人の生徒が1列に並んでいて、2人のコーチがチームを作ろうとしています。1人目のコーチは1つ目のチームを、2人目のコーチは2つ目のチームを選びます。
$i$ 番目の生徒は整数として表されるプログラミングスキル $a_i$ を持っていて、すべてのプログラミングスキルは $1$ から $n$ の異なる値をとります。
まず、1人目のコーチがどのチームにも属していない人の中で最大のプログラミングスキルを持つ生徒と、その生徒の左側で最も近い生徒 $k$ 人と右側で最も近い生徒 $k$ 人を選びます。左側や右側にいる生徒が $k$ 人よりも少ない場合は全員が選ばれます。選ばれた生徒は、全員列を抜けて1つ目のチームに入ります。次に、2人目のコーチが同じことをして、選ばれた生徒は2つ目のチームに入ります。その後、再び1人目のコーチが同じことを行い、と続いていきます。列が空になるまでこれを繰り返します。つまり、最終的にすべての生徒はどちらかのチームに入っています。
あなたは、各生徒がどちらのチームに入ることになるかを求めてください。
#### ●入力
最初の行に、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 n)$ が与えられます。 $a_i$ は $i$ 人目の生徒のプログラミングスキルで、すべてのプログラミングスキルは異なります。
#### ●出力
$n$ 文字からなる文字列を出力してください。 $i$ 文字目は、$i$ 人目の生徒が 1 つ目のチームに入るときは `1`、そうでなければ `2` としてください。
#### ●入出力例
##### 入力例1
```
5 2
2 4 5 3 1
```
##### 出力例1
```
11111
```
1人目のコーチが3番目の生徒を選び、すべての生徒が1つ目のチームに入って列は空になります。
##### 入力例2
```
5 1
2 1 3 5 4
```
##### 出力例2
```
22111
```
1人目のコーチは4番目の生徒を選び、列は `[2, 1]` になります。プログラミングスキルが `[3, 4, 5]` の生徒は1つ目のチームに入ります。
そして、2人目のコーチは1番目の生徒を選び、列は空になります。プログラミングスキルが `[1, 2]` の生徒は2つ目のチームに入ります。
##### 入力例3
```
7 1
7 2 1 3 5 4 6
```
##### 出力例3
```
1121122
```
1人目のコーチは1番目の生徒を選んで列は `[1, 3, 5, 4, 6]` になり、プログラミングスキル `[2, 7]` の生徒は1つ目のチームに入ります。
2人目のコーチは5番目の生徒を選んで列は `[1, 3, 5]` になり、プログラミングスキル `[4, 6]` の生徒は2つ目のチームに入ります。
1人目のコーチは3番目の生徒を選んで列は `[1]` になり、プログラミングスキル `[3, 5]` の生徒は1つ目のチームに入ります。
2人目のコーチが残りの生徒を選び、プログラミングスキル `1` の生徒が2つ目のチームに入ります。
##### 入力例4
```
5 1
2 4 5 3 1
```
##### 出力例4
```
21112
```
1人目のコーチは3番目の生徒を選んで列は `[2, 1]` になり、プログラミングスキル `[3, 4, 5]` の生徒は 1 つ目のチームに入ります。
2人目のコーチは1番目の生徒を選んで列は空になり、プログラミングスキル `[1, 2]` の生徒は2つ目のチームに入ります。
:::
### ◎F. Shovels Shop
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
$n$ 本のショベルが近所の店にあり、$i$ 番目のショベルは $a_i$ bourles かかります。
Misha は ***ちょうど*** $k$ 本のショベルを買う必要があって、各ショベルは最大1回しか購入できません。
Misha は複数回の購入に分けてショベルを買うことができ、1回の購入では残っている(まだ購入していない)ショベルのうちいくつかを選んで購入できます。
このお店では $m$ 個の特別なクーポンがあり、 $j$ 番目のクーポンは $(x_j, y_j)$ というペアで表されます。これは、 Misha が ***ちょうど*** $x_j$ 本のショベルを1度に購入すると、安い方から $y_j$ 本のショベルが無料で手に入るというものです。つまり、その購入では $y_j$ 本の最も安いショベルに対して支払う必要はありません。
Misha は、どのクーポンを何回 (0回も可) でも使うことができますが、***一度の購入*** で ***2つ以上*** のクーポンを使用することはできません。ただし、クーポンを使わずに購入することはできます。
Misha が適切に購入したとき、 $k$ 本のショベルを買うのにかかる最小のコストを求めてください。
#### ●入力
1行目に、3つの整数 $n, m, k (1 \leq n, m \leq 2 \cdot 10^5, 1 \leq k \leq \min(n, 2000))$ として、お店にあるショベルの本数、特別なクーポンの個数、Misha が買う必要があるショベルの本数がそれぞれ与えられます。
2行目に、$n$ 個の整数 $a_1, a_2, \ldots, a_n (1 \leq a_i \leq 2 \cdot 10^5)$ が与えられます。 $a_i$ は $i$ 番目のショベルのコストです。
続く $m$ 行で特別なクーポンの情報が与えられます。 $j$ 番目には、整数のペア $(x_j, y_j) (1 \leq y_j \leq x_j \leq n)$ が与えられ、Misha が ちょうど $x_j$ 本のショベルを購入すると、安い方から $y_j$ 本のショベルが無料で手に入ることを意味しています。
#### ●出力
1つの整数として、Misha が適切に $k$ 本のショベルを購入したときにかかる最小のコストを出力してください。
#### ●入出力例
##### 入力例1
```
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1
```
##### 出力例1
```
7
```
Misha は 1番目と4番目の (どちらもコストが2) ショベルを最初の購入で買うことができ、1つ目か3つ目のクーポンを使うと1本が無料で手に入ります。
そして、3番目と6番目の (コストはそれぞれ 4, 3) ショベルを2つ目の購入で買うと、クーポンを使って6番目のショベルが無料で手に入ります。
最後に7番目のショベルを無料で手に入れると、合計コストは $2 + 4 + 1 = 7$ となります。
##### 入力例2
```
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7
```
##### 出力例2
```
17
```
Misha は 1, 2, 3, 4, 8 番目の (コストは 6, 8, 5, 1, 2) ショベルを買うと、3つの安いショベル (コストは 5, 1, 2) が無料で手に入ります。
そして、6, 7, 9番目の (コストはすべて1) ショベルをクーポンを使わずに買います。
最終的なコストは $6 + 8 + 1 + 1 + 1 = 17$ になります。
##### 入力例3
```
5 1 4
2 5 7 4 6
5 4
```
##### 出力例3
```
17
```
安い方から4つのショベルをクーポンを使わずに買うと、合計コストは $17$ になります。
:::
### ◎G. Minimum Possible LCM
:::spoiler **クリックで展開**
TL: 4s ML: 1024MB
#### ●問題
$n$ 個の整数、$a_1, a_2, \ldots, a_n$ からなる配列 $a$ が与えられます。
添字のペア $i, j (1 \leq i < j \leq n)$ であって、$\mathrm{lcm}(a_i, a_j)$ が最小となるものを見つけてください。
$\mathrm{lcm}(x, y)$ は、$x$ と $y$ の最小公倍数 ($x$ と $y$ がどちらも約数であるような正整数で最小のもの) を表します。
#### ●入力
1行目には、1つの整数 $n (2 \leq n \leq 10^6)$ として、$a$ に含まれる要素の数が与えられます。
2行目には、$n$ 個の整数 $a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^7)$ が空白区切りで与えられます。 $a_i$ は $a$ の $i$ 番目の要素です。
#### ●出力
2つの整数 $i, j (1 \leq i < j \leq n)$ を出力してください。
この $i, j$ は、 $\mathrm{lcm}(a_i, a_j)$ がすべての有効な $i, j$ のペアの中で最小となるものにしてください。
答えが複数ある場合は、いずれの答えを出力しても構いません。
#### ●入出力例
##### 入力例1
```
5
2 4 8 3 6
```
##### 出力例1
```
1 2
```
##### 入力例2
```
5
5 2 11 3 7
```
##### 出力例2
```
2 4
```
##### 入力例3
```
6
2 5 10 1 10 2
```
##### 出力例3
```
1 4
```
:::
## ◎ヒント・解説
### ◎A. Restoring Three Numbers
:::spoiler **◎ヒント1**
$x1,x2,x3,x4$ を別々の変数として受け取ってもよいのですが、この問題では配列形式で受け取ったほうが都合がよいです。
データの受け取り方ひとつで、その後の実装の楽さが段違いとなります。
具体的には、以下のようにして入力を受け取るのがおすすめです。
```python=
# python
x = list(map(int,input().split()))
# ここに処理を書く
```
```cpp=
// c++
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> x(4);
cin >> x[0] >> x[1] >> x[2] >> x[3];
//ここに、処理を書く
}
```
:::
:::spoiler **◎ヒント2**
$a+b+c$ は、与えられる4つの数の中で最大のものです。
また、4つの数の内最大のものはソートをすることにより求まります。
4つの数を別々の変数で受け取ると、どの変数が最大なのか記録しておく必要が出るため、実装が大変になります。
```python=
# python
x = list(map(int,input().split()))
x.sort()
# この時点で、x[3] == a+b+c になっている。
# ここに残りの処理を書く
```
```cpp=
// c++
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> x(4);
cin >> x[0] >> x[1] >> x[2] >> x[3];
sort(x.begin(),x.end());
// この時点で、x[3] == a+b+c になっている。
// ここに、残りの処理を書く
}
```
:::
:::spoiler **◎ヒント3**
$a = (a+b+c)-(b+c)$
$b = (a+b+c)-(a+c)$
$c = (a+b+c)-(a+b)$
なので、4つの数のうち、最大の数から別の数を引くと、$a,b,c$ のどれかになります。
:::
:::spoiler **◎ヒント4**
$a,b,c$ はどの順番で出力しても構わないので、ヒント3で計算した3つの数字のうち、ある数は$a,b,c$のどれなのかを特定する必要はありません。
:::
:::spoiler **◎解説**
概ねヒントで書いたとおりです。
$x$ を受け取り、sortすると $x[3]$ がa+b+cになるので、$x[3]-x[0] , x[3]-x[1] , x[3]-x[2]$ の3つの数を出力すればよいです。
:::
:::spoiler **◎実装例(Python)**
```python=
# python
x = list(map(int,input().split()))
x.sort()
# この時点で、x[3] == a+b+c になっている。
print (x[3]-x[0] , x[3]-x[1] , x[3]-x[2])
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
// c++
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> x(4);
cin >> x[0] >> x[1] >> x[2] >> x[3];
sort(x.begin(),x.end());
// この時点で、x[3] == a+b+c になっている。
cout << x[3]-x[0] << " " << x[3]-x[1] << " " << x[3]-x[2] << '\n';
}
```
:::
### ◎B. Make Them Equal
:::spoiler **◎ヒント1**
値の種類数で場合分けしましょう。
PythonとC++では、入力されたリストから各種類1つだけ取り出したソート済みのリストは次のようにすると手に入ります。
```python=
# Python
n = int(input())
a = list(map(int, input().split()))
a = sorted(list(set(a)))
```
```cpp=
// C++
#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];
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
```
:::
:::spoiler **◎ヒント2**
最大1回しか操作できないので、4種類以上だと不可能です。
:::
:::spoiler **◎ヒント3**
値の2種類であるときは、2通りの方法で一致させられることがあります。
:::
:::spoiler **◎解説**
値の種類数で次のように場合分けします。
#### 1種類のとき
$D = 0$ としてすべての要素をそのままにすればよいです。
#### 2種類のとき
2種類の値が $x < y$ であるとき、$y - x$ の偶奇で場合分けします。
- 偶数のとき
- $D = \frac{y - x}{2}$ とすると、 $x + D = y - D$ となります
- 奇数のとき
- $D = y - x$ とすると、 $x + D = y$ となります
偶数のときは、$\frac{y - x}{2} < y - x$ なので $D$ として $y - x$ とすると最小ではありません。
#### 3種類のとき
3種類の値を $x < y < z$ とするとき、$z - y = y - x$ であるときのみ $D = y - x$ とすることで最小かつ達成可能です。
それ以外の場合は不可能です。
#### 4種類以上のとき
不可能です。
ここまでをまとめて実装すると良いです。
:::
:::spoiler **◎実装例(python3)**
```python=
n = int(input())
a = list(map(int, input().split()))
a = sorted(list(set(a)))
if len(a) == 1:
print(0)
elif len(a) == 2:
if (a[1] - a[0]) % 2 == 0:
print((a[1] - a[0]) // 2)
else:
print(a[1] - a[0])
elif len(a) == 3:
if a[2] - a[1] == a[1] - a[0]:
print(a[1] - a[0])
else:
print(-1)
else:
print(-1)
```
:::
:::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];
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
if (a.size() == 1) {
cout << 0 << endl;
} else if (a.size() == 2) {
if ((a[1] - a[0]) % 2 == 0) {
cout << (a[1] - a[0]) / 2 << endl;
} else {
cout << a[1] - a[0] << endl;
}
} else if (a.size() == 3) {
if (a[2] - a[1] == a[1] - a[0]) {
cout << a[1] - a[0] << endl;
} else {
cout << -1 << endl;
}
} else {
cout << -1 << endl;
}
}
```
:::
### ◎C. Gourmet Cat
:::spoiler **◎ヒント1**
始まりの曜日を全探索し、その内最大のものを出力すればよいです。
ここでは、始まりの曜日を週の始まりとして考えていきます。
:::
:::spoiler **◎ヒント2**
$a,b,c$ がかなり大きいので、愚直に解こうとするとTLEになります。
:::
:::spoiler **◎ヒント3**
始まりの曜日を固定したとき、$x$ 週間と $y$ 日間だけ、エサが食べられると考えます。
工夫をすると、 $x$ , $y$ はそれぞれ高速に求められます。
:::
:::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. Walking Robot
:::spoiler **◎ヒント1**
日光にさらされている区間はできるだけバッテリーを使って進み、蓄電池を充電したいです。
:::
:::spoiler **◎ヒント2**
そのためには、その前に蓄電池を使用して充電できるようにしておきたいです。
:::
:::spoiler **◎解説**
まず、どちらかの残量が 0 になっている場合はもう一方を使用して進むしかありません。
そうでなければ、充電できるタイミングで満充電になっているともったいないため、基本的に蓄電池を使用して進みます。
日光にさらされている区間については、蓄電池が充電できるときはバッテリーを使い、そうでなければ蓄電池を使います。
この手続きを丁寧に実装すればよいです。
実装例はこのまま実装しているので場合分けが複雑になっていますが、条件をもう少し考えると簡潔になります。
:::
:::spoiler **◎実装例(python3)**
```python=
n, b, a = map(int, input().split())
s = list(map(int, input().split()))
b_now = b
a_now = a
res = 0
for seg in s:
if a_now == 0 and b_now == 0:
break
res += 1
if a_now == 0:
b_now -= 1
if seg == 1:
a_now += 1
elif b_now == 0 or a_now == a:
a_now -= 1
else:
if seg == 1:
b_now -= 1
a_now += 1
else:
a_now -= 1
print(res)
```
:::
:::spoiler **◎実装例(C++)**
```python=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, b, a;
cin >> n >> b >> a;
vector<int> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
int b_now = b, a_now = a, res = 0;
for (auto seg: s) {
if (a_now == 0 && b_now == 0) {
break;
}
res++;
if (a_now == 0) {
b_now--;
if (seg == 1) a_now++;
} else if (b_now == 0 || a_now == a) {
a_now--;
} else {
if (seg == 1) {
b_now--;
a_now++;
} else {
a_now--;
}
}
}
cout << res << endl;
}
```
:::
### ◎E. Two Teams
:::spoiler **◎ヒント1**
愚直にやると間に合いません。
ここで言う愚直とは、以下ような方法のことです。
各 $i$ について、$i$ 番目の人が既にチームに属しているかを記録しておきます。
操作を行う際は、 残っている人の内 $a_i$ が一番大きい $i$ を見つけ出し、 $i$ の左右を、$k$ 人未確定の人を見つけるまで線形探索し続ける方法です。
上に方法でTLEになる例として、以下の場合を考えてみましょう。
$k = 1$ で、$a = [ ...,n-5,n-3,n-1,n,n-2,n-4,n-6,... ]$
であるとします。最初に $n-1,n,n-2$ が取られます。2回目の操作では、$n-5,n-3,n-4$が取られます。
この時、1回目の操作で生まれた3枠の隙間を飛び越えるように削除操作が行われています。
3回目以降の操作でも、必ずこの隙間を飛び越えるように削除操作が行われます。
隙間はだんだん拡大していくので、隙間のサイズは $O(n)$ であり、削除回数が $O(n)$ なので計算量は $O(n^2)$ になってしまいます。
:::
:::spoiler **◎ヒント2**
連結リストというデータ構造を知っていますか？
以下の記事を読んでみるといいと思います。
https://www.momoyama-usagi.com/entry/info-algo-list#nbsp
:::
:::spoiler **◎ヒント3**
ただ連結リストを使用するだけでは解くことができません。
なぜなら、連結リストを使用すると 「$a_i$ が最大となる $i$ にアクセスする。」操作が $O(n)$ かかるようになってしまうからです。
:::
:::spoiler **◎ヒント4**
連結リストと配列、両方の利点を持ったデータの持ち方を考えましょう。
そんなのできるの？と思うかもしれませんが、値の削除しかしない今回の場合においては可能です。
:::
:::spoiler **◎解説**
1つ目として、「まだチームに所属していない人のうち、$a_i$ が最大の人」を高速に見つける方法が必要です。
これにはまず、動的配列を用意しておき、$(a_i,i)$ のペア/タプルを全て入れて昇順ソートしておきます。
この動的配列の一番後ろの人が既にチームに所属している場合は、即座にpop_backするようにしておきます。
こうしておけば、「まだチームに所属していない人のうち、$a_i$ が最大の人」を見つけたいときは、動的配列の一番後ろのペアを見ればよいことになります。
2つ目として、指定した要素へのアクセスが $O(1)$ で行える双方向連結リストが必要です。
これは、リストの各要素への参照を配列に入れておくことにより解決できます。
詳しくは、実装例をご覧ください。
:::
:::spoiler **◎実装例(python3)**
特にclass等を作成せずに記述しています。
```python=
import sys
from sys import stdin
n,k = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))
ai = [ (a[i],i) for i in range(n) ]
ai.sort()
l = [None] + [i for i in range(n-1)] #まだチームに所属していないすぐ左の要素のindex
r = [i for i in range(1,n)] + [None] #まだチームに所属していないすぐ右の要素のindex
exist = [True] * n #まだチームに所属していない場合True
def lisdel(i): #i番目の人を削除する関数,exist,l,r 3つの配列を正しく書き換える
exist[i] = False
iL = l[i]
iR = r[i]
# i番目が消えると、iLの右の要素、iRの左の要素が変化する
if iL != None:
r[iL] = iR
if iR != None:
l[iR] = iL
ans = [None] * n
turn = 1
while ai:
na,ni = ai[-1]
del ai[-1]
if exist[ni]:
#ni番目を、削除する。
ans[ni] = str(turn)
lisdel(ni)
#niの左右からk個を削除する。
Lidx = l[ni]
Ridx = r[ni]
for i in range(k):
if Lidx == None:
break
ans[Lidx] = str(turn)
newLidx = l[Lidx]
lisdel(Lidx)
Lidx = newLidx
for i in range(k):
if Ridx == None:
break
ans[Ridx] = str(turn)
newRidx = r[Ridx]
lisdel(Ridx)
Ridx = newRidx
turn ^= 3 # 1 <-> 2 が切り替わる
print ("".join(ans))
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
void lisdel(int i,vector<int>& l,vector<int>& r,vector<bool>& exist){
exist[i] = false;
int iL = l[i];
int iR = r[i];
if (iL != -1){
r[iL] = iR;
}
if (iR != -1){
l[iR] = iL;
}
}
int main(){
int n,k;
cin >> n >> k;
vector<int> a(n);
rep(i,0,n) cin >> a[i];
vector<pair<int,int>> ai;
rep(i,0,n) ai.push_back(make_pair(a[i],i));
sort(ai.begin(),ai.end());
// lは、まだチームに所属していないすぐ左の要素のindex
// rは、まだチームに所属していないすぐ右の要素のindex
// -1の場合、端で存在しないことを表す
vector<int> l(n,-1),r(n,-1);
rep(i,1,n) l[i] = i-1;
rep(i,0,n-1) r[i] = i+1;
vector<bool> exist(n,true);
vector<int> ans(n);
int turn = 1;
while (!ai.empty()){
int na = ai.back().first;
int ni = ai.back().second;
ai.pop_back();
if (exist[ni]){
//ni番目を、削除する。
ans[ni] = turn;
lisdel(ni,l,r,exist);
//ni番目から左右k個を、削除する。
int Lidx = l[ni];
int Ridx = r[ni];
rep(i,0,k){
if (Lidx == -1) break;
ans[Lidx] = turn;
int newLidx = l[Lidx];
lisdel(Lidx,l,r,exist);
Lidx = newLidx;
}
rep(i,0,k){
if (Ridx == -1) break;
ans[Ridx] = turn;
int newRidx = r[Ridx];
lisdel(Ridx,l,r,exist);
Ridx = newRidx;
}
turn ^= 3;
}
}
rep(i,0,n){
cout << ans[i];
}
cout << '\n';
}
```
:::
### ◎F. Shovels Shop
:::spoiler **◎ヒント1**
$k$ は最大 2000 と小さいです。
:::
:::spoiler **◎ヒント2**
各クーポン (offer) は何回でも使用できるので、同じ $x_j$ であれば $y_j$ が最大のものだけ使えばよいです。
また、$x_j > k$ であるようなクーポンは使わないので除外できます。
:::
:::spoiler **◎ヒント3**
最終的に購入する $k$ 本のショベルは、安い方から $k$ 本とするのが最適になります。
:::
:::spoiler **◎ヒント4**
安い方から $k$ 本のショベルを取り出してソートします。
$(x, y)$ というクーポンを使うのであれば、ソートした列で連続した $x$ 本に対して使うのが最適です。
例えば、$(4, 3), (3, 1)$ というクーポンを使うとき、混ぜて使うと `o` が無料で `x` が有料とすると次のようになります。
`[]` で囲っている部分が2つ目のクーポンの使用対象です。
`oo[oxx]ox`
一方、混ぜずに使うと、 `[oxx]ooox` のようになり2番目と3番目が無料になるよりも4,5番目が無料になる方が得になります。
:::
:::spoiler **◎ヒント5**
どちらのクーポンを安い方に優先的に使うべきかを考えてソートするような方針はうまくいきません。
クーポンを何回でも使えることを利用してDPを行いましょう。
:::
:::spoiler **◎解説**
ヒントに従い、クーポンの数とショベルの数をそれぞれ $k$ 個以下に減らします。
また、クーポンに $(1, 0)$ というクーポンを使わずに購入するのと等価であるものを追加しておくと実装が簡潔になります。
DP配列は `dp[i] := 安い方から i 本購入しているときのコストの最小値` と定義します。
ここで、クーポンを使う順番はわからない状況です。
普通のナップサック問題であれば使うクーポンの番号を外側のループにします。
しかし、今回はクーポンを何回でも使用できることから、内側のループでクーポンを試すことができます。
こうすると、使うクーポン番号の順番が `[1, 2, 3]` という場合も `[2, 3, 1]` という場合についても計算できます。
DPの遷移は次のような形をしているので、累積和を用いて右辺の和を計算するとDP部分の計算量は $O(k^2)$ になります。
$$
dp[i + x_j] = \min(dp[i + x_j], dp[i] + \sum_{k = y_j + 1}^{x_j} a[i + k])$$
:::
### ◎G. Minimum Possible LCM
:::spoiler **◎ヒント1**
最小公倍数は、2つの数の積を最大公約数で割ると計算できます。
:::
:::spoiler **◎ヒント2**
$1 \leq a_i \leq 10^7$ なので、$1 \leq g \leq 10^7$ について、$g$ を約数に持つ $a_i$ を探します。
:::
:::spoiler **◎ヒント3**
$g$ を約数に持つ $a_i$ が3つ以上存在する場合、最小の2つのみ覚えておけばよいです。
:::
:::spoiler **◎ヒント4**
調和級数で計算量を抑えることができます。
:::
:::spoiler **◎解説**
この解説は、公式解説の方針ではありません。
公式解説は $d$ を $a_i$ の約数の最大値としたときに $O(nd)$ ですが、この解説は $a_i$ の最大値を $a$ としたときに $O(a \log a)$ です。
まず、ヒントにあるように各 $g$ について $g$ を約数に持つ $a_i$ で小さい方から2つを求めます。
これは、$a_i = g, 2g, \ldots, kg, \ldots$ となるものがあるか調べていけば調和級数になるため計算量は $O(a \log a)$ で抑えられます。
そしたら、倍数が 2 つ存在する $g$ についてその2つの数の最小公倍数を計算すればよいです。
この方針の疑問点はおそらく次の2つがあります。
- $g$ の倍数なので、求めた2つの数の最大公約数が $g$ とは限らない (より大きい可能性がある)
- 答えになるペアはこの探し方で見つかるのか
答えになるペアの最大公約数が $g'$ であるとき、$g'$ の倍数で小さい方から2つがそのペアでないとします。
すると、ペアの積よりもその2つの積の方が小さくなり、最小公倍数も少なくともその2つの積を $g'$ で割ったもの以下であるため矛盾となります。
よって、前者については本当に最大公約数が $g$ であるペアよりも最小2つによる最小公倍数の方が小さくなるため問題ないです。
後者についても、答えのペアはある $g$ について最小2つになっていることがわかるため問題ありません。
:::
Sign in with Wallet
Connect another wallet