AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC169 E - Count Median

競プロ

問題原文

atcoder.jp

解法

【注意】雰囲気証明なので間違っている可能性が十分にあります！！！あくまでも「こうsubmitしたくなる気持ち」の１つとして読んでいただければ

考えうる最小の中央値は、全ての区間について A_i を取った時。これを m とする。
考えうる最大の中央値は、全ての区間について B_i を取った時。これを M とする。

ここから簡単のために N が奇数の場合を考える。 ある数 X が中央値になるにはどんな条件が必要かを考えてみる。すると以下がわかる。

  1. X を取れるような区間がある
  2. 1で使ったもの以外で、 X 以下の数を取れるような区間が [\frac{N}{2}\rbrack 個ある。
  3. 2で使ったもの以外で、 X 以上の数を取れるような区間が [\frac{N}{2}\rbrack 個ある。

2, 3 の条件から、

  1. X より小さい数しか取れないような区間が [\frac{N}{2}\rbrack 個より多くある場合
  2. X より大きい数しか取れないような区間が [\frac{N}{2}\rbrack 個より多くある場合

X は中央値になり得ないことがわかる。
逆にそうでない場合、 「 X を取れるような区間がある 」という条件さえ満たせば X は中央値になりうることがわかる。

X 以下の数を取れるような区間が常に [\frac{N}{2}\rbrack 個取れるような下限はどこだろう？と考えると、それは A_i の中央値（= m）であることに気づく。
X 以上の数を取れるような区間が常に [\frac{N}{2}\rbrack 個取れるような上限はどこだろう？と考えると、それは B_i の中央値（= M）であることに気づく。

それぞれ、当然 m \leq X \leq M を区間として含む。
ので、 区間[m, M\rbrack 内の中央値は全部作れそうな気持ちになる。

偶数の場合は0.5刻みになる。

実装

N = int(input())
A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if N % 2 == 1:
    M = B[N // 2]
    m = A[N // 2]
    print(M - m + 1)

else:
    M = (B[N // 2 - 1] + B[N // 2]) / 2
    m = (A[N // 2 - 1] + A[N // 2]) / 2
    print(int((M - m + 0.5) * 2))

感想

中央値系は苦手。。。だけどメジアンメジアンを何度も解いていたのでギリギリ解けた。。。
証明難しい。多分間違ってるのでコメント待ってます。。。

ABC169 D - Div Game

競プロ

問題原文

atcoder.jp

解法

N の 因数であれば当然割り切れるので、素因数分解をしておきたい気持ちになる。

一度使った z は二度使えないので、 p^{e} を因数として持つ場合には、 p^{1}, p^{2}, p^{3}... と使っていきたくなる。

実装

from collections import Counter
N = int(input())
 
def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table
 
 
T = prime_factorization(N)
C = Counter(T)
 
ans = 0
for v in C.values():
    nx = 1
    while v >= nx:
        v -= nx
        ans += 1
        nx += 1
 
print(ans)

感想

Cが沼だったので泣きながら逃げてきた。
解きやすい問題でよかった（茶diffなのは納得いかないけど）

ABC169 C - Multiplication 3

競プロ

問題原文

atcoder.jp

解法

少数を少数のまま扱うと誤差で死ぬ。

少数第二位まで与えられるので、 ×100をしてから大丈夫そうに思えるが、floatで受け取った段階で誤差が出てるので死ぬ。

文字列として受け取ってから変換すればOK！

実装

A, B = input().split()
A, B = int(A), int(B.replace('.', ''))
print(A * B // 100)

感想

阿鼻叫喚地獄を見た、、、

ARC005 C - 器物損壊！高橋君

競プロ

問題原文

atcoder.jp

解法

「２回まで壁を壊せる」→「壁に侵入するコストを１として、ゴールまでの最小コストが２以下なら２回までしか壁を壊してない」と言い換える。

辺のコストが０か１なので、01BFSが使える。

実装

from collections import deque
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]

sh, sw = -1, -1
gh, gw = -1, -1
for h in range(H):
    for w in range(W):
        if G[h][w] == 's':
            sh, sw = h, w
        if G[h][w] == 'g':
            gh, gw = h, w


dist = [[float('inf')] * W for _ in range(H)]
dist[sh][sw] = 0
que = deque([[sh, sw]])

while que:
    nh, nw = que.pop()
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx_h, nx_w = nh + dh, nw + dw
        if not ((0 <= nx_h < H) and (0 <= nx_w < W)):
            continue

        if dist[nx_h][nx_w] != float('inf'):
            continue

        if G[nx_h][nx_w] == '#':
            dist[nx_h][nx_w] = dist[nh][nw] + 1
            que.appendleft([nx_h, nx_w])
        else:
            dist[nx_h][nx_w] = dist[nh][nw]
            que.append([nx_h, nx_w])

print('YES' if dist[gh][gw] <= 2 else 'NO')

感想

まぁこれはさくさく。

天下一2013予選B B - 天下一後入れ先出しデータ構造

競プロ

問題原文

atcoder.jp

解法

まともにデータを持っては間に合わないので、 (数字, 個数) というように持つ。
スタックの要素数は、↑の形式で持っても毎回舐めると間に合わないので、変数で管理するようにする。

↓のちょっとめんどくさいバージョンという感じ。
at274.hatenablog.com

実装

Q, L = map(int, input().split())
stack = []
stack_size = 0

for q in range(Q):
    query = list(input().split())
    if query[0] == 'Push':
        n, m = int(query[1]), int(query[2])
        stack_size += n
        if stack_size > L:
            print('FULL')
            exit()
        stack.append([m, n])

    elif query[0] == 'Pop':
        n = int(query[1])
        stack_size -= n
        if stack_size < 0:
            print('EMPTY')
            exit()

        while n:
            if n >= stack[-1][1]:
                n -= stack[-1][1]
                stack.pop()
            else:
                stack[-1][1] -= n
                n = 0

    elif query[0] == 'Top':
        if stack_size == 0:
            print('EMPTY')
            exit()
        print(stack[-1][0])

    elif query[0] == 'Size':
        print(stack_size)

print('SAFE')

感想

今なら茶diffがつきそうな気がする。

ARC007 C - 節約生活

競プロ

問題原文

atcoder.jp

解法

sample2で貪欲の線はなくなる。

制約が小さいので「どこからテレビをつけ始めるか」のbit全探索ができる。

実装

過去にテレビを点けといたことにして、今から N 分間ついてればOKみたいな感じにした。
modでやればよかったと後悔（まぁいいか）

from itertools import product
S = list(input())
N = len(S)

ans = float('inf')
for pattern in product([0, 1], repeat=N):
    pattern = list(pattern)
    X = [0] * (2 * N)
    for i, p in enumerate(pattern):
        if p == 0:
            continue
        for j, s in enumerate(S, start=i):
            if s == 'x':
                continue
            X[j] = 1
            if j + N < 2 * N:
                X[j + N] = 1
    if sum(X[N:]) == N:
        ans = min(ans, sum(pattern))

print(ans)

感想

推定diff1400ぐらいらしい。こういう実装問題は普通にすき。
令和ABCなら800はつきそうだなぁ。

DigitalArts 2012 B - Password

競プロ

問題原文

atcoder.jp

解法

与えられたパスワードと同じものはダメ というのが少し面倒。

２種類正解候補を考えられればどちらかは必ず答えになりうる。

ということで、できるだけ z に近いものを使う場合のパスワード と できるだけ a に近いものを使う場合のパスワード を計算した。

実装

ほくほく。

S = input()
P = sum([ord(s) - ord('a') + 1 for s in S])

# できるだけ z に近いものを使うように
cnt = 0
P1 = P
ans1 = []
while P1 and cnt < 20:
    p = min(P1, 26)
    ans1.append(p)
    P1 -= p
    cnt += 1

# できるだけ a に近いものを使うように
cnt = 0
P2 = P
ans2 = []
while P2 and cnt < 20:
    p = max(1, P2 - 26 * (20 - cnt - 1))
    ans2.append(p)
    P2 -= p
    cnt += 1

ans1 = ''.join([chr(ord('a') + a - 1) for a in ans1])
ans2 = ''.join([chr(ord('a') + a - 1) for a in ans2])

if P1 == 0 and ans1 != S:
    print(ans1)
elif P2 == 0 and ans2 != S:
    print(ans2)
else:
    print('NO')

感想

推定水diffらしい。令和ABCで出たら半分は通しそう。
もっとうまい方法あったら教えてください。