AtCoder Beginner Contest(ABC) 281 - Pythonでのバーチャル参加結果と内容整理

# 1. 前書き
AtCoderBeginnerContest(ABC)の参加結果と内容の整理、および外部の解説記事を参考にした上で、自分なりに解法を整理していきます。
使用言語はPythonで行きます。本業ではJavaかRubyonRailsユーザーですが、計算速度の問題であったり、トレンドに乗っておくという意味でも（こちらが大きい）、Pythonに慣れていきたいと思います。

# 2. コンテスト内容
- コンテスト名
    - AtCoder Beginner Contest 281
- 開催日時
    - 2022/12/10(土) 21:00 - 22:40
- 実施区分
    - バーチャル参加
    - 2022/12/14(水)

# 3. 結果
|区分|結果|所要時間|実行時間|
|:--|:--|:--|:--|
|A問題|AC|1:38|25ms|
|B問題|AC|22:10|23ms|
|C問題|AC|50:11|62ms|
|D問題|未提出|-|-|

# 4. 解説

## 4-1. A - Count Down

### 4-1-1. 問題文
N 以下の非負整数を大きい方から順にすべて出力してください。

#### 制約
- 1 ≤ N ≤ 100
- Nは整数

### 4-1-2. 入力形式
~~~
N
~~~

### 4-1-3. 解説
N, N-1, ... 2, 1, 0の整数列を、順番に出力します。
0 ~ Nの範囲（range(N+1))でforループを実行し、N-1を出力すればOKです。

### 4-1-4. ソースコード
~~~python
n = int(input())
for i in range(n+1):
  print(n-i)
~~~

## 4-2. B - Sandwich Number

### 4-2-1. 問題文
英大文字と数字からなる文字列 S が与えられるので、S が以下の条件を満たすか判定してください。
- S は次の文字または文字列をこの順番で連結して得られる。
    - 一文字の英大文字
    - 100000 以上 999999 以下の整数を 10 進表記して得られる長さ 6 の文字列
    - 一文字の英大文字

#### 制約
- S は英大文字と数字からなる
- S の長さは 1 以上 10 以下

### 4-2-2. 入力形式
~~~
S
~~~

### 4-2-3. 解説
問題文を読み解き、与えられた3つの条件を満たすために、必要な条件を整理します。
- 文字数が8（英大文字1桁 + 数値6桁 + 英大文字1桁）
- 1文字目が英大文字
- 8文字目が英大文字
- 2文字目が0以外の数字（これがないと、「A**012345**B」のような10進数表記の整数では無いケースで誤判定となる）

実際に提出したコードは以下でした。
文字列Sを1文字毎にfor文で判定している冗長なコードになってしまっています。
公式解説で紹介されているように、単純にs[i]のように部分文字を切り出して判定する方がスマートでした。

https://atcoder.jp/contests/abc281/submissions/37074572

### 4-2-4. ソースコード
~~~python
s = input()

if len(s) == 8:
  flg = True
  cnt = 1
  for char in s:
    if cnt == 1 or cnt == 8:
      if char.isalpha() == False:
        flg = False
        break
    elif cnt == 2:
      if char == "0":
        flg = False
        break
    else:
      if char.isalpha() == True:
        flg = False
        break
    cnt += 1    
  if flg == True:
    print("Yes")
  else:
    print("No")
else:
  print("No")
~~~

### 4-2-5. python文法の整理
**文字列が英字かどうかを判定 isalpha()**

~~~python
#使用法
[文字列].isalpha()

#使用例
s1 = abc
s2 = 123
print(s1.alpha()) -> True
print(s1.alpha()) -> False
~~~

## 4-3. C - Circular Playlist

### 4-3-1. 問題文
N 曲からなるプレイリストがあり、曲には 1,…,N の番号が付けられています。
曲 i の長さは A<sub>i</sub>秒です。

プレイリストを再生すると、曲 1、曲 2、…、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。

プレイリストを再生してから T 秒後に流れているのはどの曲ですか？また、その曲が流れ始めてから何秒の時点ですか？
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。

#### 制約
- 1 ≤ N ≤ 10<sup>5</sup>
- 1 ≤ T ≤ 10<sup>18</sup>
- 1 ≤ A<sub>i</sub> ≤ 10<sup>9</sup>
- プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
- 入力される値は全て整数

### 4-3-2. 入力形式
N T
A<sub>1</sub> ... A<sub>N</sub>

### 4-3-3. 解説
まずは、入出力例1について考えてみます。
~~~
3 600
180 240 120
~~~
この場合、600秒経過までに、プレイリストを一周して、1曲目に戻ってきています。
プレイリストが何周するかについては問われていないので、この場合は与えられたTの600秒から、プレイリスト1周分の秒数である540秒(180+240+120）を引いた状態、60秒（600-540）を考察対象とすることで、Nについて1回のループで判定できることになり、間に合いそうです。

この部分について一般化すると、
Tの中にプレイリストが何周分含まれるかは、プレイリスト１周分の秒数をsum(A)とすると、
「T ÷ sum(A)」の**小数点以下切り捨て**で取得することができます。

あとは、得られた残り秒数60秒について、プレイリストの曲順に判定していきます。
　「残り秒数 < 曲の秒数」の場合、その曲と現在の残り秒数が答えになります。
　「残り秒数 > 曲の秒数」の場合、残り秒数から曲の秒数を差し引いて、プレイリストの次の曲の判定に入ります。

これをソースコードに起こしたものが、実際に提出した以下になります。

### 4-3-4. ソースコード
~~~python
n,t = map(int, input().split())
A = list(map(int,input().split()))

#プレイリスト1周分の合計時間をsumとする
sum = sum(A)

#Tに含まれるプレイリスト複数周回分を差し引いた時間をrestとする
rest = t - sum * (t // sum)

for i,elem in enumerate(A):
  if rest > elem:
    rest -= elem
  else:
    print(i+1,rest)
    break
~~~

### 4-3-5. python文法の整理
** forループでインデックスを取得する　enumerate()**

~~~python
#使用法
for [インデックス], [要素] in enumerate([イテラブルオブジェクト])

#使用例
array = ['one', 'two', 'three']
for i, elem in enumerate(array):
  print(i, elem)
-> 0 one
-> 1 two
-> 2 three
~~~

### 4-3-6. 解説を踏まえた別解
プレイリストの累積和の数列に対して、二分探索で位置を求める、という問題に帰着できると、よりスマートです。
累積和はitertools.accumulate、二分探索はbisect.bisect_leftを使うようです。

以下の記事を参考にしました。

https://qiita.com/Waaaa1471/items/d98411cdc3045fc28610

## 4-4. D - Max Multiple

### 4-4-1. 問題文
非負整数列 A=(a<sub>1</sub>,a<sub>2</sub>,…,a<sub>N</sub>) が与えられます。
A の(添え字が相異なる) K 個の項の和として考えられる非負整数の集合を S とします。
S に含まれる D の倍数の最大値を求めてください。ただし、S に D の倍数が含まれない場合、代わりに -1 と出力してください。

### 4-4-2. 入力形式
N K D
a<sub>1</sub> ... a<sub>N</sub>

### 4-4-3. 解説
解説記事を読みましたが、動的計画法（DP）を理解するところから必要のようなので、終わり次第更新予定。