📝

AtCoder Beginner Contest 279 レポート

2022/11/28に公開

AtCoder

Python 3

tech

摘要

ABCD4完でした．E問題に1時間以上かけるも解けず．
D問題に関しても，微分という方針にすぐ辿り着いたにも関わらず， $y'=0$ を解かずに二分探索するという回りくどい方法をとってしまいました．

ABC279

コンテスト名: トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)
順位: 1413th / 7787
パフォーマンス: 1212
レーティング: 1216 → 1216 (±0)
コンテスト参加回数: 64

A - wwwvvvvvv

A - 問題

文字列 $S$ について， $(vの個数)+2*(wの個数)$ を求めよ．

A - 解法

特記事項なし．

A - ACコード

def main():
    S = input()

    dic = {'v': 1, 'w': 2}

    ans = 0
    for si in S: ans += dic[si]

    print(ans)


if __name__ == '__main__': main()

B - LOOKUP

B - 問題

文字列 $S, T$ について， $T$ が $S$ の連続部分文字列であるか判定せよ．

B - 解法

特記事項なし．
「連続」の条件を読み落として数分無駄にした．

B - ACコード

def main():
    S, T = input(), input()

    lens, lent = len(S), len(T)

    ans = 'No'
    for i in range(lens - lent + 1):
        if S[i:i + lent] == T:
            ans = 'Yes'
            break

    print(ans)


if __name__ == '__main__': main()

C - RANDOM

C - 問題

$H$ 行 $W$ 列の二次元配列 $S, T$ について， $S$ の列を並び替えることで $T$ と等しくできるか判定せよ．

C - 解法

$S, T$ それぞれの列について，ソートしたものが一致するか判定する，

C - ACコード

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    T = [input() for _ in range(H)]

    arr_s, arr_t = [[[x[i][j] for i in range(H)] for j in range(W)] for x in (S, T)]
    arr_s.sort()
    arr_t.sort()

    ans = 'Yes' if arr_s == arr_t else 'No'
    print(ans)


if __name__ == '__main__': main()

D - Freefall

D - 問題

非負整数 $x$ の関数 $y( = \frac{A}{\sqrt{x+1}} + Bx)$ の最小値を求めよ．

D - 解法

とりあえず導関数を求めた．

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

そこからなぜか単調減少な $y'$ について符号が変わる $x$ を二分探索で求めた．
考えてみれば，

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

こうするだけでよかった．

D - ACコード

def main():
    global A, B
    A, B = map(int, input().split())

    idx = binary_search()
    ans = min([B*x + A/pow(x+1, 0.5) for x in (idx, idx+1)]) if idx >= 0 else A
    print(ans)


def binary_search():
    ok, ng = -1, 10**18

    def is_ok(x): return B - A*pow(x+1, -1.5)/2 < 0
    while abs(ok - ng) > 1:
        md = (ok + ng)//2
        if is_ok(md): ok = md
        else: ng = md

    return ok


if __name__ == '__main__': main()

感想

E問題全然わかりませんでした．精進します．