総括
A, B, C解けました。
DとEはもう少しで解けると思うのですが、なかなかコンテスト時には解けず、後日のACとなりました。
#問題
https://atcoder.jp/contests/abc176
A. Takoyaki
回答
N, X, T = map(int, input().split())
if N % X == 0:
ans = (N // X) * T
else:
ans = (N // X) * T + T
print(ans)
作るたこ焼きの数Nが、たこ焼き器の最大キャパ数であるXの倍数か否かで場合分けを行いました。
B. Multiple of 9
回答
N = list(str(input()))
total = 0
for i in range(len(N)):
total += int(N[i])
if total % 9 == 0:
print('Yes')
else:
print('No')
わざわざ問題文に
「整数 N が 9 の倍数であることと、N を十進法で表したときの各桁の数の和が 9 の倍数であることは同値です。」
とヒントを書いてくれているのでそのままコードに落とします。
このヒントいらなかったのでは？と思いました。
C. Step
回答
N = int(input())
A = list(map(int, input().split()))
total = 0
for i in range(N-1):
if A[i] > A[i+1]:
diff = A[i] - A[i+1]
total += diff
A[i+1] += diff
print(total)
現在のA[i]と次のA[i+1]を比べてA[i+1]が大きければその差分を足していきます。
C問題にしては簡単でしたので提出前に何か落とし穴がないかと不安になり、制約にあるAの最大値が10**9と大きい点で何かありそう・・・と思いましたが、とりあえず出してみたら通りました。
D. Wizard in Maze
回答(後日AC pypyで通ります。pythonはTLE)
#---------------------------------[インポート]---------------------------------#
from collections import deque
#---------------------------------[入力受取・初期設定]---------------------------------#
H, W = map(int, input().split())
C = tuple(map(int, input().split())) # 魔法の位置
D = tuple(map(int, input().split())) # ゴール
D_y = D[0] -1 # 0スタート
D_x = D[1] -1 # 0スタート
S = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[C[0]-1][C[1]-1] = 0 # 初期値
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 普通の移動
main_q = deque()
magic_q = deque() # マジック用のキュー
main_q.append((C[0]-1, C[1]-1))
#---------------------------------[BFS]---------------------------------#
while main_q:
y, x = main_q.popleft()
magic_q.append((y, x))
for move in moves:
dy, dx = move
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
continue
if S[moved_y][moved_x] == '#':
continue
if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
main_q.append((moved_y, moved_x))
visited[moved_y][moved_x] = visited[y][x]
#---------------------------------[マジック用のBFS]---------------------------------#
if not main_q: # main_qが空になった場合は探索済みからマジックを使う
while magic_q:
y, x = magic_q.popleft()
for dy in range(-2, 3):
for dx in range(-2, 3):
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
continue
if S[moved_y][moved_x] == '#':
continue
if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
main_q.append((moved_y, moved_x))
visited[moved_y][moved_x] = visited[y][x] + 1
#---------------------------------[回答表示]---------------------------------#
answer = visited[D_y][D_x]
print(answer)
問題を読んだ瞬間BFSで解けるな・・・と思いましたが、マジックを使うところの実装がうまくできず、コンテスト時は解けませんでした。
方針は、
1.まずは普通に移動Aで移動する（ここで1回目のBFSを実装）
2.移動Aを全部行ったら、移動Aで探索（magic_qに格納）した箇所からマジックで移動Bを試してみる（ここで2回目のBFSを実装）
3.移動Bで探索(main_qに格納)した箇所から再度移動Aで移動開始
4.以下1~3を繰り返し。移動の際はvisitedにマジックの使用回数を記録していく
5.目的地のvisitedに記録された回数が答え
となります。
普通のBFSが書ける前提で、「visitedにマジックの使用回数を記録する」という実装ができるか否かが、この問題の肝だった気がします。
上記コードだとpythonではTLEになりpypyで通す必要があります。
工夫すればpythonでも通ると思いますが、このままのコードのほうが自分的にはわかりやすいので改良していません。
E. Bomber
回答(後日AC)
import numpy as np
H, W, M = map(int, input().split())
row = np.zeros(W)
col = np.zeros(H)
memo = []
for _ in range(M):
h, w = map(int, input().split())
h -=1
w -=1
row[w] += 1
col[h] += 1
memo.append((h, w))
col_max = col.max()
row_max = row.max()
max_col_indexes = np.where(col == col_max)[0]
max_row_indexes = np.where(row == row_max)[0]
ans = col_max + row_max -1
memo = set(memo)
for c in max_col_indexes:
for r in max_row_indexes:
if (c, r) not in memo:
ans = col_max + row_max
print(int(ans))
exit()
print(int(ans))
方針はすぐに決まってコードもかけたのですが、計算量を落としきれず、コンテスト時にACすることができませんでした。
方針としては、
1.それぞれの行、列に存在する爆弾を数えて、行、列それぞれのmaxの爆弾数（行max, 列maxとする）と、maxとなる行番号、列番号を取得
2.maxとなる行番号と列番号が同じ爆弾を数えている場合は、行max + 列max -1が答え
3.maxとなる行番号と列番号が同じ爆弾を数えていない場合は、行max + 列maxが答え
4.行と列で同じ爆弾を数えているか否かの判定は、maxとなる行番号と列番号の座標に爆弾があるか否かをチェック
です。
コードにあるmemo = set(memo)を入れないとTLEになってしまいます。