ABC220の参加記録です。
使用言語はPython3、レートは600前後の私が自分の理解した内容で記載していきます。
A問題からC問題までのACコード付きです。
A – Find Multiple
標準入出と簡単な繰り返し処理、条件分岐の問題。
繰り返し処理なしでも答えは出ますが、私は繰り返し処理で提出しました。
Cの1倍の数から順に作っていき、A以上B以下の数であればその数を出力してプログラム終了。
Cを1000倍してもA以上B以下の数字が表れなかったら-1を出力するコードです。
# AtCoder Beginner Contest 220
# A - Find Multiple
A,B,C=map(int,input().split())
for i in range (1,1001):
if A<=i*C<=B:
print(i*C)
exit()
print(-1)繰り返し処理で答えを求めるのではない場合は、
B以下であり、かつCの倍数が、A以上であればその数を出力し、そうでない場合は-1を出力する。というプログラムでもOKですね。(こちらが想定解っぽいです。)
A,B,C=map(int,input().split())
print(B//C*C) if A<=B//C*C else print(-1)
B – Base K
二進数の変換が出来るかが問われる問題。
Python3では、組み込み関数の int() を利用すると楽です。
# AtCoder Beginner Contest 220
# B - Base K
K=int(input())
A,B=map(str,input().split())
A=int(A,K)
B=int(B,K)
print(A*B)組み込み関数ではなく、計算するとしたら、N進数を10進数に戻していく繰り返し処理を記述していけばよいですね。
K=int(input())
A,B=map(str,input().split())
A=list(map(int,A))
B=list(map(int,B))
A_base10=0
B_base10=0
base_A=0
while len(A)>0:
A_base10 += A.pop() * K**base_A
base_A += 1
base_B=0
while len(B)>0:
B_base10 += B.pop() * K**base_B
base_B += 1
print(A_base10 * B_base10)C – Long Sequence
累積和と二分探索の問題。
解説を見ると累積和も二分探索も必要ありませんでした。。。
以下、この問題を解いたときの方針を記載します。
- 配列の合計よりもXが大きい時は、配列を何回連結すればよいかわかりそう。
- 配列の合計を複数回繰り返した後に残っている余りが、配列のどこに位置するかわかればよさそう。
上記二つのうまく活用できるのは、累積和と二分探索だな。ということで、この二つを利用しました。
# AtCoder Beginner Contest 220
# C - Long Sequence
import bisect
N=int(input())
A=list(map(int,input().split()))
X=int(input())
# 累積和を作成
acc_A=[0]
for i in range (N):
acc_A.append(acc_A[-1]+A[i])
# Aの合計
total_A=acc_A[-1]
# Aを何回繰り返したらよいかの判定要素
# d:何回繰り返すか
# m:d回繰り返した後に、必要な数
d,m=divmod(X,total_A)
# 答え用の変数
# 上で求めたdと配列の長さNを掛けた値
ans=d*N
# d回繰り返した後に、必要な数が累積和のどのindexに入るか
p=bisect.bisect_left(acc_A,m)
# Xと等しい場合は、必要な項数に1足す
if d*total_A+acc_A[p]==X:
print(ans+p+1)
else:
print(ans+p)今回の問題は、Xを超える項数ということで、Ｘと一致する場合は、場合分けが必要です。
私はここを見逃して1回WAを出しました。
コメント