AtCoder水色を目指して勉強

# 背景
競技プログラミングはほとんどやったことがなかったのだが、AtCoderで問題解いてみると面白い物が多かった。発想系は発想するしかないが、しっかり記憶しておかないと解けなさそうなこともあったので、そのようなことを書いておくための自分用メモ。

# データ数とオーダー
AtCoderは2秒で演算が終わらないと不正解扱いとなるので、データ数がどれくらいの場合にどれくらいの時間計算量のアルゴリズムまで使えるのかを知っておかないと提出する際に通るか通らないか分からない。
また、簡単な問題でもどこまで雑な計算で良いのかの判断材料となる。

データ数nについて
$n = 3 \times 10^2$くらいの場合は$ O(n^3) $が許容される。
$n = 4 \times 10^3$くらいの場合は$ O(n^2) $が許容される。
$n = 10^6$くらいの場合は$O(nlogn)$が許容される(つまり高速なソートはいける)。
$n = 2^{10^{7}}$くらいの場合は$ O(logn) $まで許容される。

(@DaikiSuyama さんにコメントいただいたので内容修正)

# ABC157 D - Friend Suggestions
https://atcoder.jp/contests/abc157/tasks/abc157_d

## UnionFindTree
nのノードが、同一グループに所属しているかどうかの判定を高速に行うための木を高速に構築するためのデータ構造。
これはクラス化しておいて必要に応じてコピーしてちょっと改変して使えるようにしておかないと辛そう。

<details><summary>Friend Suggestions用に作ったUnionFindTree</summary><div>

```python
class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N + 1)]
        self.friendcount = [1] * (N + 1)

    def getroot(self, x):
        node = self.root[x]
        if node == x:
            return x
        self.root[x] = self.getroot(node)
        return self.root[x]

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        if xroot > yroot:
            self.root[xroot] = yroot
            self.friendcount[yroot] += self.friendcount[xroot]
        else:
            self.root[yroot] = xroot
            self.friendcount[xroot] += self.friendcount[yroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x) # only root has an accurate number
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False
```
</div></details>

# ABC156 D - Bouquet
https://atcoder.jp/contests/abc156/tasks/abc156_d

## n個から任意個選び出し
n個のものの中から何個か選び出す組み合わせは、$ 2^n - 1 $ 通り。
n個それぞれについて、選ぶ、選ばないの2パターンがあるので$ 2^n $で、全部選ばないという選択肢を消すためにマイナス1。

## 剰余の積
$ 2^x \, mod \, y = (2^{x-1} \, mod \, y ) \, \times (2 \, mod \, y ) \, mod \, y$ 
この性質を使って、$ 2^x \, mod \, y $は繰り返し二乗法で$ O(logN) $で計算できるっぽいが、pythonなら組み込み関数pow(2, x, y)でお手軽にできるようだ。

## 組み合わせの剰余
n個からr個を選び出す組み合わせは、

```math
\frac{n \times (n - 1) \times ... \times (n + 1 - r)}{r \times (r - 1) \times ... \times 1}
```

分子をA、分母をBと置くと、

```math
\frac{A}{B}
```

これのmod pである、$\frac{A}{B}\,mod\,p$は、フェルマーの小定理

```math
X^{p - 1} \, mod \, p = 1
```

から、

```math
\begin{align}
(\frac{A}{B} \, mod \, p) \times (B^{p-1} \, mod \, p) &= (A \times B^{p-2}) \, mod \, p \\
&= (A \, mod \, p) \times (B \, mod \, p)^{p-2} \, mod \, p
\end{align}
```

となる。

$ A\,mod\,p, B\,mod\,p$は、

```python
a = 1
b = 1
for i in range(r)
    a = a * (a - i) % p
    b = b * (i + 1) % p
```

で求まるので、$(A \, mod \, p) \times (B \, mod \, p)^{p-2} \, mod \, p$は

```python
a * pow(b, p-2, p)
```

で求まるはず。

# ABC154 E - Almost Everywhere Zero
## 桁DP
最大値Nまでの数のうち、条件Xを満たすものの種類は何種類あるか系で使う。
1桁目で条件Xを満たすのはいくつ、満たさないものはいくつ、というような感じで種類数を計算し、2桁目の種類数は1桁目の種類数を使うという感じで動的に求めていく。

たぶんO(logn)な感じなので、定数倍の計算量削減は頑張らなくても大抵の場合良さそう。

今回は以下の形で定義して動的に求めていった。

```python
dp[digit][lessthan][non_zero_num]
```

## lessthan
ある桁までの検査で最大値の数と一致している場合は、それ以下じゃないといけないという束縛を受ける。逆にそれより小さな数がきている場合は0-9のどれでもとれる。
というような条件を記述する。

## non_zero_num
一つ前の桁にて0以外の数の個数がcだった場合、0以外が来たらc+1になり、0がきたらcのままになる。
というような条件を記述する。

## 実装
<details><summary>コード</summary><div>

```python
n = int(input())
k = int(input())

digit = len(str(n))
# dp[i桁まで検査済み][lessthan][0以外の個数]
dp = [[[0] * (k + 2) for i in range(2)] for j in range(digit + 1)]
dp[0][0][0] = 1

for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            for d in range(10 if b == 1 else digitvalue + 1):
                dp[a][1 if b == 1 else 1 if (d < digitvalue) else 0][c if d == 0 else c + 1] += dp[a - 1][b][c]

print(dp[digit][0][k] + dp[digit][1][k])


```
</div></details>

## 感触
dpの多重配列の添字が現在のa, b, c, dの値に束縛されるというような書き方に馴染みがないので、もう少し習熟が必要そう。
スラスラ書けるようになってないと時間オーバーすると思うので、もう一度くらい類題をこなしたほうがいいように思う。

# ナップサック問題
## 何度でも項目を選べる場合
アイテムiについて、重さL[i]で価値V[i]とする。
ナップサックの最大容量を1からmax_loadまで変化させて、
以下のいずれかのうち最大価値のものにする

 - 容量(j-1)の最適価値
 - 容量(j-L[0])の最適価値 + V[0]の価値
 - 容量(j-L[1])の最適価値 + V[1]の価値
 - ...
 - 容量(j-L[item_num - 1])の最適価値 + V[item_num - 1]の価値

```python
for j in range(1, max_load + 1):
    dp[j] = max(dp[j-1], max(dp[j - L[i]] + V[i] for i in range(item_num))
```

## 1つの項目は1度しか選べない場合
アイテムiについて、重さL[i]で価値V[i]とする。
ナップサックの最大容量を1からmax_loadまで変化させて、0からi個目の項目しか使わない状態からi+1個目のアイテムも使う場合の順に使用するアイテムを拡張させながら計算していく。

```python
for i in range(1, item_types + 1):
    for j in range(1, max_load + 1):
        dp[i][j] = dp[i-1][j] if j - L[i-1] < 0 else max(dp[i-1][j], dp[i-1][j - L[i-1] + V[i-1])
```

この手法ではアイテムを使用したか、使用していないかのフラグを持っていない。
しかし、１つ目のfor文では、各アイテムiについての考慮を行っていることから、dp[i-1]ではそのアイテムが含まれるはずはなく、重複することはない。

 - 1つ目のアイテムだけ使った場合の各重さの最適解
 - 2つ目のアイテムまで使った場合の各重さの最適解
 - ...
 - 全アイテムを使った場合の各重さの最適解

の順で計算し、各アイテムの最適解の計算は、そのアイテムを使わない場合の最適解からの計算を行うので、フラグ管理しなくても自然とアイテムの重複は発生しない。

# ABC151 D - Maze Master

各地点から最大ステップかかる場所を計算して、その最大値を答えとする。
ある地点からの最大ステップかかる場所の探索は、深さ優先探索でも幅優先探索でも良さそうなので、深さ優先探索でいったが、結局2秒以内に処理を終わらせることができなかった。
訪問済みかどうかのフラグを配列で持っておき、配列を4個複製した後に右、下、左、上の再帰関数に呼ぶ必要があるのだが、配列コピーのコストが高いために時間オーバーだったという認識(安直にdeepcopyすると更に重い)。
幅優先探索の場合は同じステップ数の場所を順次訪問するため、訪問済みフラグは複製する必要がなく、配列コピーの定数倍の重みを軽減することができて終わるという理解をしている。
迷路は幅優先探索でやるようにしよう。

# ABC150 D - Semi Common Multiple
初めて青色が自力で解けそうだった問題。といっても一つのテストケースがREで通らなくて諦めたが。どうやら最小公倍数の計算で値が大きくなりすぎるとかで実行時エラーだったようだが、0除算とかばかり疑っていたので気づけなかった。
これがなかったら水色問題なんだろうな。

解説読むとよくわからないことが書いてあるので、自分はちょっと違う解法で解いたようだ。

半公倍数をよく見ると、それぞれ2倍すると最小公倍数の奇数倍である。なので、最大値Mの2倍まで許容してやることとして、最小公倍数の問題にする。
各aの最小公倍数を求める。この最小公倍数がいずれかのaの偶数倍だった場合は半公倍数が存在しないので、"0"を出力して終了する。
全部奇数倍だった場合、求めた最小公倍数のさらに奇数倍のうち2 * M以下になるものはなにか求める。

```python
max_value = 2 * m
lcm_value = lcm(A)
if any(lcm_value % a != 1 for a in A):
    print("0")
    sys.exit(0)
max_product = max_value // lcm
print((max_product + 1) // 2)
```

こっちのほうがシンプルに思うのだが、一応解法も理解してみる。