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

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

https://atcoder.jp/contests/abc354


# A - Exponential Plant

## 問題
植物があります。 $0$ 日目の時点で高さは $0 \mathrm{cm}$です。
この植物は $i$ ( $0 \le i$ ) 日目の夜に ${2^i} \mathrm{cm}$ だけ伸びます。
毎日お昼に植物の高さを測定します。
この植物が $H \mathrm{cm}$ を超えたのを観測するのは何日目ですか？

https://atcoder.jp/contests/abc354/tasks/abc354_a

## 考察
$i$ 日目のお昼で植物の高さが $H$ 以下のとき、植物の高さを $2^i$ だけ増やして $i+1$ 日目のお昼の観測に移ります。

似たような処理の繰り返しなので、for文やwhile文をつかって解くことができます。

Pythonでは、累乗は以下のように書けます。

```Python
"""累乗の書き方"""
# どっちをつかってもok！
x = 3**4  # 81(=3^4)
y = pow(5, 3)  # 125(=5^3)
```

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

i = 0
plant_height = 0
while plant_height <= H:
    plant_height += 2**i
    i += 1
print(i)
```

## 別解

<details><summary>for文をつかった解法</summary>

```Python
H = int(input())

plant_height = 0
for i in range(100):
    if plant_height > H:
        print(i)
        break
    plant_height += 2**i
```

</details>

<details><summary>累乗の書き方(pow関数)</summary>

$3^4(=81)$ を表したいとき、 `x = 3**4` のように書きます。

もう1つ有名な書き方があって、 `x = pow(3, 4)` と書いても $3^4$ を表せます。

```Python
"""pow関数のつかい方"""
x = pow(3, 4)  # 81(3^4)
y = pow(5, 4)  # 123(=5^3)

# 第3引数に値を入れられる。第3引数で割ったあまりを求められる
a = pow(3, 4, 7)  # 4(81÷7のあまり)
b = pow(7, 3, 4)  # 3(343÷4のあまり)
```

第3引数を設定したとき、内部では繰り上がり二乗法という手法で累乗の計算をしています。

これによる高速化をつかう問題も多く、気になる方は調べてみてもいいかもしれません。

</details>



# B - AtCoder Janken 2

## 問題
$N$ 人のAtCoderユーザーがいます。 $i$ 人目のユーザーは名前が $S_i$ でレート $C_i$ です。

以下のルールで勝負をしたとき、勝者は誰になりますか？

- それぞれのユーザーに、ユーザー名の辞書順に $0,1,…,N−1$ の番号を割り当てる
- $N$ 人のレートの総和を $T$ とする。番号 $T \mod N$ を割り当てられたユーザーが勝者となる

https://atcoder.jp/contests/abc354/tasks/abc354_b

## 考察

まず、1つ目の条件「ユーザー名の辞書順に $0,1,…,N−1$ の番号を割り当てる」を処理します。
辞書順に並べるということは、Python的に言うと「ソートする」ということです。

つまり、こういう感じ。

```Python
# 入力の受け取り
N = int(input())
user_array = []
for _ in range(N):
    s, c = input().split()
    user_array.append((s, int(c)))

user_array.sort()  # 辞書順にユーザーを並べる
```

そして2つ目の条件「 $N$ 人のレートの総和を $T$ とする。番号 $T \mod N$ を割り当てられたユーザーが勝者となる」です。

条件の文自体は短いですが、見た目以上に処理することは多いです。条件の通りに実装してみると、こんな感じになります。

```Python
T = 0  # 全ユーザーのレーティングの総和
for user in user_array:
    _name, rating = user
    T += rating

winner_index = T % N
winner = user_array[winner_index]
winner_name = winner[0]
print(winner_name)
```

これらをまとめると、以下のコードになります。

## コード
```Python
N = int(input())
user_array = []
for _ in range(N):
    s, c = input().split()
    user_array.append((s, int(c)))

user_array.sort()
T = 0
for user in user_array:
    _name, rating = user
    T += rating
winner_index = T % N
winner = user_array[winner_index]
winner_name = winner[0]
print(winner_name)
```

## 別解

<details><summary>sum関数+内包表記 の書き方</summary>

レーティングの総和 $T$ を求めたコードを再掲します。

```Python
T = 0
for user in user_array:
    _name, rating = user
    T += rating
```

これは、sum関数と内包表記を合わせて以下のように書けます。

```Python
T = sum(user[1] for user in user_array)
```

簡単に書けるので、余裕のある方は積極的につかってみてもいいかもしれません。

</details>


# C - AtCoder Magics

## 問題
$N$ 枚のカードがあります。 $i$ 枚目のカードはコスト $C_i$ で強さ $A_i$ です。
$A_x \lt A_y, \enspace C_x \gt C_y$ を満たす $(x, y)$ の組があれば、カード $x$ を捨てます。
この操作をできるまで続けます。残ったカードはどれですか？


https://atcoder.jp/contests/abc354/tasks/abc354_c

## 考察1 (問題文通りに解いてみる)

すべてのカードの組をチェックしてみます。コードはこんな感じでしょうか。

```Python
N = int(input())
card_array = []
for i in range(1, N + 1):
    a, c = map(int, input().split())
    card_array.append((c, a, i))

discard_set = set()  # 捨てる予定のカード番号を格納するset
for i in range(N - 1):
    for j in range(i + 1, N):
        ai, ci, ni = card_array[i]
        aj, cj, nj = card_array[j]
        if ai < aj and ci > cj:
            discard_set.add(i)
# (出力は省略)            
```

2重ループの部分が計算量的にかなり重く、全体として $O(N^2)$ の処理です。
制約を見てみると、 $2 \le N \le 2 \times 10^5$ なので、これは実行時間制限に間に合いません。

素直にカードの組み合わせを全パターン試すのはダメだと分かりました。

## 考察2 (カードを事前に並べる)

条件がいくつかあって、その中に $C_i \lt C_j$ のような不等式が含まれているような問題はAtCoderでよく出題されます。
このような問題では、事前に $C$ の順番にオブジェクト(今回はカード)を並べて置くと、計算量を改善できることがあります。
(もっと気になる人は、「平面捜査」で調べてみるといいかもです！)

ということで、カードを捨てるかどうかチェックしていく前に、事前にコストの順にカードを並び替えておきます。

コストの小さいほうから順にカードを見ていきます。
捨てなかった直前のカード $i$ と現在見ているカード $j$ を比べます。
コストの順に並べてあるので、 $C_i \lt C_j$ が成り立ちます。
したがって、 $A_i \gt A_j$ であれば、カード $j$ は破棄することになります。

この処理はカードを1枚ずつ見ているだけで計算量は $O(N)$ です。

事前にコストの順にソートするところで $O(N \log N)$ だけかかっていて、問題全体としては計算量 $O(N \log N)$ でこの問題を解けます。


## コード
```Python
N = int(input())
card_array = []
for i in range(1, N + 1):
    a, c = map(int, input().split())
    card_array.append((c, a, i))

card_array.sort()
ans_lst = []
max_power = -1
for card in card_array:
    cost, power, card_number = card
    if max_power < power:
        max_power = power
        ans_lst.append(card_number)

ans_lst.sort()
print(len(ans_lst))
print(*ans_lst)
```

# D - AtCoder Wallpaper

## 問題

問題の図形について、左下の座標が $(A, B)$ 右上の座標が $(C, D)$ の長方形に含まれる黒色の部分の面積はいくつですか？

https://atcoder.jp/contests/abc354/tasks/abc354_d

## 考察1 (規則性を見つける)

問題の図形は下の通りです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2469270/4dc3318e-05ff-1300-cfb2-64f8035ad421.png)

図をじっくり見てみると、 $0 \le x \le 1$ の部分と $4 \le x \le 5$ の部分は、まったく同じ図形なことがわかります。
ほかにも同じ構造になっているところはたくさんあります。
一般化すると、 $a \le x \le a + 1$ の部分と $a + 4 \le x \le a + 5$ の部分はまったく同じになります。

## 考察2 ([0, 1] の範囲だけを考える)

(問題では面積を $2$ 倍した数値を出力すると書かれていますが、この解説では面積を $2$ 倍された数値のことを単に「面積」と呼ぶことにします)

先ほどの規則性から、どの $a \le x \le a+1$ を選んでも $0 \le x \le 1,\enspace 1 \le x \le 2,\enspace 2 \le x \le 3,\enspace 3 \le x \le 4 $ の $4$ つのどれかと同じ図形になっていることが分かります。

ここではいったん $0 \le x \le 1$ の範囲だけ考えてみます。
たとえば、$0 \le x \le 1, \enspace 0 \le y \le 6$ の赤枠の範囲を考えてみます。 

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2469270/8c9d6f4a-5882-39f0-1b26-b444072ae324.png)

これなら、答えは $9$ になります。
$0 \le y \le 2$ の範囲にある台形1つで面積は $3$ で、それが計 $3$ つある形です。
$0 \le y \le 6$ だったのを $-1 \le y \le 5$ にしてみるとどうでしょうか？

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2469270/ec6fe407-8161-73b5-7987-c19d62b74a34.png)

これも答えは $9$ です。

$y$ の長さが偶数の時の処理は上記の通りです。

次は $y$ の長さが奇数のときを考えます。
図も多くなるので省略しますが、 $0 \le y \le 5$ や $-1 \le y \le 4$ のときにどうなるかを考えてみるといいでしょう。

これをまとめると、以下のような関数になります。

```Python
# 0<=x<=1, bottom<=y<=top 黒色の面積
def black_area0(bottom, top):
    length = top - bottom
    if length % 2 == 0:
        return length // 2 * 3
    else:
        result = (length - 1) // 2 * 3
        if bottom % 2 == 0:
            result += 2
        else:
            result += 1
        return result
```

## 考察3 (残り3パターンも考える)

(図形を再掲)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2469270/4dc3318e-05ff-1300-cfb2-64f8035ad421.png)

まず $1 \le x \le 2$ について考えます。

$1 \le x \le 2, \enspace a \le y \le b$ の範囲の黒色の面積と、 $0 \le x \le 1, \enspace a - 1 \le y \le b - 1$ の範囲の黒色の面積は、同じになります。

この性質を使うと、以下のように関数をつくれます。

```Python
# 1<=x<=2, bottom<=y<=top 黒色の面積
def black_area1(bottom, top):
    return black_area0(bottom - 1, top - 1)
```

$2 \le x \le 3$ の範囲については、 $0 \le x \le 1$ と比べて黒白が逆転しているだけです。
$3 \le x \le 4$ と $1 \le x \le 2$ の関係も同じです。

次のように関数をつくれます。

```Python
# 2<=x<=3, bottom<=y<=top 黒色の面積
def black_area2(bottom, top):
    return (top - bottom) * 2 - black_area0(bottom, top)


# 3<=x<=4, bottom<=y<=top 黒色の面積
def black_area3(bottom, top):
    return (top - bottom) * 2 - black_area1(bottom, top)
```

## 考察4 (各関数を使う回数)

ここまでで、 $0 \le x \le 1,\enspace 1 \le x \le 2,\enspace 2 \le x \le 3,\enspace 3 \le x \le 4 $ それぞれについて、 $y$ の範囲が分かれば $O(1)$ で面積を求められるようになっています。

あとは、それぞれの図形が何度出現するのかが分かればいいです。

言い換えると、以下のような問題を解くことになります。

> - $\cdots , -4 \le x \le -3, \enspace 0 \le x \le 1, \enspace 4 \le x \le 5, \cdots$ の範囲に1つずつ旗が置いてあります
> - $A \le x \le C$ の範囲の中に旗はいくつありますか？

( $1 \le x \le 2,\enspace 2 \le x \le 3,\enspace 3 \le x \le 4 $ についても同様の問題を解きます)

解説は省きますが、$\cdots , -4 \le x \le -3, \enspace 0 \le x \le 1, \enspace 4 \le x \le 5, \cdots$  の範囲の小問題については、 $\left\lfloor\frac{C - 1}{4}\right\rfloor - \left\lceil\frac{A}{4}\right\rceil + 1$ が答えになります。
(類題: [ABC334-B Christmas Trees](https://atcoder.jp/contests/abc334/tasks/abc334_b)) 

他3つの範囲については、 $x$ 軸方向にシフトして考えることで同様に解くことができます。


## コード
```Python
# 0<=x<=1, bottom<=y<=top 黒色の面積
def black_area0(bottom, top):
    length = top - bottom
    if length % 2 == 0:
        return length // 2 * 3
    else:
        result = (length - 1) // 2 * 3
        if bottom % 2 == 0:
            result += 2
        else:
            result += 1
        return result


def black_area1(bottom, top):
    return black_area0(bottom - 1, top - 1)


def black_area2(bottom, top):
    return (top - bottom) * 2 - black_area0(bottom, top)


def black_area3(bottom, top):
    return (top - bottom) * 2 - black_area1(bottom, top)


A, B, C, D = map(int, input().split())

ans = 0
for m in range(4):
    left_idx = (A - m + 3) // 4 
    right_idx = (C - 1 - m) // 4
    cnt = right_idx - left_idx + 1
    match m:
        case 0: ans += black_area0(B, D) * cnt
        case 1: ans += black_area1(B, D) * cnt
        case 2: ans += black_area2(B, D) * cnt
        case 3: ans += black_area3(B, D) * cnt
print(ans)
```
# E - Remove Pairs

## 問題
$N$ 枚のカードがあります。 $i$ 枚目のカードは表に $A_i$ が、裏に $B_i$ が書かれています。
2人ゲームを行います。先手から交互に以下の操作を繰り返します。
- 場にあるカードの中から表面同士に同じ数が書かれている、または裏面同士に同じ数が書かれている $2$ 枚のカードの組を選び、そのカードを場から取り除く。このようなカードの組が存在しない場合、操作を行えない

操作を行えなくなったほうの負けです。両者が最適に行動するとき、どちらが勝ちますか？

https://atcoder.jp/contests/abc354/tasks/abc354_e

## 考察

メモ化再帰で解きます。

場に残っているカードのパターン数は、全部で $2^N$ 通りあります。
今回の問題では $N \le 18$ なので、パターン数自体はそこまで多くありません。

カードを $2$ 枚だけ取り除いてできる盤面の中に後手必勝盤面が存在するとき、その盤面は先手必勝盤面です。
逆にこれ以外の盤面はすべて後手必勝盤面です。
これを利用してメモ化再帰を実装することでACできます。

盤面のパターン数が $O(2^N)$ 個あり、1つの盤面からの遷移は $O(N^2)$ なので、全体として $O(2^N \times N^2)$ で解くことができます。



## コード
```Python
from functools import cache
from itertools import combinations

BitIndexDict = {1 << i: i for i in range(18)}

# 立っている最下位ビットのみを返す
def tail_bit(x):
    return x & -x

# 立っているビットのインデックスiterator
def bits_iter(x):
    v = x
    while v:
        tail = tail_bit(v)
        yield BitIndexDict(tail)
        v ^= tail

@cache
def first_win(state):
    result = False
    card_idxs = list(bits_iter(state))
    for ci, cj in combinations(card_idxs, 2):
        after_state = state ^ (1 << ci) ^ (1 << cj)
        if can_remove(ci, cj) and not first_win(after_state):
            result = True
            break
    return result


# ci, cjのカードのペアを選んで取り出せるか
def can_remove(ci, cj):
    return any(vi == vj for vi, vj in zip(cards[ci], cards[cj]))


N = int(input())
cards = [tuple(map(int, input().split())) for _ in range(N)]

print("Takahashi" if first_win((1 << N) - 1) else "Aoki")

```

## 別解

<details><summary>functools.cache について</summary>

メモ化再帰でつかわれるデコレータとして、 `functools.cache` と `functools.lru_cache` の $2$ つがあります。

`cache` は `lru_cache` のキャッシュ制限を指定しなかったものと同じです。

競プロでキャッシュ制限を使うことはないと思うので、どちらを使用してもよさそうです。

以下は、`functools.cache` の定義が書かれたコードです。そのまま `lru_cache` を呼び出しています。

```Python
################################################################################
### cache -- simplified access to the infinity cache
################################################################################

def cache(user_function, /):
    'Simple lightweight unbounded cache.  Sometimes called "memoize".'
    return lru_cache(maxsize=None)(user_function)
```

[Python公式リファレンス - functools](https://docs.python.org/ja/3/library/functools.html)

</details>