AtCoderを埋めていく

## はじめに
　競技プログラミング初心者がatcoderの問題を埋めていくログです。ログを公開することで継続を促すのが主な目的です。問題設定や解説は公式のものがあるので省略します。解いた感想 (コメント)、コーティングにおいて参考にしたサイトやコードを載せていこうと思います。
　なお、初心者ログとして残すので正解以外のコードも掲載します。具体的には、方針は合ってるけどTLEになるようなコードも参考として載せます。

## ABC
### C問題
#### 005 - おいしいたこ焼きの売り方
##### コード1. 貪欲法
$time: O(N + M)$
$space: O(N)$

```python
from collections import deque
def solve():
    takoyaki = deque()
    a_idx = 0
    b_idx = 0
    for t in range(1, 101):
        while takoyaki and takoyaki[0] + T < t:
            takoyaki.popleft()

        while a_idx < N and A[a_idx] == t:
            takoyaki.append(A[a_idx])
            a_idx += 1

        while b_idx < M and B[b_idx] == t:
            if not takoyaki:
                print('no')
                return
            takoyaki.popleft()
            b_idx += 1
    print('yes')

if __name__ == "__main__":
    T = int(input())
    N = int(input())
    A = list(map(int, input().split()))
    M = int(input())
    B = list(map(int, input().split()))
    solve()
```

#### 034 - 経路
##### コード1. nCr
$time: O(N)$
$space: O(N)$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n, r):
    return fact[n] / fact[n-r] / fact[r]

def solve(W, H):
    row, col = W - 1, H - 1
    n = row + col
    r = row
    fact = [ModInt(1)]
    for i in range(1, n + 1):
        fact.append(fact[i - 1] * i)
    print(cmb(fact, n, r))

if __name__ == "__main__":
    W, H = map(int, input().split())
    solve(W, H)
```

#### 045 - たくさんの数式
##### コード1. bit全探索
ジャッジに投げる時はf文字をstrの結合演算子に置換する必要があります。

$time: O(2^N)$
$space: O(2^N)$

```python
def solve(S):
    N = len(S) - 1
    ret = 0
    used_equation = set()
    for i in range(pow(2, N)):
        tmp_equation = ''
        last_j = -1
        for j in range(N):
            if i >> j & 1:
                tmp_equation = f'{tmp_equation} + {S[last_j + 1: j + 1]}'
                last_j = j
        if last_j < N:
            tmp_equation = f'{tmp_equation} + {S[last_j + 1:]}'
        ret += eval(tmp_equation) if tmp_equation not in used_equation else 0
        used_equation.add(tmp_equation)
    print(ret)

if __name__ == "__main__":
    S = input()
    solve(S)
```

#### 054 - One-stroke Path
##### コード1. 順列全探索
$time: O(N!)$
$space: O(N!)$

```python
from collections import deque

def solve():
    ret = 0
    stack = deque()
    stack.append([1, {1}])
    while stack:
        node, used = stack.popleft()
        if len(used) == N:
            ret += 1
            continue

        for n in neighbors[node]:
            if n in used:
                continue
            stack.append([n, used | {n}])

    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    neighbors = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        neighbors[a].append(b)
        neighbors[b].append(a)
    solve()
```

#### 076 - Dubious Document 2
##### コード１. 辞書式順序
$time: O(|S||T|)$
$space: O(|S|)$

```python
def solve():
    if len(S) < len(T):
        print('UNRESTORABLE')
        return

    valid_strs = []
    for i in range(len(S)):
        for j in range(len(T)):
            if len(S) <= i + j or S[i + j] != '?' and S[i + j] != T[j]:
                break
        else:
            valid_strs.append((S[: i] + T + S[i + len(T): ]).replace('?', 'a'))
    print(min(valid_strs) if valid_strs else 'UNRESTORABLE')

if __name__ == "__main__":
    S = input()
    T = input()
    solve()
```

#### 077 - Snuke Festival
##### コード1. binary search
$time: O(NlogN)$
$space: O(1)$

```python
import bisect

def solve(N, A, B, C):
     A.sort()
     B.sort()
     C.sort()
     ret = 0
     for j in range(N):
         i = bisect.bisect_right(A, B[j] - 1)
         k = bisect.bisect_left(C, B[j] + 1)
         ret += i * (N - k) if 0 <= i and 0 <= k < N else 0
     print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    solve(N, A, B, C)

```

#### 079 - Train Ticket
##### コード1. bit全探索
$time: O(2^N)$
$space: O(N)$

```python
def solve(operands):
    for i in range(pow(2, len(operands) - 1)):
        tmp_equation = operands[0]

        for j in range(len(operands) - 1):
            tmp_equation += '+' if i >> j & 1 else '-'
            tmp_equation += operands[j + 1]

        if eval(tmp_equation) == 7:
            print(tmp_equation + '=7')
            return

if __name__ == "__main__":
    operands = list(input())
    solve(operands)
```

#### 083 - Multiple Gift
##### コード1. 貪欲法
$time: O(log \frac{Y}{X})$
$space: O(1)$

```python
def solve():
    ret = 1
    cur_num = X
    while cur_num * 2 <= Y:
        cur_num *= 2
        ret += 1
    print(ret)

if __name__ == "__main__":
    X, Y = map(int, input().split())
    solve()
```

#### 104 - All Green
##### コード1. bit全探索
$time: O(N2^N)$
$space: O(1)$

```python
def solve(D, G, P, C):
    ret = float('inf')
    for i in range(pow(2, D)):
        tmp_score = 0
        tmp_counter = 0
        not_selected = -1

        for j in range(D):
            if i >> j & 1:
                tmp_counter += P[j]
                tmp_score += P[j] * 100 * (j + 1) + C[j]
            else:
                not_selected = j

        if G <= tmp_score:
            ret = min(ret, tmp_counter)
            continue

        for _ in range(1, P[not_selected]):
            tmp_score += 100 * (not_selected + 1)
            tmp_counter += 1
            if G <= tmp_score:
                ret = min(ret, tmp_counter)
                break

    print(ret)

if __name__ == "__main__":
    D, G = map(int, input().split())
    P = []
    C = []

    for _ in range(D):
        p, c = map(int, input().split())
        P.append(p)
        C.append(c)

    solve(D, G, P, C)
```

#### 128 - Switches
##### コード1. bit全探索
$time: O(2^N(MN))$
$space: O(N)$

```python
def solve(N, M, K, S, P):
    ret = 0
    for i in range(pow(2, N)):
        turned_on_switches = []
        for j in range(N):
            if i >> j & 1:
                turned_on_switches.append(j)
        for k in range(M):
            kth_turned_on_lights_num = 0
            for s in S[k]:
                kth_turned_on_lights_num += 1 if s - 1 in turned_on_switches else 0
            if kth_turned_on_lights_num % 2 != P[k]:
                break
        else:
            ret += 1
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        K.append(tmp[0])
        S.append(tmp[1:])
    P = list(map(int, input().split()))
    solve(N, M, K, S, P)
```

#### 145 - Average Length
##### コード1. 順列全探索
$time: O(N!)$
$space: O(N!)$

```python
from collections import deque

def solve(N, X, Y):
    ret = 0
    counter = 0
    stack = deque()
    cities = [i for i in range(N)]
    for city_idx in cities:
        stack.append([0, city_idx, cities[:city_idx] + cities[city_idx + 1:]])

    while stack:
        dist, city_idx, rest = stack.pop()
        if not rest:
            ret += dist
            counter += 1

        for idx, next_city_idx in enumerate(rest):
            stack.append([dist + ((X[city_idx] - X[next_city_idx])**2 + (Y[city_idx] - Y[next_city_idx])**2)**(1/2), next_city_idx, rest[:idx] + rest[idx + 1:]])

    print(ret / counter)

if __name__ == "__main__":
    N = int(input())
    X = []
    Y = []

    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)

    solve(N, X, Y)
```

#### 147 - HonestOrUnkind2
##### コード1. bit全探索
$time: O(2^N)$
$space: O(N)$

```python
def solve(N, A, X, Y):
    ret = 0
    for i in range(2 ** N):
        tmp = []
        for j in range(N):
            if i >> j & 1:
                tmp.append(j)
        if not tmp:
            continue

        is_valid = True
        for a_idx in tmp:
            for idx in range(A[a_idx]):
                if (Y[a_idx][idx] and X[a_idx][idx] - 1 not in tmp) \
                        or (not Y[a_idx][idx] and X[a_idx][idx] - 1 in tmp):
                    is_valid = False
                    break
        ret = max(ret, len(tmp)) if is_valid else ret
    return ret

if __name__ == "__main__":
    N = int(input())
    A = []
    X, Y = [], []
    for _ in range(N):
        A.append(int(input()))
        tmp_x, tmp_y = [], []
        for _ in range(A[-1]):
            x, y = map(int, input().split())
            tmp_x.append(x)
            tmp_y.append(y)
        X.append(tmp_x)
        Y.append(tmp_y)
    print(solve(N, A, X, Y))
```

#### 150 - Count Order
##### コード1. 順列全探索
$time: O(N!)$
$space: O(N!)$

```python
from itertools import permutations

def solve(N, P, Q):
    vals = [i for i in range(1, N + 1)]
    perms = list(permutations(vals))
    print(abs(perms.index(P) - perms.index(Q)))

if __name__ == "__main__":
    N = int(input())
    P = tuple(map(int, input().split()))
    Q = tuple(map(int, input().split()))
    solve(N, P, Q)
```

#### 165 - Many Requirements
##### コード１. DFS
$time: O(Q_{M}H_{N})$

```python
def solve(cur_index):
    global ret
    if cur_index == N:
        tmp_sum = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                tmp_sum += d[i]
        ret = max(ret, tmp_sum)
        return
    for i in range(min(A[cur_index], M), M + 1):
        A[cur_index + 1] = i
        solve(cur_index + 1)


if __name__ == '__main__':
    N, M, Q = map(int, input().split())
    a = [0 for _ in range(Q)]
    b = [0 for _ in range(Q)]
    c = [0 for _ in range(Q)]
    d = [0 for _ in range(Q)]
    for i in range(Q):
         a[i], b[i], c[i], d[i] = map(int, input().split())
    ret = 0
    A = [1 for _ in range(N + 1)]
    solve(0)
    print(ret)
```

#### 167 - Skill Up
##### コード1. bit全探索
$time: O(M2^N)$
$space: O(N) + O(M)$

```python
def is_valid(vals, M, X):
    for i in range(M):
        if vals[i] < X:
            return False
    return True

def solve(N, M, X, C, A):
    ret = float("inf")
    for i in range(2 ** N):
        tmp_vals = [0 for _ in range(M)]
        cost = 0
        for j in range(N):
            if (i >> j) & 1:
                cost += C[j]
                for k in range(M):
                   tmp_vals[k] += A[j][k]
        ret = min(ret, cost) if is_valid(tmp_vals, M, X) else ret
    return ret if ret != float("inf") else -1

if __name__ == '__main__':
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        C.append(tmp[0])
        A.append(tmp[1:])

    print(solve(N, M, X, C, A))
```

### D問題
#### 002 - 派閥
##### コード1. bit全探索
$time: O(2^N N^2)$
$space: O(N)$

```python
def isValidGroup(group_members, relations):
    if len(group_members) <= 1:
        return True

    for i in range(len(group_members)):
        for j in range(i + 1, len(group_members)):
            if group_members[j] not in relations[group_members[i]]:
                return False

    return True

def solve(N, relations):
    ret = 0
    for i in range(pow(2, N)):
        current_group_members = []
        for j in range(N):
            if i >> j & 1:
                current_group_members.append(j + 1)
        ret = max(ret, len(current_group_members)) if isValidGroup(current_group_members, relations) else ret
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    relations = [set() for _ in range(N + 1)]
    for _ in range(M):
        x, y = map(int, input().split())
        relations[x].add(y)
        relations[y].add(x)
    solve(N, relations)
```

#### 023 - 射撃王
##### コード１. 二分探索
$time: O(Nlog(NS))$
$space: O(N)$

```python
def isValid(X, H, S):
    bucket = {i: 0 for i in range(N + 1)}
    for i in range(N):
        if (X - H[i]) // S[i] <= N:
            bucket[(X - H[i]) // S[i]] += 1
        else:
            bucket[N] += 1

    T = []
    for k in bucket:
        T += [k] * bucket[k]

    current_time = 0
    for t in T:
        if t < current_time:
            return False
        current_time += 1
    return True

def solve(N, H, S):
    ok = max([H[i] + S[i] * (N - 1) for i in range(N)])
    ng = max(H) - 1
    while ng < ok - 1:
        mid = ng + ok >> 1
        if isValid(mid, H, S):
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    N = int(input())
    H = []
    S = []
    for _ in range(N):
        h, s = map(int, input().split())
        H.append(h)
        S.append(s)

    solve(N, H, S)
```

#### 088 - Grid Repainting
##### コード１. BFS
$time: O(HW)$
$space: O(HW)$

```python
from collections import deque

def solve():
    if s[0][0] == '#':
        print(-1)
        return

    stack = deque()
    stack.append([0, 0, 0])
    used = [[False for _ in range(W)] for _ in range(H)]
    costs = [[float('inf') for _ in range(W)] for _ in range(H)]
    while stack:
        i, j, cost = stack.popleft()
        costs[i][j] = cost
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not 0 <= x < H or not 0 <= y < W or used[x][y] or s[x][y] == '#':
                continue
            stack.append([x, y, cost + 1])
            used[x][y] = True

    print(dot_num - 1 - costs[H - 1][W - 1] if costs[H - 1][W - 1] != float('inf') else -1)

if __name__ == "__main__":
    H, W = map(int, input().split())
    s = []
    dot_num = 0
    for _ in range(H):
        tmp = list(input())
        dot_num += tmp.count('.')
        s.append(tmp)
    solve()
```

#### 103 - Islands War
##### コード１. 区間スケジューリング
$time: O(M)$
$space: O(1)$

```python
def solve():
    ret = 0
    most_right = 0
    for left, right in sects:
        if left < most_right:
            continue
        ret += 1
        most_right = right
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    sects = []
    for _ in range(M):
        sects.append(list(map(int, input().split())))
    sects.sort(key=lambda x: x[1])
    solve()
```

#### 138 - Ki
##### コード１. DFS
$time: O(N + Q)$
$space: O(N)$

```python
from collections import deque

def solve(N, children, weights):
    ret = [0 for _ in range(N + 1)]
    stack = deque()
    stack.append([0, 1])
    used = [False for _ in range(N + 1)]
    used[1] = True
    while stack:
        weights_sum, node = stack.pop()
        weights_sum += weights[node]
        ret[node] = weights_sum

        if not children[node]:
            continue

        for c in children[node]:
            if used[c]:
                continue
            stack.append([weights_sum, c])
            used[c] = True

    for idx in range(1, N + 1):
        print(ret[idx], end=" ")

if __name__ == "__main__":
    N, Q = map(int, input().split())
    children = [[] for _ in range(N + 1)]

    for _ in range(1, N):
        a, b = map(int, input().split())
        children[a].append(b)
        children[b].append(a)

    weights = [0 for _ in range(N + 1)]

    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p] += x

    solve(N, children, weights)
```


#### 145 - Knight

- 動的計画法を使おうとする場合、二次元配列を初期化するだけでTLE。
- 二項係数に気付いても高速化しなければやっぱりTLE。
- 下記のように高速化してもPython3で提出したらTLE。

　「斜交座標を作ればいけるのか・・・？」みたいなことを解き始めた時には考えていましたが無理ですね。ちなみに二項係数の高速化はよくある設定みたいです。

##### コード１. ナイーブな実装
$time: O\ (X + Y)$
[「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a)

```python
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)

```

##### コード2. ModIntの導入 + 逆元計算の高速化 
　提出の際は必要なmethodだけ記載した方がいいです。
$time: O\ (X + Y)$
[Pythonでmodintを実装してみた](https://qiita.com/wotsushi/items/c936838df992b706084c)

```python
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

n, m = map(int, [n, m])
fact = [ModInt(1)]
for i in range(1, X + Y + 1):
    fact.append(fact[i-1] * i)

def cmb(n, r):
    return fact[n] / fact[n-r] / fact[r]

print(cmb(n+m, min(n, m)))

```

#### 146 - Coloring Edges on Tree
##### コード1. 超愚直 BFS (TLE)
　まあ考え方自体は合ってますね。残念ながらこれだと計算時間が足りません。ポイントはBFSを行なっている最中に`used_edges`や`used_colors`内を`in`関数で検索しているところです。ここで計算オーダーが増えています。この余分な計算を無くすことで正解が導かれます。
$time: O(N^2)$

```python

from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = []
colors = [1 for _ in range(1, N + 1)]
used_colors = [[] for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.popleft()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].append(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.append(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)

```

##### コード2. 改良版 BFS
　`used_edges`と`used_colors`において使用するデータ構造を`list`から`set`に変更しました。これにより`in`による検索の平均オーダーが$O(n)$から$O(1)$になりました。
[Time Complexity - Python Wiki](https://wiki.python.org/moin/TimeComplexity)
$time: O(N)$

```python
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = set()
colors = [1 for _ in range(1, N + 1)]
used_colors = [set() for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.pop()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].add(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.add(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)
```

#### 147 - Xor Sum 4
##### コード1. 二重ループ(TLE)
　前述の`ModInt`を利用した実装。まあ計算量的に絶対通らないけど念の為試したくなる解法ですね。言うまでもなく二重ループを回すとTLEです。
$time: O(N^2)$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        if isinstance(x, str):
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

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

def xor(a, b):
    return a ^ b

ret = ModInt(0)
for i in range(N - 1):
    for j in range(i + 1, N):
        ret += xor(A[i], A[j])

print(ret)
```

##### コード2. bitごとにXOR計算 (TLE)
　一応想定解法ですが、TLEです。
$time: O(Nlog(max(A)))$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        if isinstance(x, str):
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def encode(N, A, max_k):
    bits = [[0, 0] for _ in range(max_k)]
    for i in range(N):
        a = format(A[i], 'b').zfill(max_k)
        for k in range(max_k):
            if int(a[k]) == 0:
                bits[max_k - 1 - k][0] += 1
            else:
                bits[max_k - 1 - k][1] += 1
    return bits

def decode(bits):
    return sum([ModInt(2 ** k * (counter[0] * counter[1])) for k, counter in enumerate(bits)])

N = int(input())
A = list(map(int, input().split()))
max_k = len(bin(max(A))) - 2

print(decode(encode(N, A, max_k)))

```

##### コード3. bitごとにXOR計算 (高速化)

- 配列を使わない
- 文字列を介さないで直接bit計算
- Aの最大値を求めないで定数として(Aの桁数の最大値を)定義する

ことで高速化できます。これで4倍近く高速化されました。
$time: O(Nlog(max(A)))$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        if isinstance(x, str):
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def calc(N, A, max_k):
    ret = ModInt(0)
    for k in range(max_k):
        count = 0
        for i in A:
            if i & (1 << k):
                count += 1
        ret += 2 ** k * count * (N - count)
    return ret

N = int(input())
A = list(map(int, input().split()))
max_k = 60

print(calc(N, A, max_k))
```

#### 148 - Brick Break 

##### コード1. イテレート
　何も言うことがないです。文意を読み取った時にシンプルすぎて何か見落としているのではないかと少し怖くなりました。
$time: O(N)$

```python

N = int(input())
a = list(map(int, input().split()))
broken = 0

for n in range(N):
    if a[n] != broken + 1:
        continue
    broken += 1

if broken == 0:
    print(-1)
else:
    print(N - broken)
```

#### 149 - Prediction and Restriction
##### コード1. イテレート
$time: O(N)$

```python

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

def getScore(t, R, S, P):
    if t == 'r':
        return P
    if t == 's':
        return R
    return S

latest = [{'string': '', 'count': 0} for _ in range(K)]

ret = 0
for idx, t in enumerate(T):
    latest_idx = idx % K
    if idx + 1 <= K or t != latest[latest_idx]['string']:
        ret += getScore(t, R, S, P)
        latest[latest_idx]['string'] = t
        latest[latest_idx]['count'] = 1
        continue

    if latest[latest_idx]['count'] % 2 == 0:
        ret += getScore(t, R, S, P)
    latest[latest_idx]['count'] += 1

print(ret)
```

#### 150 - Semi Common Multiple
##### コード1. イテレート
　考察で見落としがあり、苦戦しました。
[AtCoder ABC 150 D - Semi Common Multiple (400 点)](https://drken1215.hatenablog.com/entry/2020/01/12/135000)
$time: O(N)$

```python
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

def solve(N, M, A):
    while A[0] % 2 == 0:
        for idx, a in enumerate(A):
            if a % 2 != 0:
                return 0
            A[idx] //= 2
        M //= 2

    for a in A:
        if a % 2 == 0:
            return 0

    cur_lcm = 1
    for a in A:
        cur_lcm = lcm(cur_lcm, a)
        if M < cur_lcm:
            return 0
    return (M // cur_lcm + 1) // 2

if __name__ == '__main__':
    N, M = map(int, input().split())
    A = list((map(int, input().split())))
    A = [a // 2 for a in A]
    print(solve(N, M, A))
``` 

#### 151 - Maze Master
##### コード1. BFS + 2重ループ
　`stack.append`ではなく`stack.popleft()`の後に`used`を更新するとTLEです。

$time: O((HW)^2)$

```python
from collections import deque

def bfs(start, maze, H, W):
    max_step = 0
    used = [[False for _ in range(W)] for _ in range(H)]
    start_x, start_y = start
    used[start_x][start_y] = True
    stack = deque([[start, 0]])
    while stack:
        (i, j), step = stack.popleft()
        if maze[i][j] == '#':
            continue
        max_step = max(max_step, step)
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < H and 0 <= y < W and not used[x][y]:
                stack.append([(x, y), step + 1])
                used[x][y] = True
    return max_step

if __name__ == '__main__':
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(input()))
    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, bfs((i, j), S, H, W))
    print(ret)
```

#### 152 - Handstand 2
##### コード1. map生成
　全ての数字を定数長の二次元配列に格納できることに気づくかどうかですね。
$time: O(N)$

```python
def solve(N):
    ret = 0
    counter = [[0 for _ in range(10)] for _ in range(10)]
    for n in range(1, N + 1):
        i, j = map(int, [str(n)[0], str(n)[-1]])
        counter[i][j] += 1

    for i in range(10):
        for j in range(10):
            ret += counter[i][j] * counter[j][i]
    return ret


if __name__ == '__main__':
    N = int(input())
    ret = solve(N)
    print(ret)
```

#### 156 - Bouquet
##### コード1. イテレートして階乗計算（TLE）
　そういえば線形オーダーよりも高速で階乗を計算する方法を知らないです。
$time: O(N)$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n, r):
    return fact[n] / fact[n-r] / fact[r]

def solve(n, a, b):
    fact = [ModInt(1)]
    for i in range(1, max(n, a, b) + 1):
        fact.append(fact[i-1] * i)

    return  ModInt(2**n) - 1 - cmb(fact, n, a) - cmb(fact, n, b)

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    ret = solve(n, a, b)
    print(ret)
```

##### コード2. nCrの計算を改良
　なぜか$n-r+1$~ $n$のイテレートを$O(N)$だと誤解してました（本当になぜ？）。
　繰り返し二乗法を実装しようと思いましたが、pythonだとpow関数で既に採用されてるので必要ないみたいです。

$time: max(O(A), O(B))$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n, r):
    mul = ModInt(1)
    for i in range(n - r + 1, n + 1):
        mul *= i
    return mul / fact[r]

def solve(n, a, b):
    fact = [ModInt(1)]
    for i in range(1, max(a, b) + 1):
        fact.append(fact[i-1] * i)
    return  ModInt(pow(2,n)) - 1 - cmb(fact, n, a) - cmb(fact, n, b)

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    ret = solve(n, a, b)
    print(ret)
```

#### 157 - Friend Suggestions
##### コード1. 愚直なUnionFind(TLE)
$time: O(N^2)$

```python
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

def solve(uf, first_order_friends, blocked_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(list(set(uf.members(i)) - first_order_friends[i] - blocked_list[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        blocked_list[c].add(d)
        blocked_list[d].add(c)

    for ans in solve(uf, first_order_friends, blocked_list)[1:]:
        print(ans, end=' ')
```

##### コード2. 二重ループ＋UnionFind(TLE)
　`first_order_friends`と`blocked_list`を統一しました。この段階で二重ループを回していることがTLEの直接的な原因であることに気づきました。
$time: O(N^2)$

```python
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x, except_list):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root and i not in except_list]

def solve(uf, first_order_friends):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(uf.members(i, first_order_friends[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        first_order_friends[c].add(d)
        first_order_friends[d].add(c)

    for ans in solve(uf, first_order_friends)[1:]:
        print(ans, end=' ')

```

##### コード3. 入力チェック ＋ UnionFind
　コード２での考察を元に

- c,dが同じグループに属する場合のみ`except_list`に追加
- $O(1)$でグループの要素数を取得

するように変更しました。

$time: O(N)$

```python
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

def solve(uf, except_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(uf.size(i) - 1 - len(except_list[i]))
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    except_list = [[] for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        except_list[a].append(b)
        except_list[b].append(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        if not uf.same(c, d):
            continue
        except_list[c].append(d)
        except_list[d].append(c)

    for ans in solve(uf, except_list)[1:]:
        print(ans, end=' ')

```

#### 160 - Line++
##### コード1. BFS
　$10^6$でも間に合うのか不安でしたが、大丈夫みたいです。
$time: O(N^2)$

```python
from collections import deque

def solve(N, X, Y):
    ret = [0] * N
    already_used = [[False for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        already_used[i][i] = True
        reached = [False for _ in range(N + 1)]
        reached[i] = True
        stack = deque([[i, 0]])

        while stack:
            node, step = stack.popleft()
            if 1 <= step and not already_used[i][node]:
               ret[step] += 1
            already_used[i][node], already_used[node][i] = True, True

            for x in [node + 1, node - 1]:
                if 0 < x < N + 1 and not reached[x]:
                    stack.append([x, step + 1])
                    reached[x] = True
            if node == X and not reached[Y]:
                stack.append([Y, step + 1])
                reached[x] = True
            if node == Y and not reached[X]:
                stack.append([X, step + 1])
                reached[x] = True
    return ret

if __name__ == '__main__':
    N, X, Y = map(int, input().split())
    for r in solve(N, X, Y)[1:]:
        print(r)
```

#### 161 - Lunlun Number
##### コード1. 3次元配列
　解説見たときに「あっ」って声が出ました。流石にオレオレ実装が過ぎますね。
$time: O(N)$

```python
def solve(K):
    ref = [[['0'], ['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['8'], ['9']]]
    if K < 10:
        return ref[0][K][0]

    rest = K - 9
    i = 0
    while True:
        i += 1
        ref.append([[] for _ in range(10)])
        for j in range(10):
            if j == 0:
                for r in ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
            elif j == 9:
                for r in ref[i-1][j-1] + ref[i-1][j]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r
            else:
                for r in ref[i-1][j-1] + ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r

if __name__ == '__main__':
    K = int(input())
    print(solve(K))
```


##### コード2. deque
　大分スッキリしました。
$time: O(N)$

```python
from collections import deque

def solve(K):
    stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for _ in range(K):
        num = stack.popleft()
        one_digit = num % 10
        if one_digit % 10 == 0:
            nexts = [num * 10, num * 10 + 1]
        elif one_digit % 10 == 9:
            nexts = [num * 10 + 8, num * 10 + 9]
        else:
            nexts = [num * 10 + one_digit - 1, num * 10 + one_digit, num * 10 + one_digit + 1]

        for n in nexts:
            stack.append(n)
    return num

if __name__ == '__main__':
    K = int(input())
    print(solve(K))
```

#### 163 - Sum of Large Numbers
##### コード1. 和の公式
$time: O(N - K)$
$space: O(1)$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def sumOfArithmeticSequence(a, b):
    return (a + b) * (b - a + 1) // 2

def solve(N, K):
    ret = ModInt(0)
    for i in range(K, N + 2):
       ret += sumOfArithmeticSequence(N - i + 1, N) - sumOfArithmeticSequence(0, i - 1) + 1
    return ret


if __name__ == '__main__':
    N, K = map(int, input().split())
    print(solve(N, K))
```

##### コード2. 累積和
$time: O(N)$
$space: O(N)$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def differenceOfMaximumSumAndMinimumSum(cumulative_sum, i):
    return (cumulative_sum[-1] - cumulative_sum[-i-1]) - cumulative_sum[i - 1]

def solve(N, K):
    ret = ModInt(1)
    cumulative_sum = [0] * (N + 1)
    tmp_sum = 0
    for i in range(1, N + 1):
        tmp_sum += i
        cumulative_sum[i] = tmp_sum

    for i in range(K, N + 1):
        ret += differenceOfMaximumSumAndMinimumSum(cumulative_sum, i) + 1
    return ret


if __name__ == '__main__':
    N, K = map(int, input().split())
    print(solve(N, K))
```

#### 164 - Multiple of 2019
##### コード1. DP
$time: O(N)$
$space: O(N)$

```python
MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N - 1, -1, -1):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))
```

#### 167 - Teleporter
##### コード1. Floyd's cycle finding
$time: O(N)$
$space: O(N)$

```python
def solve(N, K, A):
    slow, fast = 1, 1
    is_first = True
    while is_first or slow != fast:
        is_first = False
        slow = A[slow - 1]
        fast = A[A[fast - 1] - 1]
    fast = 1
    steps_before_entering_cycle = []
    while slow != fast:
        steps_before_entering_cycle.append(fast)
        slow = A[slow - 1]
        fast = A[fast - 1]

    if K < len(steps_before_entering_cycle):
        return steps_before_entering_cycle[K]

    cycles = [slow]
    while A[slow - 1] != cycles[0]:
        cycles.append(A[slow - 1])
        slow = A[slow - 1]
    ret = cycles[(K - len(steps_before_entering_cycle)) % len(cycles)]
    return ret

if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    print(solve(N, K, A))
```
#### 168 - .. (Double Dots)
##### コード1. BFS
$time: O(N + M)$
$space: O(N + M)$

```python
from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]
                stack.append(n[1])

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)
```

#### 171 - Replacing
##### コード1. イテレート
$time: O(N + Q)$
$space: O(N)$

```python
def solve():
    ret = sum(A)
    dict_A = {}
    for a in A:
        dict_A[a] = dict_A.get(a, 0) + 1
    for i in range(Q):
        tmp = dict_A.get(B[i], 0)
        ret -= tmp * B[i]
        dict_A[B[i]] = 0
        dict_A[C[i]] = dict_A.get(C[i], 0) + tmp
        ret += C[i] * tmp
        print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [], []
    for _ in range(Q):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)
    solve()
```

#### 172 - Sum of Divisors
##### コード1. ループの入れ替え
$time: O(N)$
$space: O(1)$

```python
def solve():
    ret = 0
    for k in range(1, N + 1):
        y = N // k
        ret += k * y * (y + 1) // 2
    print(ret)

if __name__ == "__main__":
    N = int(input())
    solve()
```

### E問題
#### 148 - Double Factorial
##### コード1. 式変形
$time: O(logN)$
$space: O(1)$

```python
def solve(N):
   if N < 9 or N % 2:
       return 0
   ret = 0
   N //= 2
   while N:
       ret += N // 5
       N //= 5
   return ret

if __name__ == "__main__":
    N = int(input())
    print(solve(N))
```

#### 153 - Crested Ibis vs Monster
##### コード1. dp
$time: O(NH)$
$space: O(H)$

```python
def solve(h, n, A, B):
    dp = [float("inf")] * h + [0]
    for i in range(h, -1, -1):
        if dp[i] == float("inf"):
            continue
        for j in range(n):
            if 0 <= i - A[j]:
                dp[i - A[j]] = min(dp[i - A[j]], dp[i] + B[j])
            else:
                dp[0] = min(dp[0], dp[i] + B[j])
    return dp[0]

if __name__ == '__main__':
    h, n = map(int, input().split())
    a = [0] * n
    b = [0] * n

    for i in range(n):
        a[i], b[i] = map(int, input().split())

    print(solve(h, n, a, b))
```

#### 160 - Red and Green Apples
##### コード1. ソート ＋ イテレート
$time: max(O(X + Y), O(AlogA), O(BlogB), O(ClogC))$

```python
def solve(X, Y, p, q, r):
    red_apples = sorted(p, reverse=True)[: X]
    green_apples = sorted(q, reverse=True)[: Y]
    white_apples = sorted(r)

    ret = 0
    while red_apples and green_apples:
        if not white_apples or (white_apples[-1] < red_apples[-1] and white_apples[-1] < green_apples[-1]):
            return ret + sum(red_apples) + sum(green_apples)

        ret += white_apples.pop(-1)
        if red_apples[-1] < green_apples[-1]:
            red_apples.pop(-1)
        else:
            green_apples.pop(-1)


    if not red_apples:
        while green_apples and white_apples and (green_apples[-1] < white_apples[-1]):
            ret += white_apples.pop(-1)
            green_apples.pop(-1)
        return ret + sum(green_apples)

    else:
        while red_apples and white_apples and (red_apples[-1] < white_apples[-1]):
            ret += white_apples.pop(-1)
            red_apples.pop(-1)
        return ret + sum(red_apples)

if __name__ == '__main__':
    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    print(solve(X, Y, p, q, r))
```

##### コード2. ソート
　こちらの方が簡潔ですね。
$time: max(O(AlogA), O(BlogB), O((X + Y + C)log(X + Y + C)))$

```python
def solve(X, Y, p, q, r):
    red_apples = sorted(p, reverse=True)[: X]
    green_apples = sorted(q, reverse=True)[: Y]
    return sum(sorted(red_apples + green_apples + r, reverse=True)[: X + Y])

if __name__ == '__main__':
    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    print(solve(X, Y, p, q, r))
```

#### 166 - This Message Will Self-Destruct in 5s
##### コード1. イテレート + 辞書
$time: O(N)$
$sapce: O(N)$

```python
def solve(N, A):
    ret = 0
    ref = {}
    for idx, a in enumerate(A):
        ith_val = idx - a
        ret += ref[ith_val] if ith_val in ref else 0
        ref[idx + a] = ref.get(idx + a, 0) + 1
    return ret

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))
```

#### 167 - Colorful Blocks
##### コード1. 異なる色の数をイテレート
$time: O(N)$
$space: O(N)$


```python
MOD = 998244353
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n ,r):
    return ModInt(1) * fact[n] / fact[n - r] / fact[r]

def solve(N, M, K):
    fact = [ModInt(1)]
    for i in range(1, N + 1):
        fact.append(fact[i -1] * i)

    ret = ModInt(0)
    for x in range(K + 1):
        ret += cmb(fact, N - 1, x) * M * pow(M - 1, N - x - 1, MOD)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    print(solve(N, M, K))
```

## ARC
### A問題
#### 029 - 高橋君とお肉
##### コード1. bit全探索
$time: O(2^N)$
$space: O(1)$

```python
def solve(N, T):
    shortest_time = float('inf')
    for i in range(pow(2, N)):
        left_totoal_time = 0
        right_total_time = 0
        for j in range(N):
            if i >> j & 1:
                left_totoal_time += T[j]
            else:
                right_total_time += T[j]
        shortest_time = min(shortest_time, max(left_totoal_time, right_total_time))
    print(shortest_time)

if __name__ == "__main__":
    N = int(input())
    T = []
    for _ in range(N):
        T.append(int(input()))
    solve(N, T)
```

### B問題
#### 026 - 完全数
##### コード1. 約数列挙
$time: O(\sqrt{N})$
$space: O(\sqrt{N})$

```python
def getDivs(N):
    divs = []
    for i in range(1, int(N**0.5) + 1):
        if not N % i:
            divs.append(i)
            if i != N // i:
                divs.append(N // i)
    return divs

def solve(N):
    divs = getDivs(N)
    div_sum = sum(divs)
    if div_sum == 2 * N:
        return "Perfect"
    return "Abundant" if 2 * N < div_sum else "Deficient"

if __name__ == "__main__":
    N = int(input())
    print(solve(N))
```

#### 031 - 埋め立て
##### コード1. BFS
$N = 100$
$time: O(N^2)$
$space: O(N)$

```python
from collections import deque
def bfs(i, j, area_count):
    stack = deque()
    stack.append([i, j])
    used = [[False for _ in range(C)] for _ in range(R)]
    used[i][j] = True
    while stack:
        x, y = stack.popleft()
        area_count -= 1
        for r, c in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if not 0 <= r < R or not 0 <= c < C or A[r][c] == 'x' or used[r][c]:
                continue
            stack.append([r, c])
            used[r][c] = True
    return not area_count

def solve():
    for i in range(R):
        for j in range(C):
            if bfs(i, j, total_area_count if A[i][j] == 'o' else total_area_count + 1):
                print('YES')
                return
    print('NO')


if __name__ == "__main__":
    R, C = 10, 10
    A = []
    total_area_count = 0
    for _ in range(R):
        a = list(input())
        total_area_count += a.count('o')
        A.append(a)
    solve()
```

#### 037 - バウムテスト
##### コード1. BFS
$time: O(N + M)$
$space: O(N)$

```python
from collections import deque

def solve():
    ret = 0
    used = [False for _ in range(N + 1)]
    stack = deque()
    for i in range(1, N + 1):
        if used[i]:
            continue
        if not neighbors[i]:
           ret += 1
           continue

        for n in neighbors[i]:
            stack.append([n, i])
            used[n] = True
        is_tree = True

        while stack:
            node, parent = stack.popleft()
            for n in neighbors[node]:
                if n == parent:
                    continue
                if used[n]:
                    is_tree = False
                    continue
                stack.append([n, node])
                used[n] = True

        if is_tree:
            ret += 1
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    neighbors = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        neighbors[u].append(v)
        neighbors[v].append(u)
    solve()
```

### C問題
#### 005 - 器物損壊！高橋君
##### コード1. BFS
$time: O(HW)$
$space: O(HW)$

```python
from collections import deque
def solve():
    stack = deque()
    stack.append([(si, sj), 0])
    cost_matrix = [[float('inf') for _ in range(W)] for _ in range(H)]
    cost_matrix[si][sj] = 0

    while stack:
        (i, j), cost = stack.popleft()
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not 0 <= x < H or not 0 <= y < W or 2 < cost:
                continue

            if c[x][y] == 'g':
                cost_matrix[x][y] = min(cost_matrix[x][y], cost)

            if c[x][y] == '#' and cost + 1 < cost_matrix[x][y] and cost + 1 <= 2:
                stack.append([(x, y), cost + 1])
                cost_matrix[x][y] = cost + 1

            if c[x][y] == '.' and cost < cost_matrix[x][y]:
                stack.append([(x, y), cost])
                cost_matrix[x][y] = cost

    print('YES' if cost_matrix[gi][gj] <= 2 else 'NO')

if __name__ == "__main__":
    H, W = map(int, input().split())
    c = []
    si, sj = 0, 0
    gi, gj = 0, 0
    for i in range(H):
        tmp = list(input())
        if 's' in tmp:
            si, sj = i, tmp.index('s')
        if 'g' in tmp:
            gi, gj = i, tmp.index('g')
        c.append(tmp)
    solve()
```

#### 006 - 積み重ね
##### コード1. 貪欲法
$time: O(N)$
$space: O(N)$

```python
def solve():
    base_ws = [0 for _ in range(N)]
    for w in W:
        for idx, bw in enumerate(base_ws):
            if w <= bw or bw == 0:
                base_ws[idx] = w
                break
    print(N - base_ws.count(0))

if __name__ == "__main__":
    N = int(input())
    W = []
    for _ in range(N):
        W.append(int(input()))
    solve()
```

## AGC
### A問題
#### 033 - Darker and Darker
##### コード1. BFS
$time: O(HW)$
$space: O(HW)$

```python
from collections import deque
def solve():
    max_cost = 0
    stack = deque()
    used = [[False for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                continue
            stack.append([(i, j), 0])
            used[i][j] = True
    while stack:
        (i, j), cost = stack.popleft()
        max_cost = max(max_cost, cost)
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not 0 <= x < H or not 0 <= y < W or used[x][y]:
                continue
            stack.append([(x, y), cost + 1])
            used[x][y] = True
    print(max_cost)

if __name__ == "__main__":
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(input()))
    solve()
```

#### 038 - 01 Matrix
##### コード1. 考察
$time: O(HW)$
$space: O(HW)$

```python
def solve():
    for row in range(H):
        for col in range(W):
            if (row < B and col < A) or (B <= row and A <= col):
                print(0, end='')
            else:
                print(1, end='')
        print()

if __name__ == "__main__":
    H, W, A, B = map(int, input().split())
    solve()
```

#### 043 - Range Flip Find Route
##### コード1. DP
　実装よりは考察が大変でした。
$time: O(HW)$
$space: O(HW)$

```python
def solve(H, W, s):
    scores = [[float('inf') for _ in range(W)] for _ in range(H)]
    scores[0][0] = 0 if s[0][0] == '.' else 1

    for i in range(H):
        for j in range(W):
            for x, y in [(i - 1, j), (i, j - 1)]:
                if x < 0 or y < 0:
                    continue
                if s[i][j] == '.' or s[x][y] == '#':
                    scores[i][j] = min(scores[i][j], scores[x][y])
                else:
                    scores[i][j] = min(scores[i][j], scores[x][y] + 1)

    return scores[H - 1][W - 1]

if __name__ == '__main__':
    H, W = map(int, input().split())
    s = []
    for _ in range(H):
        s.append(list(input()))

    print(solve(H, W, s))
```
### B問題
#### 003 - Simplified mahjong
##### コード1. 貪欲法
$time: O(N)$
$space: O(1)$

```python
def solve(N, A):
    ret = 0
    for idx in range(N):
        ret += A[idx] // 2
        A[idx] %= 2
        if A[idx] and idx + 1 < N and A[idx + 1]:
            ret += 1
            A[idx + 1] -= 1
    return ret

if __name__ == "__main__":
    N = int(input())
    A = [0 for _ in range(N)]
    for idx in range(N):
        A[idx] = int(input())
    print(solve(N, A))
```

## その他
### B問題
#### キーエンスプログラミングコンテスト2020 - Robot Arms
##### コード1. 区間スケジューリング
$time: O(N)$
$sapce: O(1)$

```python
def solve(N, data):
   ret = N
   data.sort(key=lambda x: x[0] - x[1])
   most_right = float("-inf")
   for idx, d in enumerate(data):
       l, r = d[0] - d[1], d[0] + d[1]
       if not idx or most_right <= l:
           most_right = r
           continue
       ret -= 1
       most_right = min(r, most_right)
   return ret

if __name__ == "__main__":
    N = int(input())
    data = []

    for _ in range(N):
        data.append(list(map(int, input().split())))
    print(solve(N, data))
```

#### 第二回全国統一プログラミング王決定戦予選
##### コード1. 数え上げ
$time: O(N)$
$sapce: O(N)$

```python
MOD = 998244353

def solve():
    if D[0] != 0 or 0 in D[1:]:
        print(0)
        return

    tree_dict = dict()
    max_dist = 0
    for idx, dist in enumerate(D):
        tree_dict[dist] = tree_dict.get(dist, 0) + 1
        max_dist = max(max_dist, dist)
    ret = 1

    for dist in range(max_dist + 1):
        if not dist in tree_dict:
            print(0)
            return
        ret = (ret * pow(tree_dict.get(dist - 1, 1), tree_dict[dist])) % MOD
    print(ret)

if __name__ == "__main__":
    N = int(input())
    D = list(map(int, input().split()))
    solve()
```

### C問題
#### SoundHound Inc. Programming Contest 2018 - Ordinary Beauty

僕にとっては全くの初見知識が問われていました。$d = 1$での$O(m)$の解法は思いつくも、そこから一般化して高速化出来なかったです。

##### コード1. 期待値の線形性
[「期待値の線型性」についての解説と、それを用いる問題のまとめ](https://qiita.com/drken/items/3fe1613c44de1f3bfbe1)
$time: O(1)$
$sapce: O(1)$

```python
def solve(n, m, d):
    return (m - 1) * 2 * (n - d) / n**2 if d else (m - 1) / n

if __name__ == "__main__":
    n, m, d = map(int, input().split())
    print(solve(n, m, d))
```

#### DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 - Strawberry Cakes

実装かなり悩みました。

##### コード1. イテレート
$time: O(HW)$
$sapce: O(HW)$

```python
import numpy as np

def solve():
    ret = np.array([[1 for _ in range(W)] for _ in range(H)])
    row_groups = np.array([0 for _ in range(H)])
    row_group_set = set()
    prev_row = 0
    for row in range(H):
        if '#' in s[row]:
            row_groups[prev_row: row + 1] = row
            row_group_set.add(row)
            prev_row = row + 1
    row_groups[prev_row: ] = prev_row - 1

    cur_group_num = 1
    for row in row_group_set:
        prev_col = 0
        for col in range(W):
            if s[row][col] == '#':
                ret[row][prev_col: col + 1] = cur_group_num
                cur_group_num += 1
                prev_col = col + 1
            ret[row][prev_col: ] = cur_group_num - 1

    for row, row_group_num in enumerate(row_groups):
        if row in row_group_set:
            continue
        for col in range(W):
            ret[row][col] = ret[row_group_num][col]

    for row in ret:
        print(' '.join(map(str, row.tolist())))

if __name__ == "__main__":
    H, W, K = map(int, input().split())
    s = []
    for row in range(H):
        s.append(list(input()))
    solve()
```

### D問題
#### 三井住友信託銀行プログラミングコンテスト2019 - Lucky PIN
##### コード1. イテレート ＋ 辞書
$time: O(100\ N)$
$sapce: O(100\ N)$
$100\ N \leq 3\times 10^6$

```python
import copy
def solve(N, S):
    single_ref = [False for _ in range(10)]
    double_ref = [{} for _ in range(N)]

    for i in range(N - 1, -1, -1):
        if i == N - 1:
            single_ref[int(S[i])] = True
            continue
        double_ref[i] = copy.deepcopy(double_ref[i + 1])
        for j in range(10):
            if not single_ref[j]:
                continue
            double_ref[i][S[i] + str(j)] = 1
        single_ref[int(S[i])] = True

    ret = {}
    for i in range(N - 1):
        for k in double_ref[i + 1].keys():
            ret[S[i] + k] = 1
    return len(ret.keys())

if __name__ == "__main__":
    N = int(input())
    S = input()
    print(solve(N, S))
```


#### パナソニックプログラミングコンテスト2020 - String Equivalence
##### コード1. DFS


```python
def dfs(s, mx):
    if len(s) == N:
        print(s)
        return
    for c in range(ord("a"), mx + 1):
        dfs(s + chr(c), mx + 1 if c == mx else mx)

if __name__ == "__main__":
    N = int(input())
    dfs("", ord("a"))
```
### E問題 - Colorful Hats 2
#### 三井住友信託銀行プログラミングコンテスト2019
##### コード1. イテレート
$time: O(N)$
$space: O(N)$

```python
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def solve(N, A):
    ret = ModInt(1)
    count = [3 if not i else 0 for i in range(N + 1)]

    for a in A:
        ret *= count[a]
        if not ret:
            break
        count[a] -= 1
        count[a + 1] += 1

    return ret

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))
```