AtCoderをPythonで取り組んだ振り返り(ABC395 A～C)

どうもこんにちは！

今週も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で学んだしゃくとり法で解けそうと作ったのが以下。

TLEとなるプログラム

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個以上ある数値の中から最短の距離を回答すればよいとのこと。しゃくとり法でも解けはするとのことですが、ハンマー持つとなんでも釘に見えたような感じでよくなかったですね。。

--- 2025/9/20追記 ---
緑コーダーを目指して取り組んだので追記。
C問題ですが、最短となりうる数列は両端が同じ数字であることです。そこで数列内の数字の個数を数えて、2個以上ある数字の距離を計算して、一番短い値を答えとしました。

n = int(input())
s = [int(x) for x in input().split()]
d = {}

# 数列内の各文字の個数をカウント
# 隣接する場合は最小の2なので出力して終了
one = True
for i in range(n):
    if i < n-1 and s[i] == s[i+1]:
        print(2)
        exit()
    if s[i] not in d:
        d[s[i]] = [i]
    else:
        d[s[i]].append(i)
        one = False

# 数字がすべて1個なら-1を出力して終了
if one:
    print(-1)
    exit()

# 複数個ある数字の距離(=その数字を両端とする文字列の長さ)を計算
# そのうちの最短を答えとして出力する
ans = 10**9
for i in d.values():
    for j in range(1,len(i)):
        ans = min(ans,i[j]-i[j-1]+1)

print(ans)

--- 追記ここまで ---

おわりに

前回も２問完答だったので結果出せず悔しいところですが、地道にやっていくしかないですね。

ではでは。