どうもこんにちは！
今週もAtCoderのコンテストに参加できたので記録がてら振り返ります。
残念ながらA,Bの２問完答、Cを解ききれず終了となりました。悔しい。
問題
問題は以下から。
A - Strictly Increasing? -
与えられた正数数列が狭義単調増加(数列を進めると必ず数値が増える数列。同じ数値が連続になるのもNG)であるかを判定する問題。
数列を読み込んで、for文で順番に比較して満たしているかどうかを確認する形にしました。
n = int(input())
s = [int(x) for x in input().split()]
for i in range(n-1):
if s[i] >= s[i+1]:
print("No")
break
elif i == n-2:
print("Yes")
B - Make Target -
与えられた正の整数Nをもとに、N×Nの模様を作成する問題。作成の条件は以下。
・左上端の座標を(i,j)とし、上からi行目、左からj列目とする。i=1,2,…,N の順に、以下の操作を行う。jはj=N+1−i とする。
・i≤j であるならば、i が奇数ならば黒、偶数ならば白で、マス (i,i) を左上、マス(j,j) を右下とする矩形領域に含まれるマスを塗りつぶす。このとき、既に色が塗られているマスについては色を上書きする。
・i>j であるならば、何もしない。
・黒に塗るときは#、白に塗るときは.とする。
シンプルに2重ループを使ってiの値ごとに(i,i)から(j,j)を塗りつぶすとしました。
n = int(input())
s = [["."]*n for _ in range(n)]
for i in range(1,n+1):
j = n + 1 - i
if i <= j:
if i % 2 == 1:
for k in range(i-1,j):
for l in range(i-1,j):
s[k][l] = "#"
else:
for k in range(i-1,j):
for l in range(i-1,j):
s[k][l] = "."
for i in range(n):
print("".join(s[i]))
C - Shortest Duplicate Subarray -
与えられた整数Nと長さNの整数列があり、整数列の空でない連続部分列で同じ値を複数個含むようなものがあるかどうか、ある場合は最短の長さを求めるというもの。制約として整列の長さは最大で$2*10^5$、整列内の数値は最大で$10^6$。
Paizaで学んだしゃくとり法で解けそうと作ったのが以下。
n = int(input())
s = [int(x) for x in input().split()]
length = 10000000
ans = 0
tmp = [s[0]]
right = 1
for i in range(n):
while right < n and (right == i or s[right] not in tmp):
tmp.append(s[right])
right += 1
if right < n:
if s[right] in tmp:
ans = 1
length = min(length,len(tmp)+1-tmp.index(s[right]))
tmp.pop(0)
if ans == 0:
print(-1)
else:
多分解けるんですがテストケースの約半分が時間制限を満たせず。while文がある分計算量が増えている・・・？ということでfor文だけで解くようにしたんですがむしろ遅くなったようで、解決できずタイムアップ。
解説を見たら、$10^6$分の配列を作って、数列内にでてきた値の位置を仕分け、あとは2個以上ある数値の中から最短の距離を回答すればよいとのこと。しゃくとり法でも解けはするとのことですが、ハンマー持つとなんでも釘に見えたような感じでよくなかったですね。。
おわりに
前回も２問完答だったので結果出せず悔しいところですが、地道にやっていくしかないですね。
ではでは。