# 競プロ講習会第8回 Web資料
## ◎第8回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #8 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Vertual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/6b896678bd0d8c275986a276fdc1ec50ab0c083f
#### ◎公式解説
##### A問題
https://codeforces.com/blog/entry/84248
##### B～G問題
https://codeforces.com/blog/entry/49171
## ◎問題訳(意訳あり注意)
### ◎A. Array Rearrangment
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
長さ $n$ の2つの広義単調増加の整数列 $a,b$ が与えられます。さらに、整数 $x$ が与えられます。
$b$ の要素を好きな順番に並び変えることで、以下の条件を達成することができるでしょうか？
* $a_i + b_i \le x$ を全ての $i\ (1 \le i \le n)$ について満たす。
#### ●入力
1行目に、テストケースの個数 $t\ (1 \le t \le 100)$ が与えられます。
各テストケースについて、1行目に 2つの整数 $n,x\ (1 \le n \le 50,1 \le x \le 1000)$ が与えられます。
2行目に、$n$ 個の整数 $a_1,a_2, ... , a_n\ (1 \le a_1 \le a_2 \le ... \le a_n \le x)$ が与えられます。$a_i$ は、数列 $a$ の $i$ 項目です。
3行目に、$n$ 個の整数 $b_1,b_2, ... , b_n\ (1 \le b_1 \le b_2 \le ... \le b_n \le x)$ が与えられます。$b_i$ は、数列 $b$ の $i$ 項目です。
テストケースの間が空行で区切られることに注意してください(詳しくは入出力例を見てください)
#### ●出力
各テストケースについて、条件を満たすことができるならば `Yes` そうでないならば `No` を出力してください。大文字小文字が異なっても構いません。
#### ●入出力例
##### 入力例1
```
4
3 4
1 2 3
1 1 2
2 6
1 4
2 5
4 4
1 2 3 4
1 2 3 4
1 5
5
5
```
##### 出力例1
```
Yes
Yes
No
No
```
最初のテストケースでは、$b = [1,2,1]$ とすることで、$1+1 \le 4 , 2+2 \le 4 , 3+1 \le 4$ となり条件を満たせます。
2つ目のテストケースでは、 $b = [5,2]$ とすることで条件を満たせます。
3つ目のテストケースでは、どのように並び替えても $a_4 + b_4 > 4$ となってしまいます。
4つ目のテストケースは、そもそも並び替え方が1つしか存在せず、$5+5 > 5$ なので条件を満たしません。
:::
### ◎B. Display Size
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
ある会社では、新しい長方形のディスプレイを発売することにしました。このディスプレイには、ちょうど $n$ 個の画素を使用することにしました。
あなたの仕事は、ディスプレイの縦と横のサイズを決めることです。縦の画素数 $a$ 、横の画素数 $b$ を以下のように決めてください。
* ちょうど $n$ 個のピクセルが含まれる。つまり、$a \times b = n$ である。
* 縦の画素数は横の画素数を超えない。つまり、$a \le b$ である。
* $b-a$ がなるべく小さくなるようにする。
#### ●入力
1行目に、ディスプレイ全体の画素数 $n\ (1 \le n \le 10^6)$ が与えられる。
#### ●出力
2つの整数 $a,b$ を空白区切りで1行に出力してください。
#### ●入出力例
##### 入力例1
```
8
```
##### 出力例1
```
2 4
```
##### 入力例2
```
64
```
##### 出力例2
```
8 8
```
##### 入力例3
```
5
```
##### 出力例3
```
1 5
```
:::
### ◎C. Mammoth's Genome Decoding
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Berland に生息していたマンモスのゲノム解析作業がもう少しで終わりそうです！
残っている作業は、見つかっているDNA鎖 $s$ の認識できなかったヌクレオチドの復元です。
各ヌクレオチドは `A`, `C`, `G`, `T` の英大文字のいずれかで表されてます。認識できなかったヌクレオチドは `?` で表されるので、$s$ は `A`, `C`, `G`, `T`, `?` からなる文字列です。
Berland のマンモスは、DNA鎖に含まれる4種類のヌクレオチドがそれぞれ同じ回数出現するという特徴があります。
あなたは、ゲノムを解読し、認識できなかったヌクレオチドを4種類のヌクレオチドのいずれかで置き換えてください。置き換えた後のDNA鎖に含まれる4種類のヌクレオチドはそれぞれ同じ回数現れます。
#### ●入力
最初の行に、整数 $n (4 \leq n \leq 255)$ としてゲノムの長さが与えられます。
2行目に、長さ $n$ の文字列 $s$ が与えられます。これは復元前のゲノムであって、`A`, `C`, `G`, `T`, `?` からなる文字列です。
#### ●出力
ゲノムを復元し解読することが可能であれば、復元後の文字列を出力してください。複数の可能性があり得る場合はいずれを出力しても構いません。
復元が不可能であれば、3つの等号を `===` のように出力してください。
#### ●入出力例
##### 入力例1
```
8
AG?C??CT
```
##### 出力例1
```
AGACGTCT
```
最初の ? を `A`、2つ目を `G`、3つ目を `T` で置き換えると、復元後の文字列には各種類2回ずつ現れています。
##### 入力例2
```
4
AGCT
```
##### 出力例2
```
AGCT
```
ゲノムが既に復元されていて、各種類1回ずつ現れています。
##### 入力例3
```
6
????G?
```
##### 出力例3
```
===
```
条件を満たすように復元することができません。
##### 入力例4
```
4
AA??
```
##### 出力例4
```
===
```
:::
### ◎D. Servers
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
研究所には $n$ 個のサーバがあります。サーバにはそれぞれ固有のidが $1$ から $n$ まで振られています。
$q$ 個のタスクがやってくることが分かっています。各タスクは3つの値で特徴付けられます。
* $t_i$ : $i$ 番目のタスクがやってくる時刻
* $k_i$ : $i$ 番目のタスク処理に必要なサーバの数
* $d_i$ : $i$ 番目のタスク処理に要す時間
$i$ 番目のタスクを行うためには、$t_i$ 秒の時点で $k_i$ 個の専有されていないサーバーが必要です。
サーバーがタスクを始めた場合、それらのサーバが $d_i$ 秒間専有されます。それゆえ、時刻 $t_i,t_i+1, ... , t_i+d_i-1$ 秒の時点ではサーバが専有状態となり、時刻 $t_i+d_i$ 秒で再び非専有状態になります。
タスクを行うための $k_i$ 個のサーバは、非専有状態のサーバのうち、idが小さい方から $k_i$ 個が選ばれます。
また、$t_i$ 秒時点で、タスクを行うのに十分な数、非専有状態のサーバが無い場合、そのタスクは無視され、以後実行されることはありません。
各タスクが実行されるかを判定し、実行される場合はタスクが専有するサーバのidの総和を求めてください。
#### ●入力
1行目に、2つの正整数 $n,q\ (1 \le n \le 100, 1 \le q \le 10^5)$ が与えられる。
続く $q$ 行に、タスクの情報が与えられる。$i$ 行目には3つの整数 $t_i,k_i,d_i\ (1 \le t_i \le 10^6, 1 \le k_i \le n, 1 \le d_i \le 1000)$ が与えられる。
タスクは、やってくる時刻順に与えられます。また、$i \neq j$ ならば $t_i \neq t_j$ が保証されます。
#### ●出力
$q$ このクエリに答えてください。$i$ 番目のタスクが実行される場合、専有するサーバのidの総和を、実行されない場合は `-1` を出力してください。
#### ●入出力例
##### 入力例1
```
4 3
1 3 2
2 2 1
3 4 3
```
##### 出力例1
```
6
-1
10
```
##### 入力例2
```
3 2
3 2 3
5 1 2
```
##### 出力例2
```
3
3
```
##### 入力例3
```
8 6
1 3 20
4 2 1
6 5 5
10 1 1
15 3 6
21 8 8
```
##### 出力例3
```
6
9
30
-1
15
36
```
:::
### ◎E. Winter Is Coming
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Berland の冬は $n$ 日続きます。それぞれの日について、平均気温を知ることができます。
Vasya はどんな気温でも $k$ 日間まで走れる冬用タイヤを持っています。気温にかかわらず、$k$ 日間使用すると磨り減って使えなくなります。使用するのは連続する $k$ 日でなくても構いません。
冬が来るまで、Vasya は夏用のタイヤを使っています。平均気温が $0$ 度以上であれば、何日間でも使用することができます。しかし、平均気温が$0$ 度未満の日には使うことができません。
Vasya は夏用タイヤと冬用タイヤを、何回でも任意の日の最初に付け替えることができます。
冬の間、Vasya が安全に車を運転するためにタイヤを付け替える回数の最小値を求めてください。冬の最後にどちらのタイヤをつけていても構いません。
#### ●入力
最初の行に、非負整数 $n, k (1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq n)$ が与えられます。これらは、それぞれ冬の日数と冬用タイヤの使用可能日数です。
2行目には、$n$ 個の整数 $t_1, t_2, \ldots, t_n(-20, \leq t_i \leq 20) が与えられます。 $t_i$ は $i$ 日目の平均気温です。
#### ●出力
Vasya が冬を安全に過ごすためにタイヤを付け替える必要がある回数の最小値を出力してください。もしも不可能であれば `-1` を出力してください。
#### ●入出力例
##### 入力例1
```
4 3
-5 20 -3 0
```
##### 出力例1
```
2
```
この例では、1日目の朝に冬用タイヤから夏用タイヤに付け替える必要があります。冬用タイヤは3日間しか使えないので、3日間使用した後、4日目の朝に夏用タイヤに付け替えます。
よって、合計で2回付け替えることになります。
##### 入力例2
```
4 2
-5 20 -3 0
```
##### 出力例2
```
4
```
初日に冬用タイヤに付け替えた後、2日目に夏用タイヤに付け替えます。
そして、3日目の朝に再び冬用タイヤに付け替える必要があります。この例では2日間しか使用できないので、4日目の朝にも付け替える必要があります。
よって、合計で4回付け替えることになります。
##### 入力例3
```
10 6
2 -5 1 3 0 0 -4 -3 1 0
```
##### 出力例3
```
3
```
:::
### ◎F. Comments
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
Polycarpのwebsiteにはコメント欄があります。
それぞれのコメントは、英語のアルファベットの大文字と小文字で構成される1文字以上の文字列です。コメントは木のような構造をしています。すなわち、木の根であるコメント以外は、ちょうど一つの親コメントを持っています。
Polycarpのサイトでは以下のようなフォーマットでコメントを保存しています。
* まず、コメントのテキスト内容が書かれる
* 次に、そのコメントを直接の親として持つコメントの個数が書かれる(すなわち、そのコメントへの直接の返信の個数が書かれる)
* 次に、そのコメントへの返信達が時系列順で書かれる(上と同様のフォーマットで書かれる)
全ての要素は、カンマ`,`で区切られます。同様に、根である2つのコメントの間もカンマで区切られます。
コメントは、例えば以下のような形をしています。
最初のコメントは `hello,2,ok,0,bye,0` と表されます。
2つ目は、 `test,0` と表されます。
3つ目は、 `one,1,two,2,a,0,b,0` と表されます。
結局、コメント欄全体の情報は `hello,2,ok,0,bye,0,test,0,one,1,two,2,a,0,b,0` として保存されていることになります。
さて、このコメント欄の情報を以下で示されるフォーマットに変換してください。
* 1行目に、コメント木の最大の深さ $d$ が書かれている。
* 続く $d$ 行には、書き込み(コメント・返信)が過不足なく全て書かれている。
* $i$ 行目には、$i$ 番目の深さにあるコメントが時系列順、空白区切りで書かれている。
詳しくは、入出力例をご確認ください。
#### ●入力
1行目には、コメント欄の情報が問題文で説明した形式で与えられます。
各書き込みは、1文字以上のアルファベットの大文字と小文字のみで表現され、返信の個数は非負整数で表されます。返信がない場合、`0`と表現されます。
入力全体は $1$以上$10^6$ 以下の長さであることが保証されます。また、与えられる情報は正しいことが保証されます。
#### ●出力
問題文で説明した形式に変換し、出力してください。同じ深さにある書き込みは、入力で与えられた順に出力してください。
#### ●入出力例
##### 入力例1
```
hello,2,ok,0,bye,0,test,0,one,1,two,2,a,0,b,0
```
##### 出力例1
```
3
hello test one
ok bye two
a b
```
##### 入力例2
```
a,5,A,0,a,0,A,0,a,0,A,0
```
##### 出力例2
```
2
a
A a A a A
```
##### 入力例3
```
A,3,B,2,C,0,D,1,E,0,F,1,G,0,H,1,I,1,J,0,K,1,L,0,M,2,N,0,O,1,P,0
```
##### 出力例3
```
4
A K M
B F H L N O
C D G I P
E J
```
:::
### ◎G. Igor and Interesting Numbers
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
Igor は16進数が好きで、16進法表記での正整数について、各文字が $t$ 回以下しか現れないものを *interesting* だと考えています。例えば、 $t=3$ のときは、`13a13322`, `aaa`, `abcdef0123456789` は *interesting* ですが、`aaaa`, `abababab`, `1000000` は *interesting* ではありません。
あなたは、$k$ 番目に小さい *interesting* な整数を 16進法で出力してください。先頭の0は省いて考えます。
#### ●入力
最初の行には、2つの整数 $k, t(1 \leq 2 \cdot 10^9, 1 \leq t \leq 10)$ が与えられます。それぞれ、求めたい整数の情報と、*interesting* な整数に同じ文字が現れる最大回数です。
#### ●出力
Igor にとって *interesting* な整数のうち、$k$ 番目に小さいものを 16進表記で出力してください。
#### ●入出力例
##### 入力例1
```
17 1
```
##### 出力例1
```
12
```
最初の20個の $t=1$ での *interesting* な整数は、`1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15` です。 よって、答えは `12` になります。
##### 入力例2
```
1000000 2
```
##### 出力例2
```
fca2c
```
:::
## ◎ヒント・解説
### ◎A. Array Rearrangment
:::spoiler **◎ヒント0**
書くべきコードは単純ですが、考察が難しい問題を置いてみました。
考えて分からなければ解説を見てしまいましょう。
また、B問題の方が簡単かもしれないので、そちらも見てみてください。
:::
:::spoiler **◎ヒント1**
$a_i+b_i$ の最大値をなるべく小さくしたとき、その値は $x$ 以下か？
と問題を言い換えればよいです。
:::
:::spoiler **◎ヒント2**
$a_i \le a_j,b_i \le b_j$ のとき、
$\mathrm{max}(a_i+b_j,a_i+b_j) \le \mathrm{max}(a_i+b_i,a_j+b_j)$
です。
(やや難しいヒントかも？)
:::
:::spoiler **◎ヒント3**
$i < j$ かつ $b_i < b_j$ となる $i,j$ が**無い**ように、$b$を並び替えましょう。
:::
:::spoiler **◎解説**
結論としては、$b$ は前後反転させればよいです。
$b$ の前後を反転した後、$a_i+b_i \le x$ を全ての $i$ について満たしているかを調べれば答えになります。
理由を説明しましょう。
まず、ヒント2の不等式を見てください。この式自体はよく見れば当たり前だと思います。
さて、$a$ が広義単調増加なので、操作後の数列に $b_i < b_j (i < j)$ となる $i,j$ があった場合、$b_i$ と $b_j$ を交換することで、**最大値は小さくなることはあっても、大きくなることは絶対にない**ことが分かります。
初期状態からこの交換作業を続けていくと、最終的に交換する箇所が無くなりますが、この時 $b$ は**最初の状態から前後反転した状態**になります。これ以上改善はできないので、この時に最大値が最小化された状態になります。
このような、少しずつ解を改善していって、それ以上改善できないところまで操作を続けるというのはヒューリスティック探索の分野でよく使われる考え方です。ヒューリスティック探索について知っている方は、「それって局所最適解にすぎないのでは？」と思うかもしれません。今回の問題では、どのように交換動作を行っても絶対に $b$ の前後反転の状態にたどり着きます。つまり、局所最適解が1つしか無いため、この局所最適解が大域的最適解になります。
:::
:::spoiler **◎実装例(python)**
pythonでの実装においては、空行をinputする必要があることに注意してください。
```python=
t = int(input())
for loop in range(t):
n,x = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b.reverse()
ans = "Yes"
for i in range(n):
if a[i] + b[i] > x:
ans = "No"
print (ans)
# blank line
if loop == t-1:
break
blank = input()
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int loop=0; loop<t; ++loop){
int n,x;
cin >> n >> x;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i<n; ++i) cin >> a[i];
for (int i = 0; i<n; ++i) cin >> b[i];
reverse(b.begin(),b.end());
string ans = "Yes";
for (int i = 0; i<n; ++i){
if (a[i] + b[i] > x){
ans = "No";
}
}
cout << ans << '\n';
}
}
```
:::
### ◎B. Display Size
:::spoiler **◎ヒント1**
$n$ が小さいので、$n$ 回調べてもTLEしません。
:::
:::spoiler **◎解説**
$a$ として考えられる値をすべて調べ上げます。
この処理を一般的には全探索と呼びます。
具体的には、以下のアルゴリズムを実行すればよいです。
1. 変数 ans を非常に大きい数( $n$ 以上の整数)で初期化する。変数 $a,b$ も用意しておく。
2. 以下の処理を、forループを用いて全ての $i\ (1 \le i \le n)$ について実行する。
* $n$ を $i$ で割った余りが0かつ、$i \le n/i$ かつ、$n/i-i < ans$ ならば、$a = i,b = n/i$ と更新し、$ans = n/i-i$ と更新する。
3. 答えとして、$a,b$ を出力する。
:::
::: spoiler **◎実装例(python3)**
```python=
n = int(input())
ans = float("inf")
a,b = None,None
for i in range(1,n+1):
if n % i == 0 and i <= n//i and n//i-i < ans:
a = i
b = n//i
ans = n//i - i
print (a,b)
```
:::
::: spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int ans = INT_MAX;
int a,b;
for (int i = 1; i <= n ; ++i){
if (n%i==0 && i<=n/i && n/i-i < ans){
a = i;
b = n/i;
ans = n/i-i;
}
}
cout << a << " " << b << '\n';
}
```
:::
:::spoiler **◎余談**
ちなみに、$a \times b = n (a \le b)$ の時、$a$ の値は $\sqrt{n}$ 以下です。つまり、この問題は $n \le 10^{12}$ の制約だとしても $a$ としてありうる値の全探索で高速に解くことができます。
:::
### ◎C. Mammoth's Genome Decoding
:::spoiler **◎ヒント1**
解読できる条件を考えましょう。
:::
:::spoiler **◎ヒント2**
長さが4の倍数である必要があります。
:::
:::spoiler **◎ヒント3**
$\frac{n}{4} 回ずつ `A`, `T`, `G`, `C` は使われます。
:::
:::spoiler **◎解説**
$n$ が4の倍数でなければ不可能です。
最初に、`A`, `T`, `G`, `C` が何回 $s$ に出現するかを数えておきます。
もしも、$\frac{n}{4}$ 回よりも多く $s$ に出現していたら不可能です。
そうでなければ、それぞれ $\frac{n}{4}$ 回になるように先頭から `?` を置き換えていけばよいです。
C++ではそのまま string の指定位置を書き換えられますが、Pythonでは不可能なので、一度リストに変換して最後に戻すといった実装方法があります。
:::
:::spoiler **◎実装例(Python)**
```python=
n = int(input())
s = list(input())
if n % 4 != 0:
print("===")
exit()
dna = "ATGC"
cnt = [0 for i in range(4)]
for c in s:
for i in range(4):
if dna[i] == c:
cnt[i] += 1
if cnt[i] > n // 4:
print("===")
exit()
for i in range(n):
if s[i] != '?':
continue
for j in range(4):
if cnt[j] < n // 4:
s[i] = dna[j]
cnt[j] += 1
break
print("".join(s))
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
if (n % 4 != 0) {
cout << "===" << endl;
return 0;
}
string dna = "ATGC";
vector<int> cnt(4, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
if (s[i] == dna[j]) {
cnt[j]++;
if (cnt[j] > n / 4) {
cout << "===" << endl;
return 0;
}
}
}
}
for (int i = 0; i < n; i++) {
if (s[i] != '?') continue;
for (int j = 0; j < 4; j++) {
if (cnt[j] < n / 4) {
s[i] = dna[j];
cnt[j]++;
break;
}
}
}
cout << s << endl;
}
```
:::
### ◎D. Servers
:::spoiler **◎ヒント1**
以下の2種類の出来事が起こると考え、時系列順にソートしましょう。
同一時間に出来事AとBが起こる場合、**Bの方を先に処理する必要があります。**
A. タスクがやってくる。サーバが十分な数空いている場合、サーバを専有して処理が始まる。
B. タスク終了予定時間がやってくる。もしタスクを行っていた場合、専有していたサーバを解放する。
:::
:::spoiler **◎ヒント2**
各サーバが どのタスクに専有されているか/もしくは空いているか を表す配列 $server$ を用意し、管理しましょう。
:::
:::spoiler **◎解説1**
まず、ヒント1で書いたように出来事を時系列順にソートします。
$t,d$ の値域が小さいので、配列を作って入れて行ってもよいですが、ここではより汎用性の高い適切に値をタプルにすることによりソートする方法を紹介します。
今回は、出来事を以下の基準でソートする必要があります。
* 時刻がより小さい方が前に来る
* 時刻が同じ場合、タスクBの方が前に来る
出来事Aの分類番号を `1` 、出来事Bの分類番号を `0` とします。
そして、タスク $i$ について、出来事AとBを以下のような形式で表します。
* 出来事A: ( 時刻$t_i$ , 分類番号`1` , 専有サーバ数$k_i$ , タスクid $i$ )
* 出来事B: ( 時刻$t_i+d_i$ , 分類番号`0` , 専有サーバ数$k_i$ , タスクid $i$ )
以上のような形式で出来事を値の集合(タプル)として表します。このタプルを配列に入れ、昇順ソートすることで出来事を処理したい順番で得ることができます。
:::
:::spoiler **◎解説2**
さて、出来事をソートしたら、実際に処理をしていきます。
まず、以下の配列を用意します。
* サーバの状態(非専有 or どのタスクに専有されているか)を表す長さ $n$ の配列 $server$
* 答えを記録する長さ $q$ の配列 $ans$
そして、以下のように処理を行います。
* 以下の1～3の処理を全ての出来事に対して行う
1. 出来事を1つとってくる
2. 出来事がAの場合、$server$ を前から見て、非専有のサーバが $k_i$ 個以上あるか確かめる。
* ある場合、もう一度 $server$ を前から見て、非専有サーバ $k_i$ 個をタスク $i$ が専有したことにする。この時、サーバidの総和を求め、$ans_i$ に記録する。
* ない場合、$ans_i$ に `-1` を記録する。
3. 出来事がBの場合、$server$ を前から見ていく。$i$ 番目のタスクによって専有されていた場合、非専有状態にする。
:::
:::spoiler **◎実装例(python3)**
```python=
n,q = map(int,input().split())
event = []
for i in range(q):
t,k,d = map(int,input().split())
event.append( (t, 1,k,i) )
event.append( (t+d,0,k,i) )
event.sort()
server = [-1] * n #-1 means free
ans = [None] * q
for loop in range(len(event)):
t,typ,k,i = event[loop]
if typ == 1: #type A
free_cnt = 0
for j in range(n):
if server[j] == -1:
free_cnt += 1
if free_cnt >= k:
idsum = 0
for j in range(n):
if server[j] == -1:
server[j] = i
idsum += j+1
k -= 1
if k == 0:
break
ans[i] = idsum
else:
ans[i] = -1
else: #type B
for j in range(n):
if server[j] == i:
server[j] = -1
print ("\n".join(map(str,ans)))
```
:::
:::spoiler **実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,q;
cin >> n >> q;
vector<vector<int>> event;
for (int i=0; i<q; ++i){
int t,k,d;
cin >> t >> k >> d;
event.push_back({t,1,k,i});
event.push_back({t+d,0,k,i});
}
sort(event.begin(),event.end());
vector<int> server(n,-1); //-1 means free
vector<int> ans(q);
for (int loop=0; loop < event.size(); ++loop){
int t = event[loop][0];
int typ = event[loop][1];
int k = event[loop][2];
int i = event[loop][3];
if (typ == 1){ //type A
int free_cnt = 0;
for (int j=0; j<n ; ++j){
if (server[j] == -1){
free_cnt += 1;
}
}
if (free_cnt >= k){
int idsum = 0;
for (int j=0; j<n; ++j){
if (server[j] == -1){
server[j] = i;
idsum += j+1;
k -= 1;
}
if (k==0) break;
}
ans[i] = idsum;
}else{
ans[i] = -1;
}
}else{
for (int j=0; j<n; ++j){
if (server[j] == i){
server[j] = -1;
}
}
}
}
for (int i=0; i<q ;++i){
cout << ans[i] << '\n';
}
}
```
:::
### ◎E. Winter Is Coming
:::spoiler **◎ヒント1**
毎回、気温が0℃未満になる日の朝に冬用タイヤにして、次の日に戻すということを繰り返すと何回付け替えることになるでしょうか。
:::
:::spoiler **◎ヒント2**
ある寒い日の次の日に夏用タイヤへ戻さないことにすると、使用日数が何日増えて付け替える回数は何回分減るでしょうか。
:::
:::spoiler **◎ヒント3**
最後の寒い日の次の日に戻さなければ1回減り、それ以外の場合は2回減ります。
:::
:::spoiler **◎解説**
まず、気温が0度を下回る日を列挙します。
例えば、そのような日をまとめたリストが次のようになったとします。
$n = 10, k = 6$, `days = [1, 4, 5, 9]`
このとき、毎回付け替えると最大8回付け替えて、4日間使用することになります。
ここで、夏用タイヤに戻さない選択肢を考えると次のようになります。
- 1日目の後に戻さず、4日目まで冬用タイヤを使う
- 使用日数が2日分増え、2回付け替え回数が減る
- 4日目の後に戻さず、5日目まで冬用タイヤを使う
- 使用日数が0日分増え、2回付け替え回数が減る
- 5日目の後に戻さず、9日目まで冬用タイヤを使う
- 使用日数が3日分増え、2回付け替え回数が減る
- 9日目の後に戻さず、10日目(冬の最後まで)冬用タイヤを使う
- 使用日数が1日分増え、1回付け替え回数が減る
後はこの選択肢からいくつかを選び、使用日数が $k$ を超えないように付け替え回数を最大何回分減らせるかを求めればよいです。
普通ならナップサック問題のようにして解くことになりますが、今回は価値に対応する付け替え回数がひとつを除いてすべて $2$ になっているので貪欲法で解けます。
つまり、2回節約できるものについて、使用日数が少ない順に $k$ を超えるまで取っていき、最後に1回節約できるものを取れるなら取れば良いです。
:::
### ◎F. Comments
:::spoiler **◎ヒント1**
コメントの状態は一意に復元できます。
:::
:::spoiler **◎ヒント2**
スタックを活用しましょう。
:::
:::spoiler **◎ヒント3**
スタックに載せるべき情報は、(文字列,まだスタックに積まれていない直接的な子の数) のタプルです。
:::
:::spoiler **◎解説**
まず、入力文字列を (文字列,子の数) のペアとして扱えるように変換しておきます。
$stk$ をスタックとして用意します。スタックには、(文字列, まだスタックに積まれていない直接的な子の数) のタプルを載せます。
(文字列,子の数) のペアを前から見ていきます。
そして、以下のように処理を行います。(以後、1-indexedで統一)
1. 答えを入れる充分な長さの2次元配列 $ans$ を用意しておく。$ans_i$ には、深さ $i$ の書き込みを入れていく。 $ans_i$ は最初空である。
2. 以下の処理を書き込みの総回数分行う。
1. (文字列,子の数) のペアを1つ持ってくる。以後、$p$ と呼ぶことにする。
2. スタックが空でなく、スタックの一番上のタプルの2番目の値が0である限り、そのタプルを取り除き続ける。
3. スタックの一番上のタプルの、2番目の値から1を引く。
4. $p$ をスタックに積む。
5. 現在のスタックの高さを $H$ としたとき、 $ans_H$ の後ろに $p_1$ を追加する。
3. この時点で、$ans$ が答えになっている。1つも文字列が入っていない要素を取り除いて出力すればよい。
:::
:::spoiler **◎余談**
この問題で行った操作は、スタックを用いて行うDFS(深さ優先探索)と全く同じです。
この方法を用いると、再帰を用いずにDFSを書くことができます。
再帰が非常に遅いpythonなどではかなり有用な手法なので覚えておいて損はないと思います。
:::
### ◎G. Igor and Interesting Numbers
:::spoiler **◎ヒント1**
$D$ 桁の *interesting* な整数はいくつあるかを求めましょう。
:::
:::spoiler **◎ヒント2**
$dp[i][j] := 文字 i まで使って、j 桁になる通り数$ のようなDPで求めることができます。
:::
:::spoiler **◎ヒント3**
先頭から決めていきましょう。
ここで、$D$ 桁の *interesting* な整数は先頭に0を許すものと許さないものの2パターンで数えられる必要があります。
:::
:::spoiler **◎解説**
まず、$D$ 桁の *interesting* な整数について、先頭に0があるものを含めるときの数え方を考えます。
これは、$dp[i][j] := 文字 i まで使って、j 桁になる通り数$ で、今できている整数のどこかに挿入していくという考え方で求めることができます。
例えば `2` までで 4桁になっているとき、`3` まで使って6桁である整数の通り数は、`2`までで4桁である整数が `abcd` と表されるとすると、`33abcd`, `3a3bcd`, `ab33cd` のように、3を2つ挿入した形が全てです。
なので、4桁の場合は5箇所に $3$ を2つ挿入するので重複組合せで $_{5}\mathrm{H}_2 = \binom{5 + 2 - 1}{2}$ をかける遷移になります。
先頭の0を許さない場合は、最後に `0` を挿入することにして、$D$桁の整数に `0` を挿入する場合は先頭を除く $D$ 箇所に挿入すると考えればいいです。
後は、この情報を元に貪欲に先頭から決めていきます。
$D$ 桁で、先頭の0を許すものの数を $f_0(D)$、許さないものを $f_1(D)$ とします。
まず、$f_1(d)$ の和が $k$ を超える最初の $D$ を探すと、それが答えの桁数になります。
ここで、$sum = \sum_{i=1}^{D-1} f_1(i)$ とします。
そしたら、1桁目は `1`から `f`、2桁目以降は `0` から `f` で、次のようにその桁の数字を決定していくことで解けます。
1. 今、上から $i$ 桁目とするとき、$i=1$ なら $c = 1$、それ以外なら $c=0$ とする
2. $sum + f_0(D - i) < k$ の間、$sum = sum + f_0(D - i), c = c + 1$ にする
3. $i$ 桁目を $c$ で確定させ、$i = i + 1$ にする
ただし、確定させた文字を使用できる回数は減っていくので、$f_0(D), f_1(D)$ の計算は毎回残りの各文字の使用回数をもとに計算する必要があります。
また、2ステップ目についても、$c$ をもう使用できない場合はその $c$ をスキップします。
:::
Sign in with Wallet
Connect another wallet