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

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

# A問題
- 高橋くんを黙らせられる状況を考えましょう．
- `B<A<C` という式が成り立てば，高橋くんを黙らせられます．
- では，高橋くんが日を跨いで眠る場合( `C<B` )は， 
  - 日を跨ぐ前に叫ぼうとする( `B<A` )
  - 日を跨いでから叫ぼうとする場合( `A<C` )
- のいずれかが成立する時に，高橋くんを黙らせられます．

```A.py
"""
<方針>
- 高橋くんを黙らせられる状況を考えましょう．
- `B<A<C` という式が成り立てば，高橋くんを黙らせられます．
- では，高橋くんが日を跨いで眠る場合( `C<B` )は， 
  - 日を跨ぐ前に叫ぼうとする( `B<A` )
  - 日を跨いでから叫ぼうとする場合( `A<C` )
- のいずれかが成立する時に，高橋くんを黙らせられます．
"""
# 標準入力を受け取る．
A, B, C = map(int, input().split())

# 日を跨がずに眠る場合
if(B<A<C):
  print("No")
# 日を跨いで眠る場合
elif(C<B and (B<A or A<C)):
  print("No")
# 高橋くんは叫んでしまう．
else:
  print("Yes")
```

# B問題
- `Python` の力で簡単に終わらせましょう．
- `rstrip("0")` は右に `0` が続いているだけ `0` を削除できます．
- `rstrip(".")` は右に `.` が続いているだけ `.` を削除できます．
- せっかくだから俺はこの `ワンライナー回答` を選ぶぜ．
```B.py
"""
<方針>
- `Python` の力で簡単に終わらせましょう．
- `rstrip("0")` は右に `0` が続いているだけ `0` を削除できます．
- `rstrip(".")` は右に `.` が続いているだけ `.` を削除できます．
- せっかくだから俺はこの `ワンライナー回答` を選ぶぜ．
"""
print(input().rstrip("0").rstrip("."))
```

# C問題
## 方針
- `N` も `R` も極端に小さいので， `O(R^N)` で候補( `candidates` )を全て挙げれる．
- 総和が `K` の倍数にならないものを除外して出力すれば良い．
- 列挙には `itertools` を使うとかなり便利．
  - 今回利用する `itertools.product()` に昇順のリストを与えてあげれば， `candidates` は出力条件である"辞書順"を満たすことができる．

## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `N` も `R` も極端に小さいので， `O(R^N)` で候補( `candidates` )を全て挙げれる．
- 総和が `K` の倍数にならないものを除外して出力すれば良い．
- 列挙には `itertools` を使うとかなり便利．
  - 今回利用する `itertools.product()` に昇順のリストを与えてあげれば， `candidates` は出力条件である"辞書順"を満たすことができる．

"""
# ライブラリインポート
import itertools

# 標準入力を受け取る
N, K = map(int, input().split())
R = list(map(int, input().split()))

# 候補を全て列挙
candidates = list(itertools.product(*[range(1, x + 1) for x in R]))

# 候補を一つずつみる
for c in candidates:
  # 総和がKの倍数の時
  if(sum(c)%K==0):
    # 出力
    print(*c)
```

# D問題
- 「時計回りに回って最短の歩数」という条件なので， `1` 周しなくて良い．
- `s` を `1~N` で定めて，それぞれに対応する `t` を求めていては， `O(N^2)` より `tle` してしまう．
- `s` ごとに，該当する数を線形時間で求められる方法を考える．
  - まず， `s=1` とした時に，それぞれの休憩所までの距離の mod(`%M`)を考える．
  - mod を格納するリスト `D` を作成する． `index` を `mod` の値， `value` を該当する数とする．
  - さて， `s=1` の時は，当然 `D[0]` が該当する数になる．
  - では， `s=2` とした時はどうすればよか．それは， `s` を `1` から `2` に移動させた値 `dif` を参照すれば良いので， `D[dif]` が該当する数になる．
  - ただし， `s=2` とした時には， `t=1` のパターンを `D` に追加し， `t=2` を `D` から削除することを忘れてはいけない．
  - このように， 新しい `s` を考える時には，一個前を追加し，自分を削除すれば良い．
```D.py
"""
<方針>
- 「時計回りに回って最短の歩数」という条件なので， `1` 周しなくて良い．
- `s` を `1~N` で定めて，それぞれに対応する `t` を求めていては， `O(N^2)` より `tle` してしまう．
- `s` ごとに，該当する数を線形時間で求められる方法を考える．
  - まず， `s=1` とした時に，それぞれの休憩所までの距離の mod(`%M`)を考える．
  - mod を格納するリスト `D` を作成する． `index` を `mod` の値， `value` を該当する数とする．
  - さて， `s=1` の時は，当然 `D[0]` が該当する数になる．
  - では， `s=2` とした時はどうすればよか．それは， `s` を `1` から `2` に移動させた値 `dif` を参照すれば良いので， `D[dif]` が該当する数になる．
  - ただし， `s=2` とした時には， `t=1` のパターンを `D` に追加し， `t=2` を `D` から削除することを忘れてはいけない．
  - このように， 新しい `s` を考える時には，一個前を追加し，自分を削除すれば良い．
"""
# 標準入力
N, M = map(int, input().split())
A = list(map(int, input().split()))


# 休憩所1からそれぞれの休憩所への距離．累積和のように求める．
AA = [0]*(N+1)
for i in range(N):
  AA[i+1] = (AA[i] + A[i])%M

# 1周の長さ
T = sum(A)%M

# 休憩所1からのそれぞれの休憩所への距離のmod
D = [0]*M
for i in range(N-1):
  D[AA[i+1]%M] += 1

# 該当する数
ans = 0
# 移動した値
dif = 0
# s=iとして一つずつみる
for i in range(N):
  
  # s=iとしたときの該当する数
  ans += D[dif%M]
  
  # s=i+1のための準備をする
  dif = AA[i+1] # difを変える
  D[(T+AA[i])%M] += 1 # s=iを追加
  D[(AA[i+1])%M] -= 1 # s=i+1を削除

# 出力
print(ans)
```

# E問題
- 公式解説と一緒です．
```E.py
"""
<方針>
- 公式解説と一緒です．
"""
N, K = map(int, input().split())
X = list(map(int, input().split()))
A = list(map(int, input().split()))

# 10^18 < 2^60
M = 60

# ダブリングのリスト
P = [[-1]*N for _ in range(M)]

# ダブリングの初期値
for i in range(N):
  P[0][i] = X[i] - 1

# ダブリングの遷移
for i in range(1, M):
  for j in range(N):
    P[i][j] = P[i-1][P[i-1][j]]

# どこの値を参照するかの初期値
Q = list(range(N))

# K回遷移させる
for i in range(M):
  # Kを2で割る
  K, mo = divmod(K, 2)
  
  # 余りが1の時(bitが立っているとき)
  if(mo==1):
    # ダブリングのリストから遷移を行う
    for j in range(N):
      Q[j] = P[i][Q[j]]

# 出力
ans = []
for i in range(N):
  ans.append(A[Q[i]])
print(*ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc367)
- [E問題の公式解説](https://atcoder.jp/contests/abc367/editorial/10707)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(oooox--)](https://atcoder.jp/users/mattsunkun/history/share/abc367)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc367/submissions/56920296)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc367/submissions/56920439)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc367/submissions/56920691)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc367/submissions/56922168)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc367/submissions/56919961)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 実はコンテスト中に私用PCがぶっ壊れました．．．
- PCが壊れてなくても，方針違ったんで，Eは通りませんがね．．．