AtCoder Beginner Contest 239 参加記録

更新

タグ:

AtCoder Beginner Contest 239に参加しました。

結果はABCD4完・1ミスでした。

レーティング変化は312→335で微増。

灰と茶色の境界あたりの問題は結構解けるようになりました。ただレートを上げるには茶色の問題も解けるようにならないといけませんねー。

A - Horizon

問題文の通りに書くだけです。

import math
h = int(input())

print(math.sqrt(h*(12800000 + h)))

B - Integer Division

前回のコンテストで覚えた「//」を早速使いました。pythonだと楽ちんですね。

1回ミス提出してしまったのが痛恨の極み。

x = int(input())

print(x // 10)

C - Knight Fork

全探索で解きます。
点(x1, y1)を中心とする半径√5の円周上に位置する格子点は

(x1 + 1, y1 + 2)
(x1 + 1, y1 - 2)
(x1 + 2, y1 + 1)
(x1 + 2, y1 - 1)
(x1 - 1, y1 + 2)
(x1 - 1, y1 - 2)
(x1 - 2, y1 + 1)
(x1 - 2, y1 - 1)

の8つです。

あとはこの8つの点のどれかが点(x2, y2)を中心とする半径√5の円周上に存在するか判定します。これは円の方程式を使えばおk

円の方程式なんて10年ぶりぐらいに使ったわい。

x1, y1, x2, y2 = map(int, input().split())

point_list = [
    [x1+1, y1+2],
    [x1+1, y1-2],
    [x1+2, y1+1],
    [x1+2, y1-1],
    [x1-1, y1+2],
    [x1-1, y1-2],
    [x1-2, y1+1],
    [x1-2, y1-1]
]
for a_b in point_list:
    a, b = a_b
    if x2**2-2*a*x2+a**2+y2**2-2*b*y2+b**2-5 == 0:
        print("Yes")
        exit(0)
print("No")

D - Prime Sum Game

二人が最適な戦略を取るということは、
「A以上B以下の整数の中に、C以上D以下のどの整数を足しても素数にならない数がある」が
①真のとき
=高橋君はその数を選択すれば必ず勝てる
=高橋くんは必ず勝つ
②偽のとき
=高橋君は絶対に勝てない
=青木君は必ず勝つ

ということです。
なので「A以上B以下の整数の中に、C以上D以下のどの整数を足しても素数にならない数がある」の真偽を判定します。

とりあえず素数を判定するための関数をあらかじめ用意しておきます。続いて、ループを回してA以上B以下の整数の中にC以上D以下のどの整数を足しても素数にならない数が存在するか調べます。そのような数が見つかった時点で高橋君の勝ち、見つからなければ青木君の勝ちとなります。

import math
a, b, c, d = map(int, input().split())


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


for n in range(a, b+1):
    for m in range(c, d+1):
        if is_prime(n+m):
            break
        if m == d:
            print("Takahashi")
            exit(0)
print("Aoki")

E - Subtree K-th Max

問題文は読んだけど意味がわからなかったよ~\(^o^)/

F~Ex

問題文すら見ていないので省略。

感想

ギリ茶色レベルの問題なら安定して解けるようになってきました。問題文の読み替えができるようになったのと、Pythonくんが有能だからだと思います。

あともうちょっとで茶色!ガンバリマス。