プログラミングよくわからんケモノのABC395

ABC395感想

初心者にとってはA～Cの3完をいかに早くとれるかって回でした。
今回C問題で大分痛い目を見たせいで、レートが初のマイナス。
せめて茶入りはしたいので次回はしっかりこなしていきたいですね……。

A問題

数列が昇順に並んでいるかって問題です。

同値が許されないことを除けば昇順に並んでいるかを確認するだけなので、その通りにやればいいですね。

python abc395_a.py

N = input()
l = list(map(int, input().split()))

for i, j in zip(l, l[1:]):
  if i >= j:
    print("No")
    exit()
    
print("Yes")

B問題

漢字の回のような模様を作れって問題です。

一番外側の模様は固定なので、そこを基準に内側に内側に模様を入れていけばいいです。
もう少しスマートに書けた気がしますね、大分無駄が多い文だと思います。

python abc395_b.py

import itertools as it

N = int(input())
l = [["."] * N for _ in [0] * N]

for i in range(0, N, 2):
  for y, x in it.product(range(i, N-i), range(i, N-i)):
    if x == i or y == i or x == N - i - 1 or y == N - i - 1:
      l[y][x] = "#"

for ll in l:    
  print(*ll, sep="")

C問題

同じ数字同士の線分の長さを最小化しろって問題です。

問題としては非常にシンプルで、制約的に数字の種類数も$10^6$程度であり、各数字ごとの最小値をとって、その中でさらに最小値を取るだけの問題です。

(失敗した提出)

python abc395_c_mistake.py

import sys

N = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().strip().split()))

d = {}

for i in range(len(l)):
  x = l[i]
  if x in d.keys():
    a = min(d[x][0], i - d[x][1])
    d[x] = [a, x]
    
  else:
    d[x] = [float("INF"), i]
  

print(x+1 if (x := min(d[key][0] for key in d.keys())) != float("INF") else -1)

さて、これが問題のコードなのですが、どこを間違えているか分かりますか。

d[x] = [a, x]

これです。

iが現在確認している数字の位置を表していて、xが値を表しているのですが、誤って、値を挿入してしまっており、その結果、同じ数字同士の距離の測定が上手くいかなくなっているのです。
そもそもこれはx座標軸上の点の位置を表す数字と、値を表す数字の変数名が異常（本来はxを座標、iを数値としている。）なことが原因なのですが、スピードを求めすぎるあまり、レビューの質を下げるという悪い例を晒してしまった、ともとれるミスです。

この失敗のせいで15分ほどのロスが発生しており、順位としても500位程度下がる結果になってしまいました。
今後の反省とします。

python abc395_c.py

import sys

N = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().strip().split()))

d = {}

for i in range(len(l)):
  x = l[i]
  if x in d.keys():
    a = min(d[x][0], i - d[x][1])
    d[x] = [a, i]
    
  else:
    d[x] = [float("INF"), i]
  

print(x+1 if (x := min(d[key][0] for key in d.keys())) != float("INF") else -1)

D問題

鳥の移動、巣の入れ替え、鳥の巣の位置の出力を与えられた回数行え、っていう問題です。

課題となるのは巣の入れ替えですね。全く上手くいきませんでした。