どうもこんにちは！

今週のコンテストは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)

ではでは。