A - Chinchirorin
https://atcoder.jp/contests/abc203/tasks/abc203_a
- #XOR で解決するの賢いなぁ…
- 言われた通り実装して、おわり。
l = list(map(int, input().split()))
l.sort()
if l[0] != l[1] and l[1] != l[2]:
print(0)
elif l[0] == l[1]:
print(l[2])
else:
print(l[0])
B - AtCoder Condominium
https://atcoder.jp/contests/abc203/tasks/abc203_b
- ループで愚直に答え足していったら、おわり
N, K = map(int, input().split())
ans = 0
for i in range(1, N + 1):
for j in range(1, K + 1):
ans += i * 100 + j
print(ans)
C - Friends and Travel costs
https://atcoder.jp/contests/abc203/tasks/abc203_c
- 数直線移動系 #シミュレーション
- $10^{100}$まではどうあがいても無理だけど、村の数は$2\times 10^5$で済む
- 村と村の間を$O(1)$で飛ばせたら勝ち
- 1円で1個隣の村に移動できるので、手持ちのお金でどの村までいけるかわかる
- いける村までの間に、お友達がいたら手持ちが増える
- 後はしっかりシミュレーション
- 村の順番、お友達を綺麗にまとめようね
from collections import defaultdict
N, K = map(int, input().split())
d = defaultdict(int)
for i in range(N):
A, B = map(int, input().split())
d[A] += B
pos = 0
ab_L = list(d.items())
ab_L.sort()
for node, val in ab_L:
if pos + K >= node:
cost = node - pos
K -= cost
K += val
pos = node
else:
pos += K
K = 0
break
if K != 0:
pos += K
print(pos)
D - Pond
https://atcoder.jp/contests/abc203/tasks/abc203_d
- ◯◯の最小値(最大値)は、 #にぶたん を疑うこと #TIPS
- 値決め打ちにぶたんを疑うに当たって、色々と考えてみる
- $N\times N$のマス目から$K\times K$の区画を切り取った時、中央値を$x$以下にできる？
- これは愚直なら$O(N^2 \times K^2)$でいけそう…
- にぶたんコースなら、ここをどうにか削れたら…
- これは愚直なら$O(N^2 \times K^2)$でいけそう…
- 一部分の区画を見たいので、 #二次元累積和 でしばけそう
- $N \times N$のマス目のうち、$x$以下のマスを1、$x$より大きいマスを0とする
- この前処理を行ってから二次元累積和を作ると、「区画内の、$x$以下のマスの個数」が$O(1)$で出せる
- $K\times K$の区画内で$x$以下のマスの個数が、半分以上→中央値を$x$以下にできる！
- ここまでで、$N\times N$のマス目の前処理に$O(N^2)$、累積和作成で$O(N^2)$
- $K\times K$の区画切り取りを累積和使って全探索して$O((N-K+1)^2)$
- 合計$O(N^2)$でしばける
- にぶたんで$O(log(max(A)))$でしばけるので、勝ち
- $K\times K$の区画内で$x$以下のマスの個数が、半分以上→中央値を$x$以下にできる！
- $N\times N$のマス目から$K\times K$の区画を切り取った時、中央値を$x$以下にできる？
- 実装が面倒くさいので、色々関数切るのが良さげみありますね
N, K = map(int, input().split())
base_L = []
for i in range(N):
base_L.append(list(map(int, input().split())))
# 元々の2次元配列から、「x未満なら1,そうじゃないなら0」の判定配列を作る関数
def make_2d_l(l, n):
ret_L = [[0] * len(l) for _ in range(len(l[0]))]
for i in range(len(l)):
for j in range(len(l[0])):
if l[i][j] <= n:
ret_L[i][j] = 1
return ret_L
# 2次元配列を作る関数
def make_2d_accum(l):
ret_L = [[0] * (len(l[0]) + 1) for i in range(len(l) + 1)]
for i in range(N):
for j in range(len(l[0])):
ret_L[i + 1][j + 1] = ret_L[i][j + 1] + ret_L[i + 1][j] + l[i][j] - ret_L[i][j]
return ret_L
# にぶたん判定用関数
def is_ok(arg):
l = make_2d_l(base_L, arg)
accum_l = make_2d_accum(l)
for i in range(N - K + 1):
for j in range(N - K + 1):
cnt = accum_l[i + K][j + K] - accum_l[i][j + K] - accum_l[i + K][j] + accum_l[i][j]
if cnt >= (K * K) // 2 + (K % 2):
return True
return False
# にぶたんメイン部分
def meguru_bisect(ok, ng):
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
ok = 10 ** 18
ng = -1
print(meguru_bisect(ok, ng))
E - White Pawn
https://atcoder.jp/contests/abc203/tasks/abc203_e
- 縦横$2\times 10^9 + 1$の大きさを持つチェス盤なのでちょっと全探索、愚直は無理
- 条件の日本語難しいので、問題文を読む
- 黒ポーンが無い限り、白ポーンはまっすぐ下にしか降りられない
- 白ポーンの真下に黒ポーンがあったら、白ポーンは進めない
- 斜め下に黒ポーンがあれば、白ポーンは黒ポーンを取れる
- 黒ポーンのある行だけ考えたら良いかな…？
- このあたりで、Cの村移動に似た #シミュレーション 系問題
- 黒ポーンのある行だけ考えたら良いかな…？
- 白ポーンの初期配置から、黒ポーンの存在する行毎にしっかりシミュレーションを行う
- 白ポーンが動ける先と、白ポーンが進めなくなる先をしっかり考える
- 一旦黒ポーン基準に考える
- #主客転倒 ?になるのかな…？
- この黒ポーンは踏めますか？
- →Yes：以降、この列に白ポーンが存在できます
- →No：この列に、現在白ポーンは存在しますか？
- →Yes：以降、この列に白ポーンは存在できません
- →No：もとからこの列に白ポーンは存在していません
- 一旦黒ポーン基準に考える
- 手間だけど、黒ポーンの存在する行ごとに、
- 白ポーンが現在、存在できる列(pos)
- 今後白ポーンが存在できるようになる列(add_L)
- 今後白ポーンが存在できなくなる列(del_L)
- を持って、ワンクッション置いて一括更新する形
- どうせ追加→追加、追加→削除でも、$2\times M$なので…
from collections import defaultdict
N, M = map(int, input().split())
bk_pawn = defaultdict(set)
for i in range(M):
X, Y = map(int, input().split())
bk_pawn[X].add(Y)
bk_L = list(bk_pawn.items())
bk_L.sort()
pos = set([N])
for k, bk_s in bk_L:
add_L = []
del_L = []
for bk in bk_s:
if bk + 1 not in pos and bk - 1 not in pos:
del_L.append(bk)
if bk - 1 in pos or bk + 1 in pos:
add_L.append(bk)
for add in add_L:
pos.add(add)
for dis in del_L:
pos.discard(dis)
print(len(pos))