ABC365(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# ABC365(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# A問題
- `Y` を数字で受け取る．
- 順番に `if-else` で条件分岐をする．
```A.py
"""
<方針>
- `Y` を数字で受け取る．
- 順番に `if-else` で条件分岐をする．
"""
# Yを数値で受け取る．
Y = int(input())

# Yが4の倍数で無い
if(Y%4 != 0):
  print(365)
# Yが4の倍数だが，100の倍数で無い
elif(Y%4==0 and Y%100 != 0):
  print(366)
# Yが100の倍数だが，400の倍数で無い
elif(Y%100 == 0 and Y%400 != 0):
  print(365)
# Yが400の倍数
elif(Y%400 == 0):
  print(366)

```

# B問題
- `A` をソートしたもの `B` を用意する．
- 二番目に大きい値は， `B[-2]` である．
- `A` を順番に見ていき， 値が `B[-2]` と一緒になった時に， `0-indexed` に注意して， `i+1` を出力し， `exit` 関数でプログラムを終了する．
```B.py
"""
<方針>
- `A` をソートしたもの `B` を用意する．
- 二番目に大きい値は， `B[-2]` である．
- `A` を順番に見ていき， 値が `B[-2]` と一緒になった時に， `0-indexed` に注意して， `i+1` を出力し， `exit` 関数でプログラムを終了する．
"""
# 標準入力を受け取る．
N = int(input())
A = list(map(int, input().split()))

# AをソートしたBを用意する(Aの順番はそのまま)．
B = sorted(A)

# Aを順番にみる．
for i in range(N):
  # 値が二番目に大きい値と一致した時，
  if(A[i]==B[-2]):
    # i+1を出力する．
    print(i+1)
    # プログラムを終了する．
    exit()
```

# C問題
## 方針
- `M` が大きすぎるので， `M` を一つずつみるのは不可能．だから， `M` で二分探索をしよう．
- 支払う金額を確認するのに， `O(N)` である．
- つまり，計算量は `O(NlogM)` となり，十分間に合う．
- 高橋くんが `MAX` まで払えたら， `infinite` と出力すれば良い．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `M` が大きすぎるので， `M` を一つずつみるのは不可能．だから， `M` で二分探索をしよう．
- 支払う金額を確認するのに， `O(N)` である．
- つまり，計算量は `O(NlogM)` となり，十分間に合う．
- 高橋くんが `MAX` まで払えたら， `infinite` と出力すれば良い．
"""
# 標準入力
N, M = map(int, input().split())
A = list(map(int, input().split()))

# Mの想定よりも大きい値
MAX = 2*10**14 + 1

# めぐる式二分探索
ok = 0
ng = MAX + 1
while ng - ok > 1:
  # 高橋くんが設定する補助額
  mid = (ng+ok)//2
  
  # みんなに支払う総額を計算
  cost = 0
  for i in range(N):
    if(A[i] < mid):
      cost += A[i]
    else:
      cost += mid
  
  # 高橋くんは払い切れるよ．
  if(cost<=M):
    ok = mid
  # 高橋くんは払えないよ．
  else:
    ng = mid


if(ok == MAX):
  # 何円にでも設定できる．
  print("infinite")
else:
  print(ok)
```

# D問題
- `dp` で一個前に何を出したかを記録してやればできる．

```D.py
"""
<方針>
- `dp` で一個前に何を出したかを記録してやればできる．
"""
# 入力
N = int(input())
S = input()

# dp[i][j]: i回目に自分がjを出した時に勝った回数の最大値
dp = [{"R": 0, "S": 0, "P": 0} for _ in range(N+1)]

for i in range(N):
  s = S[i]
  
  # 相手がRのとき，
  if(s=="R"):
    # 自分がRを出せば引き分ける．
    dp[i+1]["R"] = max(dp[i]["S"], dp[i]["P"])
    # 自分がPを出せば勝てる
    dp[i+1]["P"] = max(dp[i]["R"], dp[i]["S"]) + 1
  
  # 同上
  if(s=="S"):
    dp[i+1]["S"] = max(dp[i]["R"], dp[i]["P"])
    dp[i+1]["R"] = max(dp[i]["P"], dp[i]["S"]) + 1
  
  # 同上
  if(s=="P"):
    dp[i+1]["P"] = max(dp[i]["S"], dp[i]["R"])
    dp[i+1]["S"] = max(dp[i]["R"], dp[i]["P"]) + 1

# 最後はどの手にしたら一番勝てたかな．
print(max(dp[N].values()))
```

# E問題
- ユーザー解説と一緒です．
```E.py
"""
- ユーザー解説と一緒です．
"""
N = int(input())
A = list(map(int, input().split()))

ans = 0
# Aでありえるbitの2**K > 10**8
K = 27

# XORは桁ごとで考えれば十分
for i in range(K):
  # dp[i][j]: 区間 [0, i] までの長さ1~i+1までの全ての区間におけるxorした結果，j となる個数．
  dp = [[0]*2 for _ in range(N)]
  
  # A[0]のibit目の値
  a = int(bool(A[0]&1<<i))
  # 初期値を設定
  dp[0][a] = 1
  
  for j in range(N-1):
    # A[j+1]のibit目の値
    a = int(bool(A[j+1]&1<<i))
    dp[j+1][0] = dp[j][a] +  (a^1) # 演算子の順序的に，()で括らないとだめ．
    dp[j+1][1] = dp[j][a^1] + a
    
  # i桁のみに注意した時の答え．
  tmp = sum(map(lambda x: x[1], dp))
  
  # 本問題では，自身のxorは除くため．
  tmp -= sum([int(bool(a&1<<i)) for a in A])
  
  # i桁目なので，2**i倍してる．
  tmp <<= i
  
  ans += tmp
  
print(ans)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc365)
- [E問題の公式解説](https://atcoder.jp/contests/abc365/editorial/10588)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(oooox--)](https://atcoder.jp/users/mattsunkun/history/share/abc365)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc365/submissions/56408057)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc365/submissions/56408111)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc365/submissions/56408347)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc365/submissions/56408494)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc365/submissions/56407949)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 明日は院試です．．．頑張ってきます．．．
- 院試前に何やってんだろ．．．