どうもこんにちは！
今週のコンテストはCまで完答、振り返りもCまで。
Dは最大$2×10^5$個のすべての組み合わせを作っただけでTLEになるので、どうやったら計算量が落とせるのかわかりませんでした。
問題と公式の解説のリンク
問題は以下のリンクから。
A - Happy Birthday! 4 -
問題
正整数x,y,zが与えられます。x,yは年齢で1年ごとに歳を取るとして、xがyのちょうどz倍になるタイミングがあるかを判定する問題。
なお歳を取る日は同じとされています。
考え方とコード
x÷yは歳をとるごとに小さくなっていくことを踏まえて、1年ごとにx÷yがz倍になっているかを判定するようにしました。
x,y,z = map(int,input().split())
while x / y >= z:
if x // y == z and x % y == 0:
print("Yes")
exit(0)
else:
x += 1
y += 1
print("No")
B - Nearest Taller -
問題
n人が横一列に並んでおり、それぞれの身長が与えられているとします。左から数えてi番目の人を基準にi-1番目以下の人で身長がi番目の人より高い人がいるかを判定する問題。いない場合は-1を、いる場合はi番目の人に一番近い人の番号を出力するとします。なおnの最大は100です。
考え方とコード
最大で100人なら2重ループでも計算できるということで、i番目の人のときにi-1番目の人から順番にi番目と身長を比較して、条件を満たしたらその番号を出力、1番目の人も満たさなければ-1を出力するとしました。
n = int(input())
a = [int(x) for x in input().split()]
print(-1)
for i in range(1,n):
for j in range(i-1,-1,-1):
if a[i] < a[j]:
print(j+1)
break
elif j == 0:
print(-1)
C - 1122 Substring 2 -
問題
数字からなる文字列が与えられます。この部分文字列の中で、以下の条件をすべて満たす文字列の個数を出力する問題。
- 2文字以上の偶数列
- 前半分は同じ数字のみ、後部分は前半分の数字に1を足した数字のみで構成(例えば前半分は1,後半分は2の111222というイメージ)
考え方とコード
まず与えられた数字列を前からサーチして、12のような1差の並びの部分を探します。その位置から前後に1個ずつ同じ数字かをチェックするとしました。例えば12という並びを見つけたら、次は前後の数字を見て1122か、もしそうならさらに1個前後の数字を見て111222となっているかを確認する、という感じです。
s = input()
l = len(s)
ans = 0
idx = 0
while idx < l-1:
if int(s[idx]) +1 == int(s[idx+1]):
ans += 1
i = 1
while idx - i >= 0 and idx + 1 + i < l:
if int(s[idx-i]) == int(s[idx]) and int(s[idx+1+i]) == int(s[idx+1]):
ans += 1
i += 1
else:
break
idx += 1
print(ans)
ではでは。