🔖

[python] ABC182 個人的メモ [AtCoder]

2020/11/09に公開

Python

競技プログラミング

AtCoder

tech

ABC182

所感

abd3完
思ったよりも冷えなかった
eがコンテスト後10分でacしたので，コンテスト中にacしたかった
今回は誤読とか勘違いとか多すぎた
前回もそんな感じだった気がするので，冷静さが足りない

A - twiblr

出力が0以下にはならないので，そこ注意
と思ったら制約でそうはならないっぽい
なので $2\times A+100-B$ を出力すれば良いっぽい

#!/usr/bin/env python3
A, B = map(int, input().split())

print(max(0, 2 * A + 100 - B))

B - Almost GCD

全探索
これだと，サンプルと一致しないけどac

最初kはAの中から選ぶと勘違いしてた
サンプルもそれで矛盾しないし

#!/usr/bin/env python3
N = int(input())
A = [int(x) for x in input().split()]

ans = [0, 0]
for i in range(2, 1000):
    res = 0
    for j in range(N):
        if A[j] % i == 0:
            res += 1
    if res > ans[1]:
        ans[0] = i
        ans[1] = res

print(ans[0])

C - To 3

さっぱりわからず
コンテスト後に見たら制約が $1\leqq N \leqq 10^{18}$ だから18桁以下だから全探索できると分かる
$10^{18}$ 桁以下だと思ってました・・・

bit全探索で解ける
コンテスト後にやったら，数分でacできた
もったいない

$10\% 3 = 1$ を利用しても解けるらしい(公式解説配信より)

#!/usr/bin/env python3
N = input()

ans = 20
for bit in range(1 << len(N)):
    res = ""
    for i in range(len(N)):
        if bit & (1 << i):
            res += N[i]
    if res == "":
        continue
    if int(res) % 3 == 0:
        ans = min(ans, len(N) - len(res))

print(ans if ans != 20 else -1)

D - Wandering

累積和

#!/usr/bin/env python3
from itertools import accumulate

N = int(input())
A = [int(x) for x in input().split()]

cumsum_A = list(accumulate(A))
end_number = list(accumulate([0] + cumsum_A))

max_forward_distance = 0
ans = 0
for i in range(N):
    max_forward_distance = max(max_forward_distance, cumsum_A[i])
    ans = max(ans, end_number[i] + max_forward_distance)

print(ans)

E - Akari

HHKB2020-Eで見た
が，解き方を思い出せなかったので過去記事を見た
ブログ書いてて有効活用できたのは良かった
acできなかったのは良くなかった
また，前回のabcみたいに少しバグらせちゃった

全てのライトから照らせる範囲を探索していくとTLEする(した)
全マスを探索すると計算量が大体 $O(HW)=O(2\times 10^6)$ となる
なので，4回ぐらいまでは全マスを探索してもよさそう
ということで，縦のマスでライトの照らせる範囲を探索し，その後横のマスでライトの照らせる範囲を探索する
ブロックとブロックに挟まれた区間にライトが有れば，その区間は全て照らされると分かるので，それを記録
区間内にライトが有るか無いかだけを見ればおｋ
ブロックに挟まれた区間の探索に $O(HW)$ ，照らされてるマスの記録に $O(HW)$ 掛かる
探索は縦と横で2回あるから $O(4\times HW)$ となり十分制限時間内に間に合う
盤面の周囲をブロックで囲っておくと実装が楽

#!/usr/bin/env python3
H, W, N, M = map(int, input().split())

# 盤面の周囲をブロックで囲む
grid = [[-1] + [0] * W + [-1] for _ in range(H)]
W += 2
H += 2
grid = [[-1] * (W)] + grid + [[-1] * (W)]
for _ in range(N):
    h, w = map(int, input().split())
    grid[h][w] = 1
for _ in range(M):
    h, w = map(int, input().split())
    grid[h][w] = -1

bright = [[0] * W for _ in range(H)]
# 横方向のライトに照らされるマスの探索
for h in range(H):
    block = 0
    paint = False
    for w in range(W):
        # ブロックに当たった時
        if grid[h][w] == -1:
            if paint:
                for k in range(block + 1, w):
                    bright[h][k] = 1
                paint = False
            block = w
        if grid[h][w] == 1:
            paint = True

# 縦方向のライトに照らされるマスの探索
for w in range(W):
    block = 0
    paint = False
    for h in range(H):
        # ブロックに当たった時
        if grid[h][w] == -1:
            if paint:
                for k in range(block + 1, h):
                    bright[k][w] = 1
                paint = False
            block = h
        if grid[h][w] == 1:
            paint = True

ans = 0
for h in range(H):
    ans += sum(bright[h])

print(ans)