[ABC433] ABC 433(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 時刻
Tが経過した時に、Z倍になっているかを方程式で考える。-
X+T == Z*(Y+T)↔︎ -
T == (X-Z*Y)/(Z-1)p
-
- 商が0以上で、余りがなければ
Yes
A.py
"""
<方針>
- 時刻 `T` が経過した時に、`Z` 倍になっているかを方程式で考える。
- `X+T == Z*(Y+T)` ↔︎
- `T == (X-Z*Y)/(Z-1)`
- 商が0以上で、余りがなければ `Yes`
"""
# 入力
X, Y, Z = map(int, input().split())
# 右辺を計算
di, mo = divmod(X-Z*Y, Z-1)
# 商が0以上で、余りがなければ良い
if(di >= 0 and mo == 0):
print("Yes")
else:
print("No")
B問題
- 気合いで
for文をかませば良さそう - 人
iを選ぶ - それより左の人
jをiに近い順番に見れば良い
B.py
"""
<方針>
- 気合いで `for` 文をかませば良さそう
- 人 `i` を選ぶ
- それより左の人 `j` を `i` に近い順番に見れば良い
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 人i
for i in range(N):
# 高い人がいたかどうかのフラグ
tall = False
# 人j
for j in range(i-1, -1, -1):
# 身長を比べる
if(A[j] > A[i]):
# 左に高い人がいた時、
tall = True
break
# 身長高い人がいたかどうか
if(tall):
# いる
print(j+1) # 0-indexed
else:
# いない
print(-1)
C問題
方針
- 線形時間程度で収めることを考える。
- 連続する数字をブロックとして捉えて一旦まとめてみる。
O(N) -
1122が12を包含するように、隣同士のブロックで作れる最長の長さが個数になりそう。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 線形時間程度で収めることを考える。
- 連続する数字をブロックとして捉えて一旦まとめてみる。`O(N)`
- `1122` が `12` を包含するように、隣同士のブロックで作れる最長の長さが個数になりそう。
"""
# 入力
S = input()
# 番兵
S += "A"
# ブロックの文字を記録
chars = []
# ブロックの個数を記録
cnts = []
# 現在の文字
char = S[0]
# 現在連続している個数
cnt = 1
# 2個目以降をみる
for s in S[1:]:
# 文字が一致すれば
if(s == char):
# 個数を増やす
cnt += 1
# 一致しなければ、
else:
# 現在の文字と個数をブロック単位として登録する
chars.append(char)
cnts.append(cnt)
# 新しいのに変える
char = s
cnt = 1
# 個数計測
ans = 0
# 隣り合うところだけ見る
for i in range(len(chars)-1):
# 左の数字に1足したら右の数字になるとき、
if(int(chars[i])+1 == int(chars[i+1])):
# 作れる最大の長さが個数
ans += min(cnts[i], cnts[i+1])
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- とある部屋にいるんだけど、絶妙な体調不良を起こしてる。
- 新卒でデビルハンター目指そうかな。
- 最近Dすら解いてなくてやばいなと思いつつ。
- まじでいつまで続けるんだろう...