# 競プロ講習会第9回 Web資料
## ◎第9回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #9 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Vertual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/5628b62e1d3b9e40f81e3a616a34812a87ec4b46
#### ◎公式解説
##### A〜F問題
https://codeforces.com/blog/entry/56381
## ◎問題訳(意訳あり注意)
### ◎A. Rounding
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Vasya は非負整数 $n$ を持っています。
Vasya は、0で終わる最も近い整数に $n$ を丸めます。
$n$ が既に $0$ で終わる場合は、既に丸めたものだと考えます。
例えば、$n=4722$ であれば答えは $4720$ になり、$n=5$ であれば 答えは $0$ もしくは $10$ になります。$n=5$ の場合はどちらも正解になります。
与えられる $n$ に対して、Vasya が丸めた後の整数としてあり得るものを見つけてください。
#### ●入力
最初の行に、整数 $n (0 \leq n \leq 10^9)$ として Vasya が持っている整数が与えられます。
#### ●出力
$n$ を丸めた結果を出力してください。
いくつかの場合には、答えが複数あることに注意してください。
そのような場合には、どの答えを出力しても正解になります。
#### ●入出力例
##### 入力例1
```
5
```
##### 出力例1
```
0
```
0で終わる整数で最も近いのは $0$ と $10$ で、どちらも正解です。
よって、$0$ と $10$ のどちらを出力しても良いです。
##### 入力例2
```
113
```
##### 出力例2
```
110
```
##### 入力例3
```
1000000000
```
##### 出力例3
```
1000000000
```
##### 入力例4
```
5432359
```
##### 出力例4
```
5432360
```
:::
### ◎B. Proper Nutrition
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Vasyaは $n$ バールのお金を持っています。Ber-Colaは1つ $a$ バールで、Bars-Barは1つ $b$ バールです。
彼は、Ber-Cola と Bars-Bar をそれぞれ0個以上購入することにしました。
適切に購入することで、$n$ 円をすべて使い切ることができますか？
さらに、出来る場合は、それぞれの購入個数を求めてください。
より厳密には、以下のように言い換えられます。
Bar-Colaを $x$ 個、Bars-Barを $y$ 個買うとしたとき、$ax+by=n$ となることはありますか？ そうなることがある場合、その時の $x,y$ を求めてください。
#### ●入力
1行目に、所持金を表す整数 $n\ (1 \le n \le 10^7)$ が与えられます。
2行目に、Ber-Colaの価格 $a\ (1 \le a \le 10^7)$ が与えられます。
3行目に、Bers-Barの価格 $b\ (1 \le b \le 10^7)$ が与えられます。
#### ●出力
もし、Vasyaがちょうど $n$ 円を使い切ることができないのならば、`NO`を出力してください。
そうでない場合、1行目に `YES` を出力し、2行目に2つの整数 $x,y$ を空白区切りで出力してください。ここで、 $x$ は Bar-Colaを買う個数、$y$ は、Bars-Barを買う個数です。
答が複数通り考えられる場合、どれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
7
2
3
```
##### 出力例1
```
YES
2 1
```
2つのBar-Colaと、1つのBars-Barを買うと、 $2 \times 2+1 \times 3 = 7$ で、ちょうど7バールを使い切ることができます。
##### 入力例2
```
100
25
10
```
##### 出力例2
```
YES
0 10
```
答として、$(x,y) = (2,5) , (4,0)$ なども考えられます。
##### 入力例3
```
15
4
8
```
##### 出力例3
```
NO
```
ちょうど15バールを使うことはできません。
##### 入力例4
```
9960594
2551
2557
```
##### 出力例4
```
YES
1951 1949
```
:::
### ◎C. Phone Numbers
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
Vasya は電話帳を持っていて、友達の電話番号が記録されています。彼の友達は、1つ以上の電話番号を持っています。
Vasya は友達の電話番号の情報をまとめることにしました。Vasya の電話帳に書かれたすべての項目が、$n$ 個の文字列として与えられます。 各項目は友達の名前から始まり、その項目に含まれる電話番号の数、その数の電話番号が続きます。同じ項目に異なるいくつかの電話番号が含まれることもあります。
Vasya は、同じ人の電話番号 $a$ と $b$ であって、$a$ が $b$ の接尾辞である ($b$ が $a$ で終わる) とき、$a$ は $b$ の市外局番を省略したものだと考え、$a$ を考慮しません。
Vasya の友達の電話番号情報をまとめたものを出力してください。異なる人物が同じ電話番号をもっていることもあります。 もしも、1人が2つの電話番号 $x, y$ を持っていて、$x$ が $y$ の接尾辞になっているとき、$x$ は出力しないでください。ある友達の電話番号が電話帳に複数回出現するときには、1つとして考えてください。
入出力例を読んで、問題文や出力形式を確認することをおすすめします。
#### ●入力
最初の行に、整数 $n (1 \leq n \leq 20)$ として Vasya の電話帳に含まれる項目数が与えられます。
続く $n$ 行には、問題文で示した形式で記録の詳細が与えられます。
Vasya の友達の名前は空でない文字列で、長さは10を超えず、小文字の英字アルファベットのみからなります。
一つの項目に含まれる電話番号の数は、$1$ 以上 $10$ 以下です。
電話番号には数字のみ含まれ、文字列として表現すると長さは $1$ 以上 $10$ 以下です。電話番号の先頭には $0$ が存在する可能性があります。
#### ●出力
整列された Vasya の友達の電話番号情報を出力してください。
最初の行に、Vasya の電話帳に含まれる友達の数 $m$ を出力してください。
続く $m$ 行は、次のような形式で出力してください。
`名前 電話番号の数(k) 電話番号1 電話番号2 ... 電話番号k`
電話番号はスペースで区切られている必要があり、各記録にはその友達の電話番号をすべて含んでいる必要があります。
項目の順番は自由で、各記録に含まれる電話番号の順番も自由です。
#### ●入出力例
##### 入力例1
```
2
ivan 1 00123
masha 1 00123
```
##### 出力例1
```
2
masha 1 00123
ivan 1 00123
```
##### 入力例2
```
3
karl 2 612 12
petr 1 12
katya 1 612
```
##### 出力例2
```
3
katya 1 612
petr 1 12
karl 1 612
```
##### 入力例3
```
4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789
```
##### 出力例3
```
2
dasha 2 23 789
ivan 4 789 123 2 456
```
:::
### ◎D. Alarm Clock
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
毎朝、Vitalyaは $n$ この目覚まし時計を付けています。 $i$ 番目の目覚まし時計は、$a_i$ の時刻になり始め、ちょうど1分後に鳴り止みます。
Vitalyaは、連続する $m$ 分の間に、$k$ 個以上の目覚まし時計のアラームを聞くと、その時に限り目を覚まします。ここで、アラームを聞くとは、アラームのなり始めから鳴り終わりまでの1分間の音全てを聞くことを指します。対象とする $m$ 分間よりも前に鳴り始めていた目覚まし時計や、対象とする $m$ 分間の後に鳴り止むような目覚まし時計は数えません。
Vitalyaは、とても疲れているので、最後まで目を覚まさないようにしたいです。最低でいくつの目覚まし時計をオフにすればよいでしょうか。なお、現在すべての目覚まし時計はオンになっています。
#### ●入力
1行目に、3つの整数 $n,m,k\ (1 \le k \le n \le 2 \times 10^5, 1 \le m \le 10^6)$ が与えられる。
2行目に、$n$ 個の互いに異なる整数 $a_1,a_2, ... , a_n (1 \le a_i \le 10^6)$ が与えられる。
#### ●出力
1行目に、オフにしなければいけない目覚まし時計の最小数を出力してください。
#### ●入出力例
##### 入力例1
```
3 3 2
3 5 1
```
##### 出力例1
```
1
```
時刻3に鳴り始める目覚まし時計をオフにすればよいです。
##### 入力例2
```
5 10 3
12 8 18 25 1
```
##### 出力例2
```
0
```
10分の間に3つ以上の目覚まし時計の音を聞くことはないため、全てオンのままで問題ありません。
##### 入力例3
```
7 7 2
7 3 4 1 6 5 2
```
##### 出力例3
```
6
```
任意の6個の目覚まし時計を消す必要があります。
##### 入力例4
```
2 2 2
1 3
```
##### 出力例4
```
0
```
:::
### ◎E. Squares and not squares
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
Ann と Borya は、キャンディの山を $n$ 個持っています。$n$ は偶数です。$i$ 番目の山には $a_i$ 個のキャンディがあります。
Ann は平方数 (ある整数の2乗になっている整数) が好きで、Borya は平方数が好きではありません。1回の操作で、ある1つの山を選んでキャンディを1つ増やすか(他の山から持ってくるのではなく、新しいキャンディを追加します)、1つ取り除くことができます(山に1つ以上のキャンディがあるときのみ)。
ちょうど $\frac{n}{2}$ 個の山について、それぞれに含まれるキャンディの数が平方数であり、ちょうど $\frac{n}{2}$ 個の山のそれぞれに含まれるキャンディの数は平方数ではないようにするために必要な操作回数の最小値を求めてください。
#### ●入力
最初の行に、偶数 $n (2 \leq n \leq 200000)$ として、キャンディの山の数が与えられます。
2行目に、整数列 $a_1, a_2, \ldots, a_n(0 \leq a_i \leq 10^9)$ として、それぞれの山に含まれるキャンディの数が与えられます。
#### ●出力
ちょうど $\frac{n}{2}$ 個の山のそれぞれについて、含まれるキャンディの数が平方数になり、残りのちょうど $\frac{n}{2}$ 個の山のそれぞれについて、含まれるキャンディの数が平方数ではないようにするために必要な操作回数の最小値を出力してください。
最初から条件が満たされている場合は $0$ を出力してください。
#### ●入出力例
##### 入力例1
```
4
12 14 30 4
```
##### 出力例1
```
2
```
2回の操作で条件を満たすことができます。2回の操作はどちらも2つ目の山にキャンディを追加することで、山のサイズは 16 になります。
その後、Ann と Borya はそれぞれ、2つのキャンディの個数が平方数である山 (2つ目と4つ目) と、2つのキャンディの個数が平方数でない山 (1つ目と3つ目) を手に入れます。
##### 入力例2
```
6
0 0 0 0 0 0
```
##### 出力例2
```
6
```
3つの山に、2つずつキャンディを追加する必要があります。
##### 入力例3
```
6
120 110 23 34 25 45
```
##### 出力例3
```
3
```
##### 入力例4
```
10
121 56 78 81 45 100 1 0 54 78
```
##### 出力例4
```
0
```
:::
### ◎F. Restoring the Expression
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
$a+b=c$ 形式の文字列は、$a,b,c$ がleading zerosを付けない正整数であり、なおかつ$a$ と $b$ の和が $c$ である時、正しい表現であると言います。
正しい表現である $a+b=c$ 形式の文字列があります。ここから $+$ と $=$ を取り除いた文字列が与えられます。$+$ と $=$ を挿入し、正しい表現である $a+b=c$ 形式の文字列に戻してください。
より具体的には、以下の条件をすべて満たす文字列 $s$ を構築してください。
* $+$,$=$ をそれぞれ1つずつ含み、$+$の方が左にある。
* $+$,$=$ のある位置で文字列を3つに区切ると、いずれも空文字列でない。
* $+$,$=$ を取り除き、残りの文字列を元の順で結合すると、入力と等しい。
* $+$,$=$ のある位置で文字列を3つに区切ったとき、ある文字列について、長さが2以上かつ、最も左の文字が $0$ であることはない。
* 文字列を数式として見たときに、正しい等式である。
この問題においては、答えが少なくとも1つ存在する入力のみが与えられます。また、答えが複数ある場合、いずれを出力しても構いません。
#### ●入力
1行目には、空ではない文字列が与えられます。長さは $10^6$ 以下で、`1,2,3,4,5,6,7,8,9,0` の文字のみを含みます。
#### ●出力
答えを1行に出力してください。
答えは入力文字列に対し $+$,$=$ の2文字を挿入し、ちょうど長さが2だけ増えた文字列となります。(スペースなどは含めないでください。)
#### ●入出力例
##### 入力例1
```
12345168
```
##### 出力例1
```
123+45=168
```
##### 入力例2
```
099
```
##### 出力例2
```
0+9=9
```
##### 入力例3
```
199100
```
##### 出力例3
```
1+99=100
```
##### 入力例4
```
123123123456456456579579579
```
##### 出力例4
```
123123123+456456456=579579579
```
:::
## ◎ヒント・解説
### ◎A. Rounding
:::spoiler **◎ヒント1**
1の位が0の数で、$n$以下で最大のものと$n$以上で最大のものを探しましょう。
:::
:::spoiler **◎ヒント2**
$n$ との差が小さい方を出力すればよいです。
:::
:::spoiler **◎ヒント3**
$n$ の1の位の数は、`n % 10` として10で割った余りで知ることができます。
:::
:::spoiler **◎解説**
$n$ 以下で最大のものは、`l = n - n % 10` とすることで手に入ります。
すると、$n$ より大きくて最小のものは `l + 10` になります。
後は、これらのうち $n$ に近い方を出力すればよいです。$n - l$ と $(l + 10) - n$ を比較しましょう。
:::
:::spoiler **◎実装例(Python)**
```python=
n = int(input())
l = n - n % 10
r = l + 10
if n - l <= r - n:
print(l)
else:
print(r)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int l = n - n % 10;
int r = l + 10;
if (n - l <= r - n) {
cout << l << endl;
} else {
cout << r << endl;
}
}
```
:::
### ◎B. Proper Nutrition
:::spoiler **◎ヒント1**
$10^7$ 回のループは、処理がシンプルならば1秒以内に収まることが多いです。
:::
:::spoiler **◎ヒント2**
$x$ を全探索しましょう。
:::
:::spoiler **◎解説**
ヒント2で述べたとおり、 $x$ を全探索することで解くことができます。
より具体的には、ありうる全ての $x$ について、対応する $y$ が存在するかを調べます。これは、以下のようなアルゴリズムで書くことができます。
* 以下の操作を $x = 0,1,2,...,n$ について調べる
1. $rem = n - x \times a$ とします。
2. $0 \le rem$ かつ、$rem\ \%\ b = 0$ ならば(ここで$\%$は剰余算)、$y = rem / b$ として、`YES` と $x,y$ を出力してプログラムを終了する。
* 全ての $x$ について調べても条件を満たす $x,y$ が見つからない場合、`NO`を出力する。
C++ユーザはオーバフローに気を付けてください。
:::
:::spoiler **◎実装例(python3)**
```python=
import sys
from sys import stdin
n = int(stdin.readline())
a = int(stdin.readline())
b = int(stdin.readline())
for x in range(n+1):
rem = n - a * x
if rem >= 0 and rem % b == 0:
y = rem // b
print ("YES")
print (x,y)
sys.exit()
print ("NO")
```
`sys.stdin.readline()` を`input()` の代わりとして使用しています。こちらの方が高速に動作するので、覚えておくと良いでしょう。
ただし、`sys.stdin.readline()` は入力に改行文字が含まれることに注意してください。
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,a,b;
cin >> n >> a >> b;
for (int x = 0; x <= n ; ++x){
int rem = n - a * x;
if (rem < 0) break;
if (rem % b == 0){
int y = rem / b;
cout << "YES\n" << x << ' ' << y << '\n';
return 0;
}
}
cout << "NO\n";
}
```
$rem$ は単調減少ですので、負になったらループを抜けています。
pythonと同じ方針で解くと、値がオーバーフローしてしまいます。
long long 型を利用すればpythonと同じ方針でも解くことができます。
:::
### ◎C. Phone Numbers
:::spoiler **◎ヒント1(入力の受け取り)**
入力の受け取りが少し難しいですが、各項目はPythonとC++ではそれぞれ次のようにして受け取ることができます。
ただし、電話番号は先頭の 0 を省かないように文字列として扱いましょう。
```python=
record = list(input().split())
name = record[0]
size = int(record[1])
phone = record[2:]
```
```cpp=
int size;
string name;
cin >> name >> size;
vector<string> phone(size);
for (int i = 0; i < size; i++) {
cin >> phone[i];
}
```
:::
:::spoiler **◎ヒント2**
同じ名前の人は同一人物として扱うことに注意しましょう。
:::
:::spoiler **◎ヒント3**
ある名前の人の電話番号を連想配列で管理しましょう。
Pythonでは `dict`、C++では `map` という名前で用意されています。
:::
:::spoiler **◎ヒント4**
ある名前の人の電話番号について、重複や、市外局番を省略しただけと考えられるものを取り除きましょう。
:::
:::spoiler **◎解説**
まず、連想配列を利用してある人の持つ電話番号をすべてまとめます。
その後、接尾辞になっているものや重複を取り除いて出力すればよいです。
重複もある文字列の末尾(すべて)と一致しているとみなせるので、文字数順でソートしてあげれば一緒に処理することができます。ただし、ちょうど一つだけ出力するという条件を考えるのは少し面倒くさいので、set などで重複をあらかじめ取り除くのが楽です。
長さ $k$ の文字列が接尾辞になっているかの判定は、他の文字列について末尾 $k$ 文字と一致するかを確かめればよいです。
詳しくは実装例を見てください。
:::
:::spoiler **◎実装例(Python)**
```python=
n = int(input())
records = dict()
for _ in range(n):
record = list(input().split())
name = record[0]
size = int(record[1])
phone = record[2:]
if name not in records:
records[name] = set()
for num in phone:
records[name].add(num)
print(len(records))
for name, phones in records.items():
ans = []
for num1 in phones:
ok = True
for num2 in phones:
if len(num1) >= len(num2):
continue
if num2[-len(num1):] == num1:
ok = False
if ok:
ans.append(num1)
print(name, len(ans), *ans)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
map<string, set<string>> records;
for (int i = 0; i < n; i++) {
int size;
string name;
cin >> name >> size;
vector<string> phone(size);
for (int i = 0; i < size; i++) {
cin >> phone[i];
records[name].insert(phone[i]);
}
}
cout << records.size() << endl;
for (auto &[name, phones] : records) {
vector<string> ans;
for (auto &num1 : phones) {
bool ok = true;
for (auto &num2 : phones) {
if (num1.size() >= num2.size()) {
continue;
}
if (num2.substr(num2.size() - num1.size()) == num1) {
ok = false;
}
}
if (ok) {
ans.push_back(num1);
}
}
cout << name << " " << ans.size() << " ";
for (auto &num : ans)
cout << num << " ";
cout << endl;
}
}
```
:::
### ◎D. Alarm Clock
:::spoiler **◎ヒント0**
どのように消すのが最適か？ を考える際には第6回のC問題として出した問題が参考になります。
https://codeforces.com/contest/1077/problem/B
:::
:::spoiler **◎ヒント1**
時系列順に見ていったとき、 $m$ 分間に $k$ 個以上の目覚まし時計があった場合、なるべく後に鳴る物を消すのが最適です。
:::
:::spoiler **◎ヒント2**
「 $m$ 分間に $k$ 個以上の目覚まし時計がある 」を 「 $k$ 個の連続する目覚まし時計の起動時間の差が $m$ 未満 」と言い換えましょう。
:::
:::spoiler **◎解説**
結論として、以下のようなアルゴリズムで解くことができます。
* $a$ を昇順ソートしておく。
* まず、空の動的配列(vector,list) $b$ を用意する。
* $i = 1,2, ... , n$ について、以下の操作を行う。
1. $b$ の後ろに $a_i$ をpushする。
2. $b$ の後ろから $j$ 番目の値を $b_{-j}$ と表すとき、$b_{-k}$ が存在し、さらに $b_{-1} - b_{-k} < m$ ならば、$b_{-1}$ をpopする。
* $b$ に入っている目覚まし時計の数が、最大で残せる個数なので、$n - |b|$ が答えである。
一番後ろを消すことが最適であることは具体例を示すと直感的に理解できます。
$k = 4,m = 4$ の時を考えてみます。
$b = [...,10,11,12]$
ここに、13をpushすることを考えましょう。
$b = [...,10,11,12,13]$
この時、$13-10 < m$ なので、条件を満たすには後ろの4要素のうち、どれかを消す必要があります。
ここで、各箇所を消した場合を比較します。
* 一番後ろを消した場合
$b = [...,10,11,12]$
* 後ろから2番目を消した場合
$b = [...,10,11,13]$
* 後ろから3番目を消した場合
$b = [...,10,12,13]$
* 後ろから4番目を消した場合
$b = [...,11,12,13]$
さて、どれ方が望ましいでしょうか…？
次の数字をpushしていくとき、新たに項を消す必要があるのは、$b_{-1} - b_{-k} < m$ を満たしたときです。
つまり、消す数を最小化するためにはこの条件をなるべく満たさない方が良いことになります。
そのため、$b_{-k}$ はなるべく小さい方が良いことが分かります。
さて、上の4つの場合を比較すると、一番後ろの要素を消した場合に$b$ の要素が全ての位置で最小値となることが分かります。
そのため、一番後ろの要素を消したときに、以後のpush操作後における $b_{-k}$ が最小値となります。
このことから、一番後ろの要素を削除するのが最適であることが分かります。
:::
:::spoiler **◎実装例(python3)**
```python=
import sys
from sys import stdin
n,m,k = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))
a.sort()
b = []
for i in range(n):
b.append(a[i])
if len(b) >= k and b[-1]-b[-k] < m:
del b[-1]
print (n - len(b))
```
:::
:::spoiler **◎実装例(C++)**
```python=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m,k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n ; ++i) cin >> a[i];
sort(a.begin(),a.end());
vector<int> b;
for (int i = 0; i < n ; ++i){
b.push_back(a[i]);
if (b.size() >= k && b[b.size()-1]-b[b.size()-k] < m ){
b.pop_back();
}
}
cout << n - b.size() << '\n';
}
```
:::
### ◎E. Squares and not squares
:::spoiler **◎ヒント1**
平方数かどうかをチェックする方法を考えましょう。
:::
:::spoiler **◎ヒント2**
平方数である場合、何回の操作で平方数以外にできるでしょうか。
入出力例を見て確認してみましょう。
:::
:::spoiler **◎ヒント3**
平方数でない場合、何回の操作で平方数にできるでしょうか。
:::
:::spoiler **◎ヒント4**
平方数と平方数以外、どちらのほうが多いでしょうか。
:::
:::spoiler **◎解説**
まず、平方数であるかどうかの確認方法を考えます。
PythonやC++にある `sqrt(math.sqrt)` は、整数にすると2乗しても元の数を超えない最大の整数を返します。
例えば、`sqrt(8) == 2`, `sqrt(9) == 3` です。なので、`sqrt` の結果を2乗したときに一致するかを確かめればよいです。
同時に、$x$ が平方数でなかった場合に平方数にするには、$x$ 以下で最大の平方数と $x$ 以上で最小の平方数の近い方にすることになります。`y = sqrt(x)` とすると、$y^2$ が $x$ 以下で最大の平方数、$(y + 1)^2$ が $x$より大きい最小の平方数になるので、近い方との差が平方数にする最小の操作回数になります。
逆に、平方数ではなくするための最小の操作回数は、基本的に平方数でないときは $0$、平方数であるときは $1$ ですが、入出力例にもある通り、$0$ だけは $2$ 回の操作が必要になります。
これで、各山に含まれるキャンディの個数を平方数にするため/平方数ではなくするために必要な操作回数がそれぞれ求まりました。平方数である山のほうが少ない場合は平方数にするための操作を、平方数でない山の方が少ない場合は平方数でなくするための操作をする必要があります。
今は、平方数である山のほうが少ない場合を考えます。
このとき、既に平方数である山を平方数にするために必要な操作回数を $0$ 回とすると、操作回数の必要数が少ない方から $\frac{n}{2}$ 個の和を取ればそれが答えになります。
例えば、 `[12, 14, 30, 4]` の場合は平方数にするために必要な操作回数はそれぞれ `[3, 2, 5, 0]` になるので、$\frac{n}{2}$ 個の山を平方数にするためには $0 + 2 = 2$ 回が最小の操作回数になります。
既に平方数であるものに必要な操作回数を省き、もともと平方数であった山の数を $s$ として小さい方から $\frac{n}{2} - s$ 個の和を取るとしても良いですが、考えることが少し増えます。
平方数でない山のほうが少ない場合も同様に、平方数でなくするために必要な操作回数が少ない方から $\frac{n}{2}$ 個の和を取れば良いです。
:::
### ◎F. Restoring the Expression
:::spoiler **◎ヒント1**
入力文字列の長さを $n$ とします。
さらに、 $a,b,c$ の長さ(桁数)をそれぞれ、$A,B,C$ とします。
$A+B+C = n$ 以外に $A,B,C$ の満たす条件を考えましょう。
:::
:::spoiler **◎ヒント2**
2数の足し算をした後の桁数は、長いほうに従います。さらに、一番上の桁で繰り上がりがある場合は長さが1増えます。
そのため、$A,B,C$は以下のどちらかを満たします。
* $C = \mathrm{max}(A,B)$
* $C = \mathrm{max}(A,B) + 1$
:::
:::spoiler **◎ヒント3**
$A+B+C = N$ を利用します。
$A$ を決め打つと、$B,C$ は数通りに絞り込むことができます。
:::
:::spoiler **◎ヒント4**
適当な大きな数 $p$ を考えます。
$((a\%p) + (b\%p)) \% p = c\%p$ を満たす場合、高確率で $a+b=c$ であることが言えます。($\%$ は剰余算)
:::
:::spoiler **◎解説**
まず、ヒントでも述べた通り $A$ を決め打つことを考えます。
この時、$B,C$ の組み合わせとしてありうるのは以下の4通りです。
* $B = N-2A , C = A$
* $B = N-2A-1 , C = A+1$
* $B = \lfloor (N-A)/2 \rfloor, C = \lfloor (N-A)/2 \rfloor$
* $B = \lfloor (N-A)/2 \rfloor, C = \lfloor (N-A)/2 \rfloor + 1$
これで大分考慮すべき場合を絞り込めました。$A$ を $1,2,...,n$ と全通り調べたとしても、$4N$ 回だけ調べればよいことになります。
さらに、 $A+B+C = N$ でない場合と $0 \le C-\mathrm{max}(A,B) \le 1$ でない場合を取り除いておくとよいです。
さて、後は足し算をして正しいか調べればよいのですが、桁数が大きいため、全体の計算量は $O(N^2)$ になってしまいます。
そこで、ハッシュ・確率論の考え方を導入します。
適当な大きな数 $p$ を用意します。
$((a\%p) + (b\%p)) \% p = c\%p$ を満たす場合、高確率で $a+b=c$ であることが言えます。($\%$ は剰余算)
この方法では、本当は $a+b \neq c$ なのに、$((a\%p) + (b\%p)) \% p = c\%p$ を満たしてしまうことがあります。すなわち、偽陽性を出すことがあります。
しかし、偽陰性は絶対に出すことがありません。なぜなら、$a+b=c$ ならば $((a\%p) + (b\%p)) \% p = c\%p$ は絶対に満たすからです。
そのため、調べ上げた後、陽性となったものについて、本当に $a+b=c$ なのかをチェックすれば、その中に答えが入っていることになります。
実際は、偽陽性となる確率は単純計算で $1/p$ ですので、$p$ が $10^9$ くらいの大きさならば、偽陽性が出ることもほとんどなく、再チェックしなくても正解になることが多いです。
さて、後は $a\%p , b\%p , c\%p$ を高速に導出できれば解くことができます。
入力文字列を $s$ とします。
$dp_i = s_{(1,2,...,i)} \% p$ (すなわち、$s$ の先頭 $i$ 桁を整数と見たときの値を$p$で割った余り) となるような配列$dp$を構築します。
この配列は、以下のような動的計画法で求めることができます。
* $dp_1 = a_1 \% p$
* $dp_i = ( dp_{i-1} \times 10 + a_i ) \% p$ ($i = 2,3,...,n$ の場合)
この配列を利用すると、$s_{(l,l+1,...,r)} \% p$ は以下のように求められます。
* $s_{(l,l+1,...,r)} \% p = dp_r$ ($l = 1$ の場合)
* $s_{(l,l+1,...,r)} \% p = ( dp_r - dp_{l-1} \times 10^{r-l+1} ) \% p$ ($l > 1$ の場合)
よって、後は10のべき乗を $p$ で割ったものを前計算しておけば、高速に $a\%p , b\%p , c\%p$ を求められることが示せました。
C++の実装においては、意図せぬオーバーフローを考慮してlong long 型の利用を推奨します。
:::
Sign in with Wallet
Connect another wallet