Ccmmutty logo
Commutty IT
・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 *

xx秒超能力を使ったときの落下時間f(x)f(x)を最小化します。 f(x)f(x)を微分して２分探索で極限を求めればよいです。
f(x)=A(1+x)−12+Bxf(x) = A (1 + x)^{-\frac{1}{2}} + B x
f′(x)=−A2(1+x)−32+Bf'(x) = {-\frac{A}{2}} (1 + x)^{-\frac{3}{2}} + B
ただし、「f′(xz)<=0f'(x_z) <= 0となる最大の整数xzx_z」のような条件で二分探索すると、f′(xr)=0f'(x_r) = 0の実数解xrx_rがxrx_rよりもxr+1x_r+1に近い場合に不正解になります。
例えば、A=10,B=1A=10, B=1のとき、f′(xr)=0f'(x_r) = 0の解xr≃1.924x_r \simeq 1.924ですがxz=1x_z=1よりもxz+1=2x_z + 1 = 2の方が実数解に近く、f(x)f(x)も小さくなります。
このため、解をmin(f(x),f(x+1)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)O(1) です。
f′(x)=0⇔x=(A2B)23−1f'(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*

  1. BBに対して全てのAiA_iの入れ替えを実行します
  2. Bj⇒jB_j \Rightarrow j となる最終的なBBの逆写像invinvを得ます
  3. もう一度BBに対してAiA_iの入れ替えを順に行いますが、このとき「ii回目の操作で入れ替わることになる数のペア BAi,BAi+1B_{A_i}, B_{A_i + 1}」が確認できます
  4. 「ii回目の入れ替えをスキップした場合の最終的なinvinv」とはすなわち「invBAi,invBAi+1inv_{B_{A_i}}, inv_{B_{A_i + 1}} をスワップしたもの」であるので、「 invinvのスワップ → inv1inv_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
提出 #36840981

Discussion

コメントにはログインが必要です。