AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY） – AtCoder
ちょっと最近、集中力が切れがちなので慎重にunrated参加です（実際コンテスト中に20分ほど離席してしまった）。結果はABCDの4問解答(B問題で1ペナ)でした。
素直に場合分けして解きました。if文はもっと短くかけますが、ミスがないようにこのくらいでいいかなと…。
R, X = map(int, input().split())
if X == 1:
if 1600 R 2999:
print("Yes")
else:
print("No")
else:
if 1200 R 2399:
print("Yes")
else:
print("No")
ちょっと時間がかかってしまった上に、1ペナでした。
考え方は以下のようにしました。
- 1 数字の出現回数を記録する配列
counter[]を用意する - 2 配列
Aの末尾の値の、カウントを減らす - 3
counter[]が全て1以上かチェック - 2,3 を繰り返し
より単純に、配列Aの末尾を短くする → 配列A内の数字をカウント としても、計算量は十分間にあるので、そちらのほうが良かったかもしれません。
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 数字の出現回数を記録する配列
counter = [0] * (M+1)
for i in range(len(A)):
value = A[i]
counter[value] += 1
# 各数字が1個以上あるかを判定する
def check():
for i in range(1, len(counter)):
if counter[i] 0:
return False
return True
# 初期状態で各数字が1個以上あるかを判定する
if check() == False:
print(0)
exit()
# A[]の末尾から数字カウントを減らしていく
for i in range(1, len(A) + 1):
value = A[-1 * (i)]
counter[value] -= 1
if check() == False:
print(i)
exit()
# N = 4の場合
answer = A1*A2 + A1*A3 + A1*A4 + A2*A3 + A2*A4 + A3*A4
↓
answer = (A1 + A2 + A3) * A4
+ (A1 + A2) * A3
+ (A1) * A2
上のように式変形をすると、(A[1]からA[k-1]までの累積和) * A[k] を使うと、効率よく計算できる事がわかります。
N = int(input())
A = list(map(int, input().split()))
# Aの累積和を求める
sum_a = []
sum_a.append(0)
for i in range(len(A)):
next = sum_a[-1] + A[i]
sum_a.append(next)
# 累積和を使って、答えを求める
answer = 0
for i in range(2, N+1):
answer += sum_a[i-1] * A[i-1]
print(answer)
問題文とは逆に、出口’E’からスタートして、各通路’.’に最短距離でどうやって到達するか…を考えました。
最短距離は幅優先探索で求められますので、そのようにしました。
H, W = map(int, input().split())
# 地図の周囲を"#"で囲うと、マップ外判定が楽になる
S = []
S.append(list("#" * (W + 2)))
for i in range(H):
S.append(list("#" + input() + "#"))
S.append(list("#" * (W + 2)))
# 答えの書き込み用に、SをコピーしてTを作成
T = []
for i in range(len(S)):
line = S[i].copy()
T.append(line)
# 出口 E の座標を求めておく
e_list = []
for y in range(len(S)):
for x in range(W + 2):
if S[y][x] == "E":
e_list.append((x, y))
# 幅優先探索
que = deque()
# スタート地点をキューに入れる
for i in range(len(e_list)):
x, y = e_list[i]
dist = 0
que.append((dist, x, y))
# 移動できる方向(上下左右)と、マス目にいれる記号の配列
next_dir = [(1,0,""), (-1,0,">"), (0,1,"^"), (0,-1,"v")]
# 幅優先探索
while que:
dist, x, y = que.popleft()
# 行ける通路があれば、キューに入れる
for dx, dy, char in next_dir:
if T[y+dy][x+dx] == ".":
T[y+dy][x+dx] = char
que.append((dist+1, x+dx, y+dy))
for i in range(1, H+1):
line = T[i]
line = line[1:-1]
print("".join(line))
Views: 4
