# 競プロ講習会第6回 Web資料
## ◎第6回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #6 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Vertual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/a461e622489b3409a083f1b99c39111e867bae07
#### ◎公式解説
##### A問題
なし
##### B〜G問題
https://codeforces.com/blog/entry/63274
##### H問題
https://codeforces.com/blog/entry/44259
## ◎問題訳(意訳あり注意)
---
### ◎A. A+B (Trial Problem)
:::spoiler **クリックで展開**
TL:1s ML:256MB
#### ●問題
2つの整数 $a,b$ を与えられます。$a+b$ を出力してください。
#### ●入力
1行目には、1つの整数 $t\ (1 \le t \le 10^4)$ が与えられます。これは、 入力にあるテストケースの数です。以後, $t$ 行に渡ってテストケースが与えられます。
それぞれのテストケースでは、2つの整数 $a,b\ (-1000 \le a,b \le 1000)$ が与えられます。
#### ●出力
$t$ 行に渡って出力してください. $i$ 行目には、 $i$ 番目のテストケースの答えを出力し、最後には改行をしてください。
#### ●入出力例
##### 入力例1
```
4
1 5
314 15
-99 99
123 987
```
##### 出力例1
```
6
329
0
1110
```
:::
---
### ◎B. Flog Jumping
:::spoiler **クリックで展開**
TL:1s ML:256MB
#### ●問題
数直線上の座標0の点に蛙がいます。蛙は、以下のようなアルゴリズムに従ってジャンプします。
* 今までに偶数回ジャンプしたことがあれば(すなわち奇数回目のジャンプでは)、現在の座標を $x$ として $x+a$ の座標にジャンプする。
* 今までに奇数回ジャンプしたことがあれば(すなわち偶数回目のジャンプでは)、現在の座標を $x$ として $x-b$ の座標にジャンプする。
蛙がちょうど $k$ 回ジャンプした後にいる座標の値を答えてください。
ただし、蛙は沢山いるので上の問題を $t$ 個解いてください。
#### ●入力
まず、与えられるテストケース(問題)の個数$t\ (1 \le t \le 1000)$ が1行目に与えられます。
続く $t$ 行に、各行に一つのテストケースが $a\ b\ k$ の順で空白区切りで与えられます。$(1 \le a,b,k \le 10^9)$
#### ●出力
$t$ 行に一つずつ整数を出力してください。
$i$ 行目には、$i$番目のテストケースの答えを出力し、改行してください。
#### ●入出力例
##### 入力例1
```
6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999
```
##### 出力例1
```
8
198
-17
2999999997
0
1
```
:::
---
### ◎C. Disturbed People
:::spoiler **クリックで展開**
TL:1s ML:256MB
#### ●問題
$n$ 階建ての家があり、Vovaは毎晩その家を見ています。
家は $n$ 要素の数列 $a_1, a_2, \ldots, a_n$ で表され、$a_i = 1$ であれば $i$ 階は明かりがついていて、 $a_i = 0$ であればついていません。
Vova は、$i (1 < i < n)$ 階に住んでいる人は $a_{i-1} = a_{i+1} = 1$ かつ $a_i = 0$ であれば明かりが邪魔で眠れないだろうと考えました。
そのような階を邪魔されている階と呼ぶことにします。
そこで、最少でいくつの階の明かりを消せば邪魔されている階がなくなるのかを考えることにしました。
#### ●入力
最初の行に、家の階数 $n (3 \leq n \leq 100)$ が与えられます。
2行目に、$n$ 個の整数 $a_1, a_2, \ldots, a_n(a_i \in \{0, 1\})$ が与えられます。$a_i$ は $i$ 階の明かりがついているかどうかを表します。
#### ●出力
1つの整数 $k$ を出力してください。$k$ は $k$ 個の異なる階の明かりを消したら邪魔されている階がなくなるような $k$ の最小値です。
#### ●入出力例
##### 入力例1
```
10
1 1 0 1 1 0 1 0 1 0
```
##### 出力例1
```
2
```
##### 入力例2
```
5
1 1 0 0 0
```
##### 出力例2
```
0
```
##### 入力例3
```
4
1 1 1 1
```
##### 出力例3
```
0
```
最初の例では、2階と7階、もしくは4階と7階の明かりを消すことで、どの階も明かりに邪魔されてない状態になります。
2つ目と3つ目の例については、もともと邪魔されている階はありません。
:::
---
### ◎D. Good Array
:::spoiler **クリックで展開**
TL:1s ML:256MB
#### ●問題
ある配列について、ある要素以外の和がその要素に一致するときにその配列を *good* と呼ぶことにします。例えば、$a = [1, 3, 3, 7]$ は $a_4 = a_1 + a_2 + a_3 = 7$ より *good* です。
あなたは $n$ 要素の配列 $a$ が与えられます。あなたの課題は、$a$ の $j$ 番目の要素を削除すると *good* になるような添字 $j$ をすべて出力することです。そのような添字を *nice* と呼びます。
例えば、$a = [8, 3, 5, 2]$ とすると *nice* な添字は $1$ と $4$ です。
- $a_1$ を取り除くと、$[3, 5, 2]$ のようになり、これは *good* です
- $a_4$ を取り除くと、$[8, 3, 5]$ のようになり、これは *good* です
すべての削除は独立に考えてください。つまり、ある要素を削除した配列について *good* かどうかを確認した後は、削除した要素を戻してください。
#### ●入力
最初の行に、整数 $n(1 \leq n \leq 2 \cdot 10^5)$ が与えられます。配列 $a$ の要素数です。
2行目に、$n$ 個の整数 $a_1, a_2, \ldots, a_n(1 \leq a_i \leq 10^6)$ が与えられます。
#### ●出力
最初の行に1つの整数 $k$ を出力してください。 $k$ は *nice* な添字の数です。
2行目には、$k$ 個の整数 $j_1, j_2, \ldots, j_k$ を任意の順番で出力してください。それぞれ、配列 $a$ の *nice* な添字です。
もし *nice* な添字が $a$ に存在しないときには、1行目に $0$ を出力してください。2行目は空にするか何も出力しないでください。
#### ●入出力例
##### 入力例1
```
5
2 5 1 2 2
```
##### 出力例1
```
3
4 1 5
```
##### 入力例2
```
4
8 3 5 2
```
##### 出力例2
```
2
1 4
```
##### 入力例3
```
5
2 1 2 4 3
```
##### 出力例3
```
0
```
最初の例では、好きな位置の $2$ を削除すると $[5, 1, 2, 2]$ のようになり、 $5 = 1 + 2 + 2$ より *good* になります。
2つ目の例では、 $8$ を削除すると $[3, 5, 2]$ になり、 $5 = 3 + 2$ より *good* です。 $2$ を削除すると $[8, 3, 5]$ になり、 $8 = 3 + 5$ より *good* です。
3つ目の例では、与えられた配列をちょうど1つの要素を削除するだけで *good* にすることはできません。
:::
---
### ◎E. Cutting Out
:::spoiler **クリックで展開**
TL:3s ML:256MB
#### ●問題
$n$ 個の整数からなる配列 $s$ が与えられます。
あなたは長さ $k$ の任意の配列 $t$ として、$s$ から $t$ のコピーを取り除く操作を最も多く行える配列を探す必要があります。
$t$ のコピーを取り除く操作では、$t$ の各要素 $t_i$ について、$t_i$ を $s$ から探し出し、それを $s$ から削除します。ある $t_i$ について、$s$ に含まれていない場合には $t$ のコピーを更に $s$ から取り除くことはできません。どちらの配列も、重複する要素が存在する可能性があります。
例えば、 $s = [1, 2, 3, 2, 4, 3, 1], k = 3$ としたとき、1つの答えとしては $t = [1, 2, 3]$ があります。この配列 $t$ は $2$ 回取り除くことができます。
- $t$ の最初のコピーを取り除くとき、$[1, (2), 3, 2, 4, (3), (1)]$ 括弧で囲んだ要素を使うことができます。これらの要素を削除した後、$s$ は $[1, 3, 2, 4]$ のようになります。
- 2つ目のコピーを取り除くときは、$[(1), (3), (2), 4]$ を使うことができます。2つ目のコピーを取り除いた後の $s$ は $[4]$ のようになります。
あなたの課題は、最も多くの回数 $s$ から $t$ のコピーを取り除くことができるような $t$ を見つけることです。複数の答えがある場合、どの答えを出力しても問題ありません。
#### ●入力
最初の行に、2つの整数 $n, k (1 \leq k \leq n \leq 2 \cdot 10^5)$ が与えられます。それぞれ、配列 $s$ の要素数と配列 $t$ の要素数です。
2行目に、$n$ 個の整数 $s_1, s_2, \ldots, s_n(1 \leq s_i \leq 2 \cdot 10^5)$ が与えられます。
#### ●出力
配列 $t$ の要素である $k$ 個の整数を出力してください。このとき、$t$ は $s$ からコピーを取り除く操作を最も多く行える配列です。複数の答えがあるときは、その中の任意の配列を出力していいです。 また、 $t$ は重複する要素を含むことができ、すべての要素は $1 \leq t_i \leq 2 \cdot 10^5$ を満たしている必要があります。
#### ●入出力例
##### 入力例1
```
7 3
1 2 3 2 4 3 1
```
##### 出力例1
```
1 2 3
```
##### 入力例2
```
10 4
1 3 1 3 10 3 7 7 12 3
```
##### 出力例2
```
7 3 1 3
```
##### 入力例3
```
15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1
```
##### 出力例3
```
1 1
```
1つ目の例は、問題文中のものと同じです
2つ目の例では、$[7, 3, 1, 3]$ とその並び替えが唯一の解です。 それ以外の配列を $t$ とすると、2回以上コピーを取り除けないことを示すことができます。
3つ目の例では、$t$ のコピーを $5$ 回取り除くことができます。
:::
---
### ◎F. Thematic Contests
:::spoiler **クリックで展開**
TL:1s ML:256MB
#### ●問題
Polycarpは、$n$ 個の競プロの問題を作りました。$i$ 番目の問題のトピックは $a_i$ です。いくつかの問題のトピックが等しいこともありえます。
Polycarpは、これらの問題を使用して何回かトピック別コンテストを開こうと思っています。1回のコンテストに含まれるの問題は全て同じトピックである必要があります。また、同じトピックのコンテストは1回しか開けません。
更に、Polycarpは以下のような方針でコンテストを開くことにしました。
* コンテストの問題数は、直前に行ったコンテストの問題数のちょうど2倍にする。(初回の問題数は任意)
* 全てのコンテストの問題数の合計が最大になるようにする。(コンテスト回数は最大化する必要がない)
この方針に従ったとき、全てのコンテストの問題数の合計はいくつになるか答えてください。
#### ●入力
1行目には問題数 $n\ (1 \le n \le 2 \times 10^5)$ が与えられる。
2行目に、 $n$ 個の整数 $a_1,a_2,\ ...\ , a_n(1 \le a_i \le 10^9)$ が与えられる。$a_i$ は $i$ 問目のトピックである。
#### ●出力
答えを1行に出力し、改行してください。
#### ●入出力例
##### 入力例1
```
18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10
```
##### 出力例1
```
14
```
##### 入力例2
```
10
6 6 6 3 6 1000000000 3 3 6 6
```
##### 出力例2
```
9
```
##### 入力例3
```
3
1337 1337 1337
```
##### 出力例3
```
3
```
:::
---
### ◎G1&G2. Pictures with Kittens
:::spoiler **クリックで展開**
G1問題 TL:2s ML:256MB
G2問題 TL:2.5s ML:512MB
#### ●問題
`easy(G1)とhard(G2)の違いは、制約のみです。`
Vovaは子猫の写真が好きです。ニュース欄には $n$ 枚の子猫の写真が載っていて、上から $i$ 番目の写真の美しさは $a_i$ です。
彼は、この中から以下の条件を守りつつ、ちょうど $x$ 枚の写真を引用しようと思いました。
* ニュース欄の任意の連続する $k$ 枚の写真を取ってくると、その内少なくとも1枚は引用されている。
例えば、 $k = 1$ ならばVovaは全ての写真を引用する必要があります。もし、$k = 2$ ならば写真を引用せずスキップしても構いませんが、連続する2枚の写真の両方をスキップすることはできません。
この時、引用した写真の美しさの合計値として考えられる最大値を求めてください。ただし、そもそも条件を満たす引用方法がない場合はその旨を報告してください。
#### ●入力
1行目には、3つの整数 $n\ k\ x$がこの順で空白区切りで与えられます。
G1問題では、 $1 \le k,x \le n \le 200$ が、
G2問題では、 $1 \le k,x \le n \le 5000$ が保証されます。
2行目には、$n$ 個の整数 $a_1,a_2,\ ...\ ,a_n(1 \le a_i \le 10^9)$ が与えられます。
#### ●出力
もし、条件を満たす引用方法がない場合、$-1$ を出力してください。
そうでない場合、答えを1行に出力してください。
最後に改行してください。
#### ●入出力例
##### 入力例1
```
5 2 3
5 1 3 10 1
```
##### 出力例1
```
18
```
##### 入力例2
```
6 1 5
10 30 30 70 10 10
```
##### 出力例2
```
-1
```
##### 入力例3
```
4 3 1
1 100 1 1
```
##### 出力例3
```
100
```
:::
---
### ◎H. Bear and Bowling 4
:::spoiler **クリックで展開**
TL:2s ML:256MB
#### ●問題
Limak は年老いたヒグマです。彼はよく友達とボウリングをします。今日はとても調子が良かったので、自分の記録を更新しようと思いました。
ロールをする(ボールを転がす)ことでスコアを手に入れることができます。スコアは整数 (負になることもある) で表されます。$i$ 回目のロールによるスコアは $i$ 倍されて、最終的に合計されます。 よって、 $k$ 回のロールによるスコアが $s_1, s_2, \ldots, s_k$ であれば合計スコアは $\sum_{i=1}^k i\cdot s_i$ になります。一度もロールしなかったときのスコアは $0$ です。
Limak は $n$ 回のロールを行い、$i$ 番目のロールでスコア $a_i$ を手に入れました。彼は、面白い思いつきで合計スコアを最大化することにしました。最初のいくつかのロールはウォーミングアップだと言い、最後のいくつかのロールは注目しない事ができます。
正式に書くと、彼は $a_1, a_2, \ldots, a_n$ の任意の prefix と任意の suffix をなかったことにできます。すべてのロールをなかったことにすることも、どのロールも取り消さないこともできます。
合計スコアは、取り消さないロールしか最初からなかったかのように計算されます。つまり、取り消されなかった最初のロールによるスコアは $1$ 倍され、次のスコアは $2$ 倍され、と続いていき、最後の取り消されなかったロールまで続きます。
Limak が取れる最大のスコアを求めてください。
#### ●入力
最初の行に、整数 $n (1 \leq n \leq 2 \cdot 10^5)$ として Limak がロールを行った回数が与えられます。
2行目には、$n$ 個の整数 $a_1, a_2, \ldots, a_n (|a_i| \leq 10^7)$ が与えられます。それぞれ、Limak のロールに対するスコアです。
#### ●出力
ロールを取り消した後の合計スコアとしてありえるものの最大値を出力してください。
#### ●入出力例
##### 入力例1
```
6
5 -1000 1 -3 7 -8
```
##### 出力例1
```
16
```
##### 入力例2
```
5
1000 1000 1001 1000 1000
```
##### 出力例2
```
15003
```
##### 入力例3
```
3
-60 -70 -80
```
##### 出力例3
```
0
```
最初の例では、Limakは最初の2つのロールと最後の1つのロールを取り消すのが最適です。残ったロールのスコアは $1, -3, 7$ で、合計スコアは $1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 = 1 - 6 + 21 = 16$ になります。
:::
---
## ◎ヒント・解説
### ◎ヒント・解説に関しての諸注意
:::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. A+B (Trial Problem)
:::spoiler **◎プログラミング経験が一切無い方へ**
プログラミング経験が無い方は、この問題の解説を読んでも理解するのが難しいかもしれません。
逆に、少しでもコードを書いたことがある方でしたら、一つ下の「テストケースとは？」の節から見て頂ければ理解できると思います。
プログラミング経験が無い方はまず、atcoder.jp(https://atcoder.jp/home) に登録しAPG4b(https://atcoder.jp/contests/APG4b) に取り組んでみてください。
取り組んでいる間にわからないことなどありましたら、質問は受け付けますのでお気軽にどうぞ。
1章の終わりまで取り組んだら、この問題に取り組んでみてください。
:::
:::spoiler **◎テストケースとは？**
Codeforcesでは、多くの問題が「複数テストケース」のスタイルを取っています。
「複数テストケース」では、問題文の問題を複数個解いてからプログラムを終了することが要求されます。
多くの場合は、入力の1行目に解くべき問題の個数 $t$ が与えられます。その後 $t$ 個の問題を解いてからプログラムを終了しなくてはいけません。
より具体的には、以下の「何をすればいいか？」で説明します。
:::
:::spoiler **◎何をすればいいか？**
まず、問題の入出力例1の部分を見てみましょう。(以下にコピーしてあります)
##### 入力例1
```
4
1 5
314 15
-99 99
123 987
```
##### 出力例1
```
6
329
0
1110
```
入力例の1行目に書かれている「4」はこの入出力例におけるテストケースの数です。
そして2～5行目には、4つの問題の入力が書かれています。
出力例の4つの数は、この4つの問題の答えに対応しています。
(※例えば、入力例の2行目 $1\ 5$ は、$1 + 5 = 6$ であり、出力例の1行目の $6$ と対応しています。)
「入力例1のような入力を受け取ったら、出力例1のような出力をするプログラムを書け」というのが本問題で求められていることです。
:::
:::spoiler **◎入出力の受け取り方**
入力は「標準入力ストリーム」から受け取り、出力は「標準出力ストリーム」に行います。
各言語で入出力の方法は大きく異なるので、以上のワードを含めて検索すると良いと思います。
:::
:::spoiler **◎解説**
二つの整数を受け取り、出力するだけの問題です。
競技プログラミングを一切やったことがない方々もいると思いますので、今回はセットに含めることにしました。
注意として、各テストケースの答えは改行区切りで出力し、出力の一番最後にも改行を入れる必要があります。
以下、実装を紹介します。
:::
:::spoiler **◎pythonの実装例**
```python=
#python
t = int(input())
for _ in range(t):
a,b = map(int,input().split())
print (a+b)
```
:::
:::spoiler **◎C++の実装例**
```cpp=
//C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int loop = 0 ; loop < t ; ++loop){
int a,b;
cin >> a >> b;
cout << a+b << '\n';
}
}
```
:::
---
### ◎B. Flog Jumping
:::spoiler **◎ヒント1**
愚直に移動をシミュレーションするとTLEします。
:::
:::spoiler **◎ヒント2**
答えを数式で表しましょう。
:::
:::spoiler **◎ヒント3**
移動回数の偶奇によって分けるのもありです。
:::
:::spoiler **◎解説**
$a,-b$ の移動がそれぞれ何回起こるかを計算し、合計を出せばよいです。
このように考えると、答えは $a \lceil k/2 \rceil - b \lfloor k/2 \rfloor$ であることが分かります。
いくつか$k$を代入してみると、正しいことがわかると思います。
ただし、
$\lceil X \rceil$ は $X$ 以上の最小の整数であり、
(例: $\lceil 4 \rceil = 4$、$\lceil 4.5 \rceil = 5$)
$\lfloor X \rfloor$ は $X$ 以下の最大の整数です。
(例: $\lfloor 4 \rfloor = 4$、$\lfloor 4.5 \rfloor = 4$)
実装に関して、多くの言語で整数 $x,y$ の割り算 $x/y$ は $\lfloor x/y \rfloor$ で定義されています。ceil関数が用意されている言語もありますが、以下の式を用いることで簡単にceilを計算することができます。
$x,y$ が共に正の整数の時、
$\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$
以下のコード例においても、この言いかえを用いています。
:::
:::spoiler **◎pythonでの実装例**
```python=
tt = int(input())
for qidx in range(tt):
a,b,k = map(int,input().split())
ans = a*( (k+1)//2 ) - b*( k//2 )
print (ans)
```
:::
:::spoiler **◎C++での実装例**
int型だとオーバーフローするのでlong long型を使用しています。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
for (int qidx = 0 ; qidx < tt ; qidx++){
long long a,b,k;
cin >> a >> b >> k;
long long ans = a*( (k+1)/2 ) - b*( k/2 );
cout << ans << '\n';
}
}
```
:::
---
### ◎C. Disturbed People
:::spoiler **◎ヒント1**
消す必要があるのは、もともと邪魔されている階に隣接しているどちらかだけです。
:::
:::spoiler **◎ヒント2**
`10101` のようになっていると、中心の階だけ消せば良いです。
:::
:::spoiler **◎ヒント3**
先頭から見ていって、邪魔されている階があるとき、前と後ろのどちらを消すべきでしょうか。
:::
:::spoiler **◎解説**
$i = 1$ から $n-1$ までそれぞれの階を見ていって、邪魔されている階があればどちらかをその場で消して解決した後に進んでいく方法を考えます。
このとき、ある階 $i$ が邪魔されていれば、手前の階 $i - 1$ の電気を消してもその更に前の階 $i - 2$ が邪魔されている状態から直ることはありません。仮に最初邪魔されていたら $i - 2$ を先に見ていて解決しているはずだからです。
一方、$i+1$ の電気を消すと、$i + 2$ はまだ見ていないため邪魔されている可能性があるので、同時に2つの階を解決することができることがあります。
よって、先頭から見ていき、 $i$ 階が邪魔されていれば $i+1$ 階の電気を消すということを繰り返せば良いです。
:::
---
### ◎D. Good Array
:::spoiler **◎ヒント1**
すべての要素の和を計算して使うことを考えます。
:::
:::spoiler **◎ヒント2**
ある配列が *good* であるとき、どのような要素があるでしょうか。
:::
:::spoiler **◎ヒント3**
ある値が何回現れるかを数えておきましょう。
:::
:::spoiler **◎解説**
ある配列の総和を $sum$ としたとき、$\frac{sum}{2}$ が配列に含まれていれば *good* な配列です。
よって、ある要素 $a_i$ を取り除くことで *good* になるかどうかは、取り除いた後の配列に $\frac{sum - a_i}{2}$ が存在するかを調べればいいです。
ただし、取り除いた値が $\frac{sum - a_i}{2}$ だった場合は、元の配列に2回以上登場している必要が有ることに注意してください。
:::
---
### ◎E. Cutting Out
:::spoiler **◎ヒント1**
$t$ が与えられたとき、何回コピーを削除できるかはどのように計算できるでしょうか。
:::
:::spoiler **◎ヒント2**
答えとなる最大で何回コピーを削除できるかを二分探索で求めます。
:::
:::spoiler **◎ヒント3**
ある値が何回現れるかを数えておきましょう。
:::
:::spoiler **◎解説**
ある値 $i$ が $s$ に現れる回数を $cnt_i$ とします。
このとき、コピーを取り除くことができる回数が $x$ になる $t$ が存在するかどうかを判定できれば二分探索で解くことができます。
ここで、$x$ を決めたときに $t$ に $i$ を含むことができる個数は $\lfloor \frac{cnt_i}{x} \rfloor$ になります。
すべての $i$ について、この和を求めて $k$ 以上であれば存在するということになります。
最大回数が求まったら、それを $x$ として $t$ の要素が $k$ 個になるまで $i$ を $\lfloor \frac{cnt_i}{x} \rfloor$ 回追加するといいです。
:::
---
### ◎F. Thematic Contests
:::spoiler **◎ヒント1**
まず、トピックの番号ごとにいくつあるのかを数えましょう。
トピックの番号の情報は不要なので、数えた後は捨てていいです。
:::
:::spoiler **◎ヒント2**
個数が少ない順にトピックを並べましょう。
:::
:::spoiler **◎ヒント3**
動的計画法で解くことができます。
:::
:::spoiler **◎ヒント4**
貪欲法でも解くことができます。
:::
:::spoiler **◎ヒント5**
いずれの場合も問題数が$n$問しかないことを利用します。
:::
:::spoiler **◎解説1**
まず、各トピックごとにいくつあるかを数え、少ないほうから並べます。
これは、pythonの辞書型や、C++のmapを利用することで実現できます。
1問以上ある各トピックを問題数の少ない順に並べたとき、その問題数が
$c_1,c_2,c_3,...,c_k$ 個あるとします。
以下、動的計画法と貪欲法の2つのアプローチを紹介します。
:::
:::spoiler **◎解説2**
この節では、動的計画法のアプローチを紹介します。
まず、$c$を前から取ってコンテストを構成していく場合を考え、以下のようにdpを定義します。
$\mathrm{dp}[i] =$ 最後に構成したコンテストが $i$ 問の時、今までに構成したコンテストの総問題数
推移に関しては、以下の2通りを考えればよいです。
1. $1 \le x \le c_i$ を満たす各整数 $x$ について、$x$ 問のコンテストを、最初のコンテストとして作成する。
2. $1 \le y \le c_i$ を満たす各偶数 $y$ について、直前に構成したコンテストが $y/2$ 問の状態に、 $y$ 問のコンテストを付けたす。
2→1の順に処理し、さらに2ではdp配列を後ろから更新していくことでdp配列1本で以上の推移を行うことができます。
計算量は $O(\sum_{i=1}^{k} c_i)$ すなわち、$O(n)$ です。
言葉での説明には限界がありますので、以下に解答例を用意しました。
:::
:::spoiler **◎解説2の実装例(python3)**
```python=
import sys
from sys import stdin
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
dic = {}
for i in a:
if i not in dic:
dic[i] = 1
else:
dic[i] += 1
c = []
for i in dic:
c.append( dic[i] )
c.sort()
dp = [float("-inf")] * (n+1)
for ci in c:
for j in range(ci,-1,-1): #type2
if j % 2 == 0:
dp[j] = max(dp[j] , dp[j//2] + j)
for j in range(ci,-1,-1): #type1
dp[j] = max(dp[j] , j)
ans = max(dp)
print (ans)
```
:::
:::spoiler **◎解説3**
この節では、貪欲法のアプローチを紹介します。
dpに慣れていない方はこちらの方が簡単かもしれません。
この方針では、最後のコンテストの問題数を決め打ち全探索します。
最後のコンテストの問題数を固定すると、問題数の多いトピックを問題数が多いコンテストに割り当てるのが最適なので、$c$の後ろから貪欲にコンテストを作れるだけ作れば良いことが分かります。
取るコンテスト数は $O(\mathrm{log}n)$ なので、全体で $O(n\mathrm{log}n)$ で問題を解くことができます。
:::
:::spoiler **◎解説3の実装例(python3)**
```python=
import sys
from sys import stdin
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
dic = {}
for i in a:
if i not in dic:
dic[i] = 1
else:
dic[i] += 1
c = []
for i in dic:
c.append( dic[i] )
c.sort()
ans = 0
for last in range(1,n+1):
allprob = 0
nowprob = last
for i in range(len(c)-1,-1,-1):
if c[i] >= nowprob:
allprob += nowprob
else:
break
if nowprob % 2 != 0:
break
nowprob //= 2
ans = max(ans , allprob)
print (ans)
```
:::
---
### ◎G1&G2. Pictures with Kittens
:::spoiler **◎ヒント1(easy)**
動的計画法を使って解くことができます。
:::
:::spoiler **◎ヒント2(hard)**
easyを高速化して、 $O(nx)$ にしましょう。
※logを付けるとやや厳しい可能性があります。
:::
:::spoiler **◎解説1(easy)**
写真を前から見ていき、dp推移することを考えます。
dpを以下のように定義します。
$\mathrm{dp}[lx][li] =$ $li$枚目まで採用するかを決め、$lx$枚写真を採用したときの、美しさの最大値
※ $li,lx$ の順番が一般と逆なのはhardのためです。
計算量は $O(nkx)$ となります。
:::
:::spoiler **◎解説2(hard)**
$k$ に対して以上のdpの高速化を試みます。
$\mathrm{dp}[lx][li] = max( \mathrm{dp}[lx-1][li-k],\mathrm{dp}[lx-1][li-k+1],\ ...\ ,\mathrm{dp}[lx-1][li-1]) + a[li]$
です。
そのため、区間最大値を高速に求めることができれば高速な推移が可能となります。
セグメントツリーを使うことで高速化できますが、制約が大きいため、定数倍がやや厳しいです。
今回は最小値を求めたい区間の長さが$k$で一定なので、スライド最小値(最大値)と呼ばれるアルゴリズムを使用することができます。
スライド最小値:
https://phwinx.hatenablog.com/entry/2018/11/17/042646
すると、計算量は $O(nx)$ となります。
:::
---
### ◎H. Bear and Bowling 4
:::spoiler **◎ヒント1**
ある区間が残ったときの合計スコアを効率的に計算する方法を考えましょう。
:::
:::spoiler **◎ヒント2**
Convex Hull Trickというテクニックを扱えるデータ構造があると、次のようなことが$O(\log N)$ でできます。
1. $a_ix + b_i$ という形の直線を追加する
2. $x$ を与えると、今まで追加した直線のうち $x$ で最大(最小) になるものを見つける
:::
:::spoiler **◎ヒント3**
次のような2つの累積和を使います。
$$
S_1(k) := \sum_{i=1}^{k} a_i \\
S_2(k) := \sum_{i=1}^{k} i \cdot a_i
$$
:::
:::spoiler **◎解説**
ある区間 $(l, r]$ が取り消されなかったときの合計スコアは、ヒント3で導入した累積和を使うと
$$
\sum_{i = l + 1}^r (i - l) \cdot a_i = (S_2(r) - S_2(l)) - l \cdot (S_1(r) - S_1(l))
$$
と表すことができます。ここで、$l$ に依存している部分と $r$ に依存している部分を分けると
$$
(S_2(r) - S_2(l)) - l \cdot (S_1(r) - S_1(l)) = (-S_2(l) + l \cdot S_1(l)) - l \cdot S_1(r) + S_2(r)
$$
となり、$l \cdot S_1(r)$ のみ $l$ と $r$ の両方に依存しています。ここで、$-l \cdot x + (-S_2(l) + l \cdot S_1(l))$ という直線を考えると、$x$ に $S_1(r)$ を代入したときに最大になる直線での値に $S_2(r)$ を足せばいいことがわかります。
これは CHT で実現できるので、$O(N \log N)$ で解けます。
:::
---
Sign in with Wallet
Connect another wallet