Zenn
📌

AtCoder ARC 109 個人的メモ

2020/11/29に公開
Python
#
競技プログラミング
AtCoder
tech

所感

a1完
arc179score

A - Hands

絵描いて，場合分け

#!/usr/bin/env python3
a, b, x, y = map(int, input().split())

if a > b:
    can1 = x + (a - b - 1) * y
    can2 = ((a - b) * 2 - 1) * x
    print(min(can1, can2))
else:
    can1 = x + (b - a) * y
    can2 = ((b - a) * 2 + 1) * x
    print(min(can1, can2))

B - log

二分探索

最も長い丸太N+1から，長さ１から小さい順にできるだけ多くの丸太を切り出すのが良さそう
二分探索で切り出せる丸太の個数を探す

コンテスト中は答えを直接求めようとした
切り出す丸太の数をkとした時，等差数列の総和の公式より以下の不等式が成立すればおｋ

\frac{k(k+1)}{2} \leqq N+1

これを変形して以下の様になる

k^2+k-2(N+1)\leqq 0

この式のkの最大値を求めれば良いので，答えは二次関数の解の公式より以下の様に求まる

k=\frac{\sqrt{8N+9}-1}{2}

で，これをそのまま実装したら平方根の誤差でwaした
でも，他の解法も思いつかなかった
まぁ，二分探索の想定解法思いつけなかったのは実力不足だよな～って思った

#!/usr/bin/env python3
def solve(n):
    return n * (n + 1) // 2


N = int(input())

left = 0
right = N + 1
while abs(right - left) > 1:
    mid = abs(right + left) // 2
    if solve(mid) <= N + 1:
        left = mid
    else:
        right = mid

print(N - left + 1)
float型の話

float型に関する公式ドキュメント
上によると，float型は56bitで表されてるっぽい
2^{56}=9007199254740992\sim 10^{16}なので，16桁未満なら精度は大丈夫そう
しかし，今回のARC109B問題は最大18桁の計算をすることになるので，精度が足りなかったっぽい

解決方法

  • decimalを使う
    decimalの公式ドキュメント
    decimalモジュールを使うと，10進数を正確に表現できる
    デフォルトで28桁まで計算精度があるらしい
    これを使えばacできる
    decimalへの引数はint，文字列，float等だが，floatだと誤差が既に生じた状態になっているので，他のintか文字列で渡す
from decimal import Decimal

N = int(input())

ans = N + 1 - ((Decimal(8 * N + 9)).sqrt() - 1) // 2

print(ans)
  • ニュートン法を使う
    パッと見た感じ二分探索では？
    よく見てないけど

C - Large RPS Tournament

一工夫してシミュレーションすればできる
典型的なダブリングらしい?

#!/usr/bin/env python3
def solve(N, K, S):
    wins = (("R", "S"), ("S", "P"), ("P", "R"))
    for _ in range(K):
        hands = S * 2
        S = ""
        for i in range(0, len(hands), 2):
            a = hands[i]
            b = hands[i + 1]
            win_a = False
            for x, y in wins:
                if a == x and b == y:
                    win_a = True
                    break
            if win_a:
                S += a
            else:
                S += b

    return S[0]


N, K = map(int, input().split())
S = input()
print(solve(N, K, S))

参考

Discussion