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. ソースコード
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以外の数字（これがないと、「A012345B」のような10進数表記の整数では無いケースで誤判定となる）
実際に提出したコードは以下でした。
文字列Sを1文字毎にfor文で判定している冗長なコードになってしまっています。
公式解説で紹介されているように、単純にs[i]のように部分文字を切り出して判定する方がスマートでした。
4-2-4. ソースコード
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()
#使用法
[文字列].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 の長さは Ai秒です。
プレイリストを再生すると、曲 1、曲 2、…、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。
プレイリストを再生してから T 秒後に流れているのはどの曲ですか？また、その曲が流れ始めてから何秒の時点ですか？
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。
制約
- 1 ≤ N ≤ 105
- 1 ≤ T ≤ 1018
- 1 ≤ Ai ≤ 109
- プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
- 入力される値は全て整数
4-3-2. 入力形式
N T
A1 ... AN
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. ソースコード
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()**
#使用法
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を使うようです。
以下の記事を参考にしました。
4-4. D - Max Multiple
4-4-1. 問題文
非負整数列 A=(a1,a2,…,aN) が与えられます。
A の(添え字が相異なる) K 個の項の和として考えられる非負整数の集合を S とします。
S に含まれる D の倍数の最大値を求めてください。ただし、S に D の倍数が含まれない場合、代わりに -1 と出力してください。
4-4-2. 入力形式
N K D
a1 ... aN
4-4-3. 解説
解説記事を読みましたが、動的計画法（DP）を理解するところから必要のようなので、終わり次第更新予定。