どうもこんにちは！
今週のコンテストはA,Bを完答。CはTLEを解消できず。
問題
問題は以下のリンクから。完答できたBとCのできたところまでを振り返ります。
A - Not Acceptable -
入力として4つの数字A,B,C,Dが与えられ、C時D分がA時B分より前の時間かを判定する問題。内容としてはA時B分がレポート提出期限で、C時D分に提出したら期限内かどうか、というもの。時間は24時間制で与えられ、同じ時間が与えられることはないです。
シンプルに時間を比較するんですが、比較条件が以下のどちらかを満たせばよいことに注意ですね。
- C < A (この場合、分は無条件で成立する)
- C = A かつ D < B
a,b,c,d = map(int,input().split())
if a > c or (a == c and b >= d):
print("Yes")
else:
print("No")
B - Product Calculator -
N個の整数と正整数Kが与えられます。最初の値を1として、N個の整数を順番にかけ算しますが、計算結果の桁数がK桁以下なら計算結果をそのまま、K+1桁となった場合は計算結果を1におきかえるとして、最終結果を出力するという問題。
計算結果の桁数判定は計算結果をstr型にしたものをlen関数で求めて判定しました。
n,k = map(int,input().split())
s = [int(x) for x in input().split()]
ans = 1
for i in s:
ans *= i
if len(str(ans)) > k:
ans = 1
print(ans)
C - ~ -
与えられた長さnの整数列Pに対して、Pの連続部分列でありかつ下記4つの条件をすべて満たす数列($A_1,A_2,･･･,A_n$)の個数を出力する問題。整数列Pは1,2,3,4,･･･,nを並び替えたもので、同じ値が複数個存在することはないです。
- 数列の長さが4以上
- $A_1 < A_2$
- 数列内で$A_{i-1} < A_i > A_{i+1}$を満たすのは1箇所のみ (例えば 2 4 3という並び)
- 数列内で$A_{i-1} > A_i < A_{i+1}$を満たすのは1箇所のみ (例えば 4 2 3という並び)
例えば数列が(1, 3, 6, 4, 2, 5)のときは(1, 3, 6, 4, 2, 5)と(3, 6, 4, 2, 5)を満たすこととなり、回答は2となります。なお与えられる数列の長さは最大$3 × 10^5$で計算量を意識する必要があります。
さて、計算量を考えなければ、for文の2重ループで条件を満たすかを順番に比較すればよいです。3個目と4個目の条件は1個しか含まないように判定する点に注意です。
判定だけなら以下の実装でできるはずです。(なおTLEで完答にはなりません)
n = int(input())
s = [int(x) for x in input().split()]
ans = 0
for i in range(1,n-2):
if s[i-1] >= s[i]:
continue
n1,n2 = False,False
for j in range(i+1,n-1):
if s[j-1] < s[j] and s[j] > s[j+1]:
if n1 == False:
n1 = True
else:
break
if s[j-1] > s[j] and s[j] < s[j+1]:
if n2 == False:
n2 = True
else:
break
if n1 == True and n2 == True:
解説によると、前後の数字を比較して不等号の配列を作って、この配列にランレングス圧縮をかけると探索すべき場所がわかって答えが出る…らしいんですが、現状理解できていません。。ある程度わかってコード書けたら追記するかもしれません。
ではでは。