【AtCoder】PythonでABC248のA, B, C, D, Eを解く

自分がコンテストでやった考察と実装を書いてみます.

# 目次

* [A問題 『Lacked Number』](https://qiita.com/yassu/items/ae83817838c2c25e5a1d#a%E5%95%8F%E9%A1%8C-lacked-number)
* [B問題 『Slimes』](https://qiita.com/yassu/items/ae83817838c2c25e5a1d#b%E5%95%8F%E9%A1%8C-slimes)
* [C問題 『Dice Sum』](https://qiita.com/yassu/items/ae83817838c2c25e5a1d#c%E5%95%8F%E9%A1%8C-dice-sum)
* [D問題 『Range Count Query』](https://qiita.com/yassu/items/ae83817838c2c25e5a1d#d%E5%95%8F%E9%A1%8C-range-count-query)
* [E問題 『K-colinear Line』](https://qiita.com/yassu/items/ae83817838c2c25e5a1d#e%E5%95%8F%E9%A1%8C-k-colinear-line)

## A問題 『Lacked Number』

問題ページ: [A - Lacked Number](https://atcoder.jp/contests/abc248/tasks/abc248_a)
Difficulty: <font color="#808080"> 22 </font>

### 考察

与えられた数字を全て `set` に持っておいて, `set(range(10))` から引くと, `set(range(10))` に含まれるが, もともとの数字に含まれない要素が取得できます.
任意の値の取得は `s.pop()` で取得できるので, それを出力すれば良いです.

### 実装

``` python
#!/usr/bin/env pypy3

s = set(map(int, list(input())))
s = set(range(10)) - s
print(s.pop())
```

## B問題 『Slimes』

問題ページ: [B - Slimes](https://atcoder.jp/contests/abc248/tasks/abc248_b)
Difficulty: <font color="#808080"> 41 </font>

### 考察

一回ごとにスライムの数を `B` 倍するのをシミュレーションすればいいです.
`A=1, B=10^9, C=2` の時に答えが最大になります. その時の答えは 
``` math
\lceil \log_2 10^9\rceil = 30
```
なので, 間に合います.
### 実装

``` python
#!/usr/bin/env pypy3

a, b, k = map(int, input().split())
res = 0
while a < b:
    a *= k
    res += 1

print(res)
```

## C問題 『Dice Sum』

問題ページ: [C - Dice Sum](https://atcoder.jp/contests/abc248/tasks/abc248_c)
Difficulty: <font color="#804000"> 787 </font>

### 考察

典型的なdp問題です.
`dp[i][j]` を長さ `i-1`で数列の和が`j`であるものの個数とします.
`0 <= i <= n, 0 <= j <= mn <= 2500` です.
初期化は
``` python
dp = [[0] * (M + 1) for _ in range(n + 1)]
dp[0][0] = 1
```
であり, 更新は長さが`i-1`かつ最後の値が `j-m` 以上 `j-1` 以下である数列から条件を満たす数列が一意的に作ることができるので
``` math
dp[i][j] = \sum_{t=1}^{\min(j, m)} dp[i-1][j-t]
```
です.
更新に `O(M)` かかり, `i, j` の走査に `O(NK)` かかるので, 全体の計算量は `O(MNK)` となり, これでACすることができます.
なお, 更新と同時に$dp[i]$の累積和を計算するようにすれば 更新を$O(1)$で行うこともできます. この時の計算量は `O(NK)` となります.

### 実装

``` python
#!/usr/bin/env pypy3

n, m, k = map(int, input().split())
M = 2500
mod = 998244353
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(k + 1):
        for t in range(1, min(j, m) + 1):
            dp[i][j] += dp[i - 1][j - t]
            dp[i][j] %= mod

print(sum(dp[n][:k + 1]) % mod)
```

## D問題 『Range Count Query』

問題ページ: [D - Range Count Query](https://atcoder.jp/contests/abc248/tasks/abc248_d)
Difficulty: <font color="#804000"> 793 </font>

### 考察

`inds[x]` を 値が`x`であるインデックスを昇順に入れたリストとします.
すると, クエリでは値が`X`であり, インデックスが `L` 以上`R` 以下であるものの個数を返したいですが, これは二分探索によって `O(log N)` で求めることができます.
以上によって, 入力, 及び`inds`の構築に`O(N)`, クエリの処理に `O(Q log N)` かかるので, 全体の計算量は `O(max(N, Q log N))` であり, ACすることができます.

### 実装

``` python
#!/usr/bin/env pypy3

from bisect import bisect_left, bisect_right
from collections import defaultdict

n = int(input())
A = list(map(int, input().split()))

inds = defaultdict(list)
for i, x in enumerate(A):
    inds[x].append(i)

q = int(input())
for _ in range(q):
    l, r, x = map(int, input().split())
    l -= 1
    r -= 1
    res = bisect_right(inds[x], r) - bisect_left(inds[x], l)
    print(res)
```

## E問題 『K-colinear Line』

問題ページ: [E - K-colinear Line](https://atcoder.jp/contests/abc248/tasks/abc248_e)
Difficulty: <font color="#00C0C0"> 1292 </font>

### 考察

まず, `k==1` の時のみ答えが `Infinity` になる. 以下 `k != 1` とする.
直線 `L` が異なる二点を通る直線として現れる回数を `cnts[L]` 書くこととします.
すると 直線 `L` 上に $k$ 個以上の点としてあらわれることの必要十分条件は, `cnts[L]` が $k$個の点から2つを選ぶ方法の個数 ${}_k \mathrm{C}_2 = k (k - 1) / 2$ 以上であることです.

最後に 二点を通る直線の表示について考えます.
二点 $(x_0, y_0), (x_1, y_1)$を通る直線は

``` math
(x_1-x_0) y + (y_0-y_1)x + x_0 y_1 - x_1 y_0 = 0
```

と表されます.
直線の表示を一意的にするため, $y$ の係数, $x$ の係数, 定数項 のそれぞれの部分を一意的に表しておきます.

``` math
\begin{align*}
a &= x_1 - x_0 \\
b &= y_0 - y_1 \\
c &= x_0 y_1 - x_1y_0
\end{align*}
```

とおきます. このとき

* $\gcd(a, b, c) = 1$.
* $a \neq 0$ の時: $a > 0$.
* $a = 0$の時, $b > 0$.

となるように正規化しておきます.
`cnts`の構築に `O(N^2)` かかるので, 計算量は全体で `O(N^2)` です.

### 実装

``` python
#!/usr/bin/env pypy3

from collections import Counter
from itertools import combinations
from math import gcd

n, k = map(int, input().split())

if k == 1:
    print("Infinity")
    exit()

poses = [None] * n
for i in range(n):
    poses[i] = list(map(int, input().split()))

cnts = Counter()
for (x0, y0), (x1, y1) in combinations(poses, 2):
    a = x1 - x0
    b = y0 - y1
    c = x0 * y1 - x1 * y0
    g = gcd(gcd(a, b), c)
    a, b, c = a // g, b // g, c // g

    if a < 0:
        a *= -1
        b *= -1
        c *= -1
    elif a == 0 and b < 0:
        b *= -1
        c *= -1
    cnts[(a, b, c)] += 1

res = 0
for c in cnts.values():
    res += c >= k * (k - 1) // 2

print(res)
```