24か月前公開・24か月前更新・0 pv・7 min read

AtCoder Beginner Contest 279 まとめ（A~F)

AtCoderABCPythonABC279

https://cdn.magicode.io/media/notebox/7f5ed2e7-cdb0-4498-bb40-77269a70f8e8.jpeg

AtCoder Beginner Contest 279

ABC261の個人的に実装できた解法まとめです。

特筆がなければ言語はPyPy3です。

*がついてるものは時間内にACできた問題になります。

A - wwwvvvvvv*

str.count()でvとwを数えます。

S = input()
print(S.count('v') + S.count('w')*2)

提出 #36792058

B - LOOKUP*

Pythonなら文字列の内包関係をin演算子で評価可能です。

YN = ['No', 'Yes']

S = input()
T = input()
print(YN[T in S])

提出 #36794609

C - RANDOM*

列ごとのtupleにしてCounterに入れて等号比較します。

import sys
from collections import Counter

def i2s(): return sys.stdin.readline().rstrip()
def i2nn(): return list(map(int, i2s().split()))
YN=['No','Yes']

H,W=i2nn()
S=[i2s() for _ in range(H)]
T=[i2s() for _ in range(H)]
print(YN[
    Counter(tuple(S[r][c] for r in range(H)) for c in range(W)) ==
    Counter(tuple(T[r][c] for r in range(H)) for c in range(W))
    ])

提出 #36833421

D - Freefall *

x

秒超能力を使ったときの落下時間

f(x)

を最小化します。

f(x)

を微分して２分探索で極限を求めればよいです。

f(x) = A (1 + x)^{-\frac{1}{2}} + B x

f'(x) = {-\frac{A}{2}} (1 + x)^{-\frac{3}{2}} + B

ただし、「

f'(x_z) <= 0

となる最大の整数

x_z

」のような条件で二分探索すると、

f'(x_r) = 0

の実数解

x_r

が

x_r

よりも

x_r+1

に近い場合に不正解になります。

例えば、

A=10, B=1

のとき、

f'(x_r) = 0

の解

x_r \simeq 1.924

ですが

x_z=1

よりも

x_z + 1 = 2

の方が実数解に近く、

f(x)

も小さくなります。

このため、解を

min(f(x), f(x+1)

としています。

import sys
def i2s(): return sys.stdin.readline().rstrip()
def i2nn(): return list(map(int, i2s().split()))

A,B=i2nn()

def f(x): return A * (1+x)**-0.5 + B*x
def fd(x): return -0.5 * A * (1+x)**(-1.5) + B

def main():
    
    def is_ok(x) -> bool:
        return fd(x) <= 0

    ok = 0
    ng = -(-A//B)
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    
    
    print(min(f(ok), f(ng)))
    return

main()

提出 #36832992

別解

普通に導関数の解を計算しておけば二分探索も必要なく

O(1)

です。

f'(x) = 0 \Leftrightarrow x = \left( \frac{A}{2B} \right) ^ \frac{2}{3} - 1

import sys
import math
def i2s(): return sys.stdin.readline().rstrip()
def i2nn(): return list(map(int, i2s().split()))
 
A,B=i2nn()
def f(x): return A * (1+x)**-0.5 + B*x
def g(A,B): return (A/(2*B))**(2/3) - 1
 
x = max(0, math.floor(g(A, B)))
print(min(f(x), f(x+1)))

提出 #36840981

E - Cheating Amidakuji*

$B$ に対して全ての $A_i$ の入れ替えを実行します
$B_j \Rightarrow j$ となる最終的な $B$ の逆写像 $inv$ を得ます
もう一度 $B$ に対して $A_i$ の入れ替えを順に行いますが、このとき「 $i$ 回目の操作で入れ替わることになる数のペア $B_{A_i}, B_{A_i + 1}$ 」が確認できます
「 $i$ 回目の入れ替えをスキップした場合の最終的な $inv$ 」とはすなわち「 $inv_{B_{A_i}}, inv_{B_{A_i + 1}}$ をスワップしたもの」であるので、「 $inv$ のスワップ → $inv_1$ を出力 → 再スワップで戻す」という手順を繰り返すことで解答を出力できます

import sys

def i2s(): return sys.stdin.readline().rstrip()
def i2nn(): return list(map(int, i2s().split()))

N,M=i2nn()
A=i2nn()

B = list(range(N+1))
for a in A:
    B[a], B[a+1] = B[a+1], B[a]
inv = {b: i for i, b in enumerate(B)}

ans = []
for a in reversed(A):
    x, y = B[a], B[a+1] = B[a+1], B[a]
    inv[x], inv[y] = inv[y], inv[x]
    ans.append(inv[1])
    inv[x], inv[y] = inv[y], inv[x]
print(*reversed(ans), sep='\n')

提出 #36835330

F - BOX

要素数1のリストをノードして扱います
- ルートノードの要素は箱の番号
- 非ルートノードの要素は親ノードへの参照
root[i] には箱i を示すルートノードが格納されています
parent[j] にはボールj の親ノードが格納されています

操作1

箱Y の中身を箱X の子にする

ルートノードroot[Y]を親ノードをroot[X]とします
- root[Y]は親ノードを持つのでルートノードではなくなります
root[Y]に新たなルートノード[Y]を代入し、元ルートノードへの直接的な参照はできなくなります

操作2

あらたなボールを追加し箱X の子にする

parent[j] に root[X] を追加します

操作3

ボールX の箱の番号 = ルートノードを得る

parent[X] からルートノードまでを再帰的に親ノードをたどります
その際経路を記憶し、各ノードにルートノードを設定し直すことでPath Compressionします(Union-Find要素)

import sys
sys.setrecursionlimit(2**31-1)
 
def i2s(): return sys.stdin.readline().rstrip()
def i2nn(): return list(map(int, i2s().split()))
N,Q=i2nn()
 
root = [[i] for i in range(N+1)]
parent = list(root)
for _ in range(Q):
    q, *v = i2nn()
    if q == 1:
        X, Y = v
        root[Y][0] = root[X]
        root[Y] = [Y]
        continue
 
    elif q == 2:
        X, = v
        parent.append(root[X])
        continue
    
    else:
        X, = v
        cur = parent[X]
        children = []
        while type(cur[0]) != int:
            children.append(cur)
            cur = cur[0]
        for child in children:
            child[0] = cur
        print(cur[0])
        continue