今年最後のABCである、ABC233の参加記録です。
レートは600台の使用言語Python3の私が自分が理解出来た内容で振り返る記事です。
A – 10yen Stamp
標準入出力とif文が書けるかが問われる問題。
1行に複数変数を受け取るのに、私はものすごく苦労しました。
AtCoderのpractice contestのWelcome to AtCoder に書かれている通り、map() を利用して、受け取ります。
この問題の条件分岐は以下の3つです。
- 既に貼られている切手X円がY円以上である場合
- X円に何枚かの10円切手を貼ったら、丁度Y円になる場合
- X円に何枚かの10円切手を貼って、丁度Y円にならず、数円分を余計に貼る必要がある場合
# AtCoder Beginner Contest 233
# A - 10yen Stamp
X, Y = map(int, input().split())
# XがY以上の場合、追加不要
if X>=Y:
print(0)
exit()
# 不足分を計算
shortage = Y - X
# 足りない分が、丁度10で割り切れる場合、
if shortage % 10 == 0:
print(shortage // 10)
# 10で割り切れない場合は追加でもう1枚必要
else:
print((shortage // 10) + 1)B – A Reverse
文字列の扱いと、スライスが利用できますか。が問われる問題。
Python3では、文字列もスライスが可能ですね。詳しくは、このページなどを参照してもらうとわかりやすいと思います。
0-indexであることと、反転は[::-1] を利用することを知っていればそれぞれの部分で文字列を作成して、あとは文字列を結合して出力すればOKですね。
# AtCoder Beginner Contest 233
# B - A Reverse
L, R = map(int, input().split())
# 0-index
L, R = L-1, R-1
S = input()
# 3つに分割
S1 = S[0:L]
S2 = S[L:R+1]
S3 = S[R+1:]
# S2だけ[::-1]で反転させて結合
print(S1 + S2[::-1] + S3)C – Product
全探索が出来ますか。が問われる問題。
私は解けませんでした。
公式の解説の再帰DFSなどを見て、いろいろ考えた結果、自分が理解できたのは以下の内容です。
- 各Liを頂点集合とみなす。
- 各LiとLi+1の各頂点間に有効辺を貼る。
入力例2はこのようなイメージです。
- LiがNと一致して、かつ、Xと一致している数を数え上げる。
- LiがN未満の場合、スタックにLi+1の各頂点と今の値の積を追加する。
- 途中、計算の過程で値がXより大きい場合は、それ以降の探索をしない。
上記を実装してACしました。
# AtCoder Beginner Contest 233
# C - Product
N, X = map(int, input().split())
As = []
for _ in range(N):
line = list(map(int,input().split()))
L, A = line[0], line[1:]
As.append(A)
N -= 1 #0-index に変更
ans=0
# DFS
# todoには、(Lの階層, 値) を持つ。
todo=[]
# Lの階層が0の値をセット
for a in As[0]:
todo.append((0,a))
while todo:
now_n, now_val = todo.pop()
# 途中で値がXを超えていた場合は、continue
if now_val > X:
continue
# Lの階層がN(0-index)で、かつ、値がXなら、ans をプラス
if now_n==N and now_val==X:
ans+=1
# Lの階層がN未満であれば、次の階層の各値と掛けた値をtodoに追加
if now_n < N:
now_n += 1
for e in As[now_n]:
todo.append((now_n,now_val*e))
print(ans)C問題は解けずも、D問題は解けて、レートは上がりました。Highestの更新もしましたが、今年の目標だった緑にはなれませんでした。
コメント