[python] ABC184 個人的メモ [AtCoder]
ABC184
所感
abc3完
思ったよりも冷えなかった
A - Determinant
#!/usr/bin/env python3
a, b = map(int, input().split())
c, d = map(int, input().split())
print(a * d - b * c)
B - Quizzes
不正解時に点数がマイナスにならない様にシミュレーションしてけばおk
#!/usr/bin/env python3
N, X = map(int, input().split())
S = input()
ans = X
for s in S:
if s == "o":
ans += 1
else:
ans = max(0, ans - 1)
print(ans)
C - Super Ryuma
落ち着いて場合分けを考えればおk
紙に書いて考えたら分かり易かった
80分かかったけど
コマの移動範囲は上下左右で対称
なので状況を簡単にするために始点を原点,移動方向を第1象限の方向に限定する
まず,斜め方向の移動のみ考える
図に斜め移動のみで到達できるマスを示した
例として
これより以下が分かる
-
のマス(赤)は,斜め移動1回で到達できるc=d -
が偶数のマス(青)は斜め移動2回で到達できるc-d -
が奇数のマス(白)は斜め移動のみでは到達できないc-d
しかし,コマはマンハッタン距離3以下の付近のマスにも移動できる
よって,コマは全てのマスに3手以内で到達できると分かる
なので,
-
0手
- 始点と終点が一致する
-
1手
- 赤マス
- マンハッタン距離3以下
-
2手
- 青マス
- 赤マスからマンハッタン距離3以下
- マンハッタン距離6以下(白マスでも2手で行ける)
-
3手
- 上記以外
コンテスト中の提出はマンハッタン距離6以下の場合を考慮していない嘘解法だったのでafter_contestのテストケースでwa
なので直した
#!/usr/bin/env python3
a, b = map(int, input().split())
c, d = map(int, input().split())
# 原点スタートとする
c = abs(c - a)
d = abs(d - b)
res = abs(c - d)
if c == 0 and d == 0:
ans = 0
elif c + d <= 3 or res == 0:
ans = 1
elif res % 2 == 0 or res <= 3 or c + d <= 6:
ans = 2
else:
ans = 3
print(ans)
D - increment of coins
確率DP
正直良く分からん
そうすると,以下の漸化式が得られる
これを再帰関数で実装する
メモ化しないとTLEする
計算量は
lru_cacheは関数をメモ化してくれるデコレータ
ただし,辞書でメモ化するのでリストでメモ化するよりも実行速度が遅くなる
#!/usr/bin/env python3
from functools import lru_cache
@lru_cache(maxsize=None)
def func(a, b, c):
res = 0
if max(a, b, c) == limit:
return res
if a != 0:
res += a * (func(a + 1, b, c) + 1)
if b != 0:
res += b * (func(a, b + 1, c) + 1)
if c != 0:
res += c * (func(a, b, c + 1) + 1)
res /= a + b + c
return res
A, B, C = map(int, input().split())
limit = 100
print(func(A, B, C))
E - Third Avenue
問題文通りにBFSを実装する
このままだとTLEする
同じ文字のテレポーターを複数回使うのは明らかに無駄
なので,1度使ったテレポーターは使わないようにする
これでおk
#!/usr/bin/env python3
from collections import deque, defaultdict
H, W = map(int, input().split())
margin = [["#"] * (W + 2)]
grid = margin + ["#" + input() + "#" for _ in range(H)] + margin
warp = defaultdict(list)
for i in range(1, H + 1):
for j in range(1, W + 1):
if grid[i][j] == "." or grid[i][j] == "#":
continue
warp[grid[i][j]].append((i, j))
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
seen = [[-1] * (W + 2) for _ in range(H + 2)]
queue = deque([(warp["S"][0][0], warp["S"][0][1], 0)])
while queue:
i, j, time = queue.popleft()
if seen[i][j] != -1:
continue
seen[i][j] = time
if [(i, j)] == warp["G"]:
break
# 隣接マスへの移動
for di, dj in move:
ni = i + di
nj = j + dj
if grid[ni][nj] == "#":
continue
queue.append((ni, nj, time + 1))
# テレポーター
if grid[i][j] != ".":
for k in warp[grid[i][j]]:
ni, nj = k
queue.append((k[0], k[1], time + 1))
# テレポーターの複数回使用を除く
del warp[grid[i][j]]
print(seen[warp["G"][0][0]][warp["G"][0][1]])
参考
- 解説 - AtCoder Beginner Contest 184
https://atcoder.jp/contests/abc184/editorial - functools --- 高階関数と呼び出し可能オブジェクトの操作 Python 3.9.0 ドキュメント
https://docs.python.org/ja/3/library/functools.html#functools.lru_cache - 確率 DP を極めよう - 確率と期待値の問題解説 - tsutaj
http://compro.tsutajiro.com/archive/180220_probability_dp.pdf - AtCoder Beginner Contest 184 C,D,E,F問題メモ [いかたこのたこつぼ] https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2020/1122_abc184#d_-_increment_of_coins
- AtCoder ABC 184 D - increment of coins (水色, 400 点) - けんちょんの競プロ精進記録
https://drken1215.hatenablog.com/entry/2020/11/23/010500 - 【Python】ABC184 解説 MA-R-CO NOTE
https://marco-note.net/abc-184-work-log/ - [AtCoder] ABC 184 D - increment of coins | ヤマカサの競技プログラミング
https://yamakasa.net/atcoder-abc-184-d/
Author And Source
この問題について([python] ABC184 個人的メモ [AtCoder]), 我々は、より多くの情報をここで見つけました https://zenn.dev/m193h/articles/35738abd5ef80bb8edbc著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol