[ABC407] ABC 407(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# [ABC407] ABC 407(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# A問題
- 切り捨て `ceil` と切り上げ `floor` を求める。
- `real` と差分が近い方を答えとする。
```A.py
"""
<方針>
- 切り捨て `ceil` と切り上げ `floor` を求める。
- `real` と差分が近い方を答えとする。
"""
# 入力
A, B = map(int, input().split())

# A/Bを計算
real = A/B

# 切り上げを計算
ceil = (A+B-1)//B

# 切り捨てを計算
floor = A//B

# 切り上げのほうが差分が小さいとき、
if((ceil - real) < (real - floor)):
  print(ceil)
# 切り捨てのほうが差分が小さいとき、
else:
  print(floor)
```

# B問題
- 余事象を考える。
  - `6x6` の全部の出目を考えて、`notX` かつ `notY` となる回数を数える。
  - `36` からそれらを引けば良い。
- あとは `36` で割れば良い。
```B.py
"""
<方針>
- 余事象を考える。
  - `6x6` の全部の出目を考えて、`notX` かつ `notY` となる回数を数える。
  - `36` からそれらを引けば良い。
- あとは `36` で割れば良い。
"""
# 入力
X, Y = map(int, input().split())

# 余事象の数
notXY = 0

# 6x6パターンを考える。
for i in range(1, 7):
  for j in range(1, 7):
    # not X かつ not Y
    if( 
      not (X <=i+j) and 
      not (Y <= abs(i-j))
      ):
      notXY += 1

# 求めたい方に変える。
XY = 36-notXY

# 確率を求める。
ans = XY/36

# 出力
print(ans)
```

# C問題
## 方針
- 文字列を後ろから見ていき、`0` になるまで、`A` ボタンを押し、`0` になったら `B` ボタンを押して、次の文字をみれば良いと思う。
- だけど、`N = len(S)` とし、`B` ボタンの操作（毎回全ての文字列 `t` を書き換える）をすると、`O(N^2)` みたいになっちゃう。
- そこで、どれだけ今まで `A` ボタンを押したかを記録しておけば、毎回前方の文字を操作しなくてもいいよね。
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 文字列を後ろから見ていき、`0` になるまで、`A` ボタンを押し、`0` になったら `B` ボタンを押して、次の文字をみれば良いと思う。
- だけど、`N = len(S)` とし、`B` ボタンの操作（毎回全ての文字列 `t` を書き換える）をすると、`O(N^2)` みたいになっちゃう。
- そこで、どれだけ今まで `A` ボタンを押したかを記録しておけば、毎回前方の文字を操作しなくてもいいよね。
"""
# [s_1, s_2, ..., s_N] を数字として受け取る
S = list(map(int, list(input())))

cntA = 0
cntB = 0
# 後ろから見ていく。
for s in reversed(S):
  # 今まで押したボタンBの回数を反映させた上で、必要か回数を登録する。
  cntB += (s - cntB)%10
  # `0` になったので、ボタンAを押す。
  cntA += 1

# 出力
print(cntA+cntB)
```

# D問題
- ドミノで隠せる全パターンを考えて最適解を出力すれば良さそう。
- `Python` なので、非再帰 `DFS` で実装しよう。
  - `q` に、それぞれのマスにドミノを縦に置く `-1` と横に置く `+1` と置かない `0` を格納して考える。
- `bit` 演算は `^=` で簡単に求まるよ。
```D.py
"""
<方針>
- ドミノで隠せる全パターンを考えて最適解を出力すれば良さそう。
- `Python` なので、非再帰 `DFS` で実装しよう。
  - `q` に、それぞれのマスにドミノを縦に置く `-1` と横に置く `+1` と置かない `0` を格納して考える。
- `bit` 演算は `^=` で簡単に求まるよ。
"""
# 入力
H, W = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(H)]

# 最大値
ans = 0

# 非再帰キュー
q = []

# 初期値を登録
q.append([0])
if(H > 1):
  q.append([-1])
if(W > 1):
  q.append([+1])

# 非再帰
while q:
  B = q.pop() # DFS
  
  # それぞれのマスが隠されていると `1` が格納される。
  table = [[0]*W for _ in range(H)]
  # ドミノで盤面を隠す
  for i, b in enumerate(B):
    if(b != 0):
      h, w = divmod(i, W)
      table[h][w] += 1
      if(b == -1):
        table[h+1][w] += 1
      if(b == +1):
        table[h][w+1] += 1
  
  # まだ、全ての位置にドミノを置くかどうか決まってない時、
  if(i < H*W):
    # 次のマスでドミノを置かない
    q.append(B+[0])
    
    h, w = divmod(i+1, W)
    
    if(w+0 < W and h+1 < H and table[h][w] == table[h+1][w] == 0):
      # 次のマスでドミノを縦に置く
      q.append(B+[-1])
    
    if(w+1 < W and h+0 < H and table[h][w] == table[h][w+1] == 0):
      # 次のマスでドミノを横に置く
      q.append(B+[+1])
  # 全てのマスにドミノを置くかどうか決まった時、
  else:
    tmp = 0 # 解
    for h in range(H):
      for w in range(W):
        # ドミノで隠れてない時、
        if(table[h][w] == 0):
          # 排他的論理和
          tmp ^= AA[h][w]
    
    # 更新
    ans = max(ans, tmp)

# 出力
print(ans)
```

# E問題
- 貪欲に行こう。
- 右から `parentheses` をペアで追加して、その際、左にある任意の `)` の中で最大値と取り換えればいけそう。
- 最大値の保持には `heapq` を使えば、`logN` なので、多分 `O(NlogN)` でいけそう。
```E.py
"""
<方針>
- 貪欲に行こう。
- 右から `parentheses` をペアで追加して、その際、左にある任意の `)` の中で最大値と取り換えればいけそう。
- 最大値の保持には `heapq` を使えば、`logN` なので、多分 `O(NlogN)` でいけそう。
"""
import heapq
T = int(input())

for _ in range(T):
  q = []
  N = int(input())
  ans = 0 # 解
  for i in range(N):
    a1 = int(input())
    a2 = int(input())
    
    # 新入りのカッコの左について検討する。
    # キューがある時は、
    if(q):
      # 最大値を取得する。
      x = -heapq.heappop(q)
      # 新入りの方が値が大きい時、
      if(x < a1):
        # キューを戻す。
        heapq.heappush(q, -x)
        # 新入りを答えに記入する。
        ans += a1
      # キューの方が大きい値が格納されている時、
      else:
        # 新入りをキューに入れる。
        heapq.heappush(q, -a1)
        # キューの最大値を答えに記入する。
        ans += x
    # まだキューが空の時は、
    else:
      # 新入りを答えに記入する。
      ans += a1
    # 新入りのカッコの右については必ずキューに格納する。
    heapq.heappush(q, -a2)
  print(ans)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc407)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc407/submissions/66100273)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc407/submissions/66178238)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc407/submissions/66178738)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc407/submissions/66179414)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc407/submissions/66179628)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- My Thoughts When Solving the Problem C
    - いいや!「限界」だッ!押すねッ! 『今だッ』!