ABC310をPythonで解いてみたよ。(A～E問題)

[AtCoder Beginners Contest 310 (ABC310)](https://atcoder.jp/contests/abc310) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。

# A - Order Something Else

## 問題ページ
https://atcoder.jp/contests/abc310/tasks/abc310_a

## 考察
支払う方法は次の2つです。
- $P$ 円だけ払う
- $Q$ 円払って、さらにリスト $D$ の中で最も安いものを買う

これをそのまま実装します。
min(D) ← これでリスト内の最小値を持ってきてくれて便利です！

## コード
```Python
N, P, Q = map(int, input().split())
D = list(map(int, input().split()))

ans = min(P, Q + min(D))
print(ans)

```
# B - Strictly Superior

## 問題ページ
https://atcoder.jp/contests/abc310/tasks/abc310_b

## 考察
問題文はごちゃごちゃ書いていますが、B問題までならだいたい書いてあることを愚直に実装できればOKなことが多いです。
具体的なことは、下のコードを参考にしてください。

<details> <summary>下のコードの入力受け取りについて</summary>

入力の受け取りでは、次のコードを書いています。
```Python
p, c, *f = map(int, input().split())
```
このコードは、次のように動きます。
```Python
T = [10, 30, 70, 4, -15]
p, c, *f = T
print(p)  # 10
print(c)  # 30
print(f)  # [70, 4, -15]
```
これを知っていると、たまにつかえてラクできます！

</details>

## コード
```Python
N, M = map(int, input().split())

P = []  # P[i]: 商品iの値段
F = []  # F[i]: 商品iの機能のセット
for _ in range(N):
    p, c, *f = map(int, input().split())
    P.append(p)
    se = set()
    for el in f:
        se.add(el)
    F.append(se)

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        # 1つ目の条件
        if P[i] < P[j]:
            continue
        
        # 2つ目の条件
        is_ok = True
        for el in F[i]:
            if el not in F[j]:
                is_ok = False
        if not is_ok:
            continue

        # 3つ目の条件
        if P[i] > P[j]:
            print("Yes")
            exit()
        for el in F[j]:
            if el not in F[i]:
                print("Yes")
                exit()

print("No")

```
# C - Reversible

## 問題ページ
https://atcoder.jp/contests/abc310/tasks/abc310_c

## 考察
反転させたものも同じものとみなすのが、難しいポイントです。
まずセットを用意します。文字列を順番に見ていって、「その文字列 $S$と反転させた文字列 $T$ がどちらもセットに入っていなければ、セットに今見ている文字列を入れる。」の操作を繰り返すことでACできます。
また、文字列の反転は次のコードで書けます。
```Python
T = S[::-1]
```

## コード
```Python
N = int(input())

se = set()
for _ in range(N):
    S = input()
    T = S[::-1]
    if S in se or T in se:
        continue
    else:
        se.add(S)
print(len(se))

```
# D - Peaceful Teams

## 問題ページ
https://atcoder.jp/contests/abc310/tasks/abc310_d

## 考察
再帰関数で解きます。
再帰関数をつかうときは、以下のコードをそのまま先頭に貼り付けます。
```python
import sys
import pypyjit

sys.setrecursionlimit(10**7)
pypyjit.set_param('max_unroll_recursion=-1')
```
setrecursionlimitは再帰の回数を引き上げるメソッドで、なにもしないとPythonは $1000$ 回が再帰の上限なので、それを $10^7$ 回にしています。
もう片方のはpypyで再帰がはやくなるおまじないらしくて、まだ私もよくわかっていないです。(すみません...)

各チームをリストだと思うことにします。つまり、
$[[チーム1], [チーム2], ..., [チームT]]$
みたいに管理していきます。

ただし、 $[[1, 2], [3, 4]]$ と $[[3,4],[2,1]]$ のように、順番が違うだけのものは一緒のものとして扱います。

具体的には、次のように解きます。
- 関数 $f(v, lis)$ を用意します。これは、今から選手 $v$ をチームに入れようとしていて、チームの状況が $lis$ であることを表しています。
- チーム1から順番に選手 $v$ が入れるかどうかを見ていきます。もし選手 $v$ がそのチームに入れるなら、そのチームに選手 $v$ を加入させた新たなチームの状況 $nlis$ を用意して、 $f(v+1, nlis)$ を解くことにします。
- ただし、今から入ろうとしているチームの人数が0人だったとき、加入させたうえで、それ以降のチームに関しては入れるかどうかを見ずに打ち切ります。順番が違うだけのものは一緒のものとして扱われるからです。
- こうして $N$ 人をみんなチームに入れたら、チーム $T$ に誰か所属しているのを確認して、変数 $ans$ を $1$ だけ増やします。チーム $T$ に誰も所属していなかったら、それはチーム数が $T-1$ になってしまっているのでカウントしません。



## コード
```Python
import sys
import pypyjit

sys.setrecursionlimit(10**7)
pypyjit.set_param('max_unroll_recursion=-1')

N, T, M = map(int, input().split())

C = set()
for _ in range(M):
    a, b = map(int, input().split())
    C.add((a - 1, b - 1))
    C.add((b - 1, a - 1))

ans = 0


def f(v, lis):
    if v == N:
        # チーム数がT未満なら、答えにはカウントしない。
        if len(lis[-1]) == 0:
            return

        global ans
        ans += 1
        return

    for i in range(T):
        nlis = [a[:] for a in lis]  # lisのコピー
        if len(nlis[i]) == 0:
            nlis[i].append(v)
            f(v + 1, nlis)
            break

        is_ok = True  # 相性の悪い選手がチームにいればFalse
        for v2 in nlis[i]:
            if (v, v2) in C:
                is_ok = False
        if is_ok:
            nlis[i].append(v)
            f(v + 1, nlis)


f(0, [[] for _ in range(T)])
print(ans)

```

## 類題
[ABC236-D Dance](https://atcoder.jp/contests/abc236/tasks/abc236_d)

# E - NAND repeatedly

## 問題ページ
https://atcoder.jp/contests/abc310/tasks/abc310_e

## 考察
動的計画法DPで解きます。
例えば $N=3$ だったとして、すべての $f(l,r)$ の値が分かっているとします。
このときの数列の末尾に $0$ か $1$ を追加したときに、答えがどう変わるかを考えます。
答えには $f(1,4)+f(2,4)+f(3,4)+f(4,4)$ を足すことになります。
$f(1,4)=f(1,3)　\bar\wedge　A_4$
$f(2,4)=f(2,3)　\bar\wedge　A_4$
$f(3,4)=f(3,3)　\bar\wedge　A_4$
( $f(4,4)=A_4$ )
です。こうしていちいち計算していると計算量が $O(N^2)$ でTLEしちゃいます。
上の例だと、 $f(1,3)$ ～ $f(3,3)$ の中で $0$ と $1$ の数が分かっていると、$O(N)$ で計算できます。

$dp[i][num]$: $f(1,i)$ ～ $f(i,i)$ の中で値が $num$ の個数
として、$N=1$ のときの問題から順番に $N=2, N=3, ...$ と解いていくことで答えが求められます。


## コード
```Python
def NAND(x, y):
    if x == y == 1:
        return 0
    return 1


N = int(input())
S = input()

dp = [[0] * 2 for _ in range(N + 1)]

for i, ss in enumerate(S):
    s = int(ss)
    dp[i + 1][NAND(s, 0)] += dp[i][0]
    dp[i + 1][NAND(s, 1)] += dp[i][1]
    dp[i + 1][s] += 1

ans = 0
for i in range(N + 1):
    ans += dp[i][1]
print(ans)

```