ABC205 Python3解説(A問題~D問題)

こんにちは、こんばんは。現役<font color = "#008000">緑色</font>コーダーの<b>Rute</b>です。
今回は<b>ABC205</b>の<b>A問題</b>から<b>D問題</b>までの解説を行います。

# A問題 - kcal
問題文
$100$mLあたり$A$kcalのエネルギーをもつドリンクがあります。このドリンク$B$mLは何kcalのエネルギーを持つでしょうか？

制約

- $ 0 \leq A,B \leq 1000$
- 入力はすべて整数である

出力
答えを表す数値を出力せよ。
なお、想定解答との絶対誤差または相対誤差が$10^{-6}$以下であれば正解として扱われる。

## 解説
答えは、<font color="#FF00000">$\frac{AB}{100}$</font>です。ただ、そのまま計算しようとすると小数誤差が生じる可能性も否定できないので`Decimal`とよばれる<b>十進表記ライブラリ</b>を使って分数を正確な値で表現しましょう。

```ABC205.py
#Decimalライブラリを読み込んでいる
from decimal import Decimal
A,B = map(int,input().split())
print(Decimal(A * B / 100))

```

# B問題 -  Permutation Check
問題文
$1$以上$N$以下の整数からなる長さ$N$の数列$A = (A_1,A_2,...A_N)$が与えられます。
$A$が$(1,2,...,N)$の並び替えによって得られるかどうかを判定してください。

制約

- $1 \leq N \leq 10^3$
- $1 \leq A_i \leq N$
- 入力はすべて整数

出力
$A$が$(1,2,...,N)$の並び替えによって得られるなら`Yes`.そうでないなら`No`と出力せよ。

## 解法1 ソートする
$A$を昇順にソートしてそれが$(1,2,...,N)$の並び替えと同じかを判定する方法です。
計算量はソートの部分が$O(NlogN)$,入力の部分が$O(N)$なので<font color="#FF0000">$O(NlogN)$</font>で処理を行うことが可能です。

```ABC205B1.py
N = int(input())
A = list(map(int,input().split()))
ls = [i+1 for i in range(N)]
A.sort()
if ls == A:
  print("Yes")
else:
  print("No")
```

<font color="#808080">(これは解答例の一部です。最短で2行で解くことも可能です...)</font>

## 解法2 setの長さで条件分岐
制約が$1 \leq A_i \leq N$であることに着目すると、この問題は以下の問題に言い換えることができます。
<b>「$1$から$N$までの数がすべて存在するか」</b>
すべて存在するかどうかについては$O(N)$で判定することができます。

```ABC205B2.py
N = int(input())
A = list(map(int,input().split()))
#setを用いると種類数を管理することができます
B = len(set(A))
if B == N:
  print("Yes")
else:
  print("No")
```

<font color="#808080">(これは解答例の一部です。最短で2行で解くことも可能です...)</font>

この問題の類題としては以下の問題が挙げられます。
<a href = "https://atcoder.jp/contests/abc164/tasks/abc164_c">ABC164 - C問題「gacha」</a>

# C問題 -  POW
問題文
数$X$を$Y$回掛けたものを「$X$の$Y$乗」といい、$pow(X,Y)$で表します。例えば、$pow(2,3) = 2 × 2 × 2 = 8$です。
$3$つの整数$A,B,C$が与えられるので、$pow(A,C)$と$pow(B,C)$の大小を比較してください。

制約

- 10^9 \leq A,B \leq 10^9
- 1 \leq C \leq 10^9
- 入力はすべて整数

## 解説
愚直に、${10^9}^{10^9}$などを計算しようとすると、<b>多倍数整数の計算</b>をすることになります。
これでは、残念ながら実行時間制限の<b>2秒</b>以内に処理を行うことはできません。

ここで着目するのは、$C$の偶奇と、$A,B$の符号、さらに$A,B$の絶対値$|A|,|B|$の値です。この値に着目して場合分けをすればよいです。

基礎知識としては

- <b>マイナスの値を2以上の偶数回掛けるとプラスになる</b>
- <b>マイナスの値を奇数回掛けるとマイナスになる</b>
- <b>プラスの値は掛ける回数が正であればプラスになる</b>
- <b>ある整数自身を掛ける回数が<b>0</b>である場合、<b>1</b>になる

ということですね。

この知識に基づいて条件分岐を行うと、$O(1)$で解くことが可能です。

回答コードは長いので、AtCoderの提出リンクを直接貼っておくことにします。

https://atcoder.jp/contests/abc205/submissions/23428228

# D問題 Kth Excluded
問題文
長さ$N$の正整数列 $A = (A_1, A_2, \dots, A_N)$ と $Q$個のクエリが与えられます。
$i \, (1 \leq i \leq Q)$ 番目のクエリでは、正整数 $K_i$ が与えられるので、$A_1, A_2, \dots, A_N$ のいずれとも異なる正整数のうち、小さい方から数えて $K_i$ 番目のものを求めてください。</p>
</section>

制約

- $1 \leq N,Q \leq 10^5$
- $1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18} $
- $1 \leq K_i \leq 10^{18}$
- 入力はすべて整数である。

出力
$Q$出力せよ。$i$行目には$i$番目のクエリに対する答えを出力せよ。

## 解説
### 1.最初に思いつきやすい解法</b>
まず、$1$から$10^{18}$までの数字の配列を作成します。これを$B$とします。
$2$番目の制約から任意の$i,j$に対して $A_i \leq A_j$が成り立つので、
各$A_i$を配列から除外していきます。
あとは、各$K_i$に対して`B[K_i-1]`を求めます。

...残念ながら、この解法は<b>間違っています</b>
まず、Pythonにおいて、配列から値を削除する`remove`は配列の長さを$N$とすると、<b>$O(N)$</b>の計算量を要します。これを$N$回行うので<b>$O(N^2)$</b>となります。
配列の長さが$(10^{18})$なので、実行時間制限の3秒以内に間に合いません。
また、そもそもの話、長さ$10^{18}$の配列を作成しようとすると、<b>配列の長さ分の計算量がかかる</b>ので、配列を作成しようとする時点で<b>TLE(実行時間制限超過)</b>となってしまいます。

では、除外せずに、$K_i$番目の値を求める方法とは、どのような方法なのでしょうか？
### 2.ステップ1
まずは、入力例1をもとに、各区間における以下の数を考えます。
(ここでは、配列を1-indexedで考えます)
各$i$ $(1 \leq i \leq N)$について

- $i = 1$のとき、$0$から$A[1]$までの間にある正整数の場合の数
- $2 \leq i \leq N-1$のとき$A[i-1]$から$A[i]$までの間にある正整数の場合の数
- $i = N$のとき、$A[N]$からあとにある正整数の場合の数

この場合の数を並べた数列を$B$とします。

- $B[1] = A[1] - 1$
- $B[2]$から$B[N]$ $= B[i] - B[i-1] - 1$

となります。$B[N+1]$は定義しようとすると$\inf$になるので定義していません。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530417/9349ceef-0a85-2194-ba6e-b5e7621d0204.png)

### 3.ステップ2

次に、$B$に対しての<b>累積和</b>をとります。
<b>累積和</b>というのは、元の数列の0項目からからある項までの総和として定義される数列です。
今回の場合、累積和を$C$とすると、以下のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530417/3b497500-f49d-cdb6-1739-4a56a1ee8104.png)

この累積和を求めることにより、各$C[i]$について
<b>$C[i]$ = 0から$A[i+1]$までの正整数の中で
($A_1,A_2,...A_{i+1}$)に含まれていない正整数の場合の数</b>

というように求めることができました。

### 3.ステップ3

これで前準備は完了です。あとは、
<font color="#FF0000">$A_1, A_2, \dots, A_N$ のいずれとも異なる正整数のうち、小さい方から数えて $K_i$ 番目のものを求める

ということを考えます。

これまでに考えた数列のうち、$C$に着目すると、
各$i$ $(1 \leq i \leq Q)$について
$K_i \leq C[j]$ となる最小のインデックス<b>$j$</b>を求める。すると
<b>$A[j]$から$A[j+1]$の間に小さい方から$K_i$番目の数が含まれる</b>

ということが分かります。

そして、求めたインデックス$j$の値によって、答えは以下のようになることがわかります。
#### 答え
(jは1-indexedではなく0-indexedであることに注意してください)
$j = 0$の場合は0から$A[1]$の間に$K_i$番目の数があります。
この場合の答えは<font color="#FF0000"><b>$K_i$</b></font>になります。
$1 \leq j \leq N-1$の場合$A[j]$から$A[j+1]$までの間に$K_i$番目の数があります。
この場合の答えは<font color="#FF0000"><b>$A[j] + (K_i - A[j])$</b></font>となります。
$j = N$の場合は$K_i$番目の数は$A[N]より大きいことがわかります。
したがって、この場合の答えは<font color="#FF0000"><b>$A[N] + (K_i - A[N])$</b></font>となります。

したがって、最小のインデックスを求めればよいですが、<b>これにも罠があります。</b>

例えば、$Q$回のクエリにおいて$K_i$を受け取って、最小のインデックスを左から<b>線形探索で求める</b>、という解法ではどうでしょう？

一見この解法でも解けそうに見えますが、例えば<b>最小のインデックスがすべて$N$だった場合</b>、最小のインデックスを1個ずつ調べていくのに$O(N)$の計算量が必要で、かつこれを$Q$回繰り返すので計算量は$O(NQ)$となります。


今回の制約についてもう一度着目すると、
制約

- $1 \leq N,Q \leq 10^5$
- <font color="#808080">$1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18} $
- <font color="#808080">$1 \leq K_i \leq 10^{18}$

$N,Q$が$10^5$以下なので、最大で$10^{10}$回程度の計算が必要になります。
高速な言語でも<b>1秒間に$10^8$回程度の計算が精一杯なので</b>、これでは実行時間制限の3秒以内に間に合わず、<b>TLE</b>となってしまいます。

### ステップ4

では、<b>高速に探索</b>するためにはどのような方法を考えればよいでしょうか。

<font color="#808080">これまでに考えた数列のうち、$C$に着目すると、
<font color="#FF0000">各$i$ $(1 \leq i \leq Q)$について
$K_i \leq C[j]$ となる最小のインデックス<b>$j$</b>を求める。</font>すると
<b>$A[j]$から$A[j+1]$の間に小さい方から$K_i$番目の数が含まれる</b>

最小のインデックスを求めるということを考えると、<b>二分探索</b>が探索回数を減らすのに有効なのではないか？と考えられそうです。

したがって、<b>二分探索</b>によって最小のインデックスを求めることにより、

- 毎回の二分探索の計算量が<b>$O(logN)$</b>,
- 二分探索を$Q$回実行するので二分探索部分の計算量が<b>$O(QlogN)$</b>,
- 前処理部分の計算量は$O(N)$

ということから<b>$O(N + QlogN)$</b>の計算量でこの問題を解くことができました。

解答例を示します。

```ABC204D.py
#bisectは二分探索のライブラリです。
import bisect
import copy
N,Q = map(int,input().split())
#端点を追加するために[0]を入力に加えています
A = [0] + list(map(int,input().split()))
B = []
#Bの計算
for i in range(N):
    B.append(A[i+1]-A[i]-1)
#元の配列に影響を与えないようにコピーをしています
C = copy.deepcopy(B)
#累積和の計算部分
for i in range(len(C)):
    if i > 0:
        C[i] += C[i-1]
for i in range(Q):
    K = int(input())
    #K ≦C[j]となる最小のインデックスjを求めています。
    j = bisect.bisect_left(C,K)
    if j == 0:
        print(K)
    elif j == N:
        print(A[-1]+(K-C[-1]))
    else:
        print(A[j]+(K-C[j-1]))
```

以上で、ABC205のA問題~D問題の解説を終了します。
記事に関して質問等がありましたらコメントをお願いします。