ebisuke競プロ初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。C言語も少しだけ勉強中

AtCoder-ABC198 C - Compass Walking【Python解答例】

f:id:ebisuke33:20210411233753p:plain
AtCoder Beginner Contest198のC - Compass WalkingについてPythonの解答例を記事にしていきます。
atcoder.jp


AtCoder Beginner Contest198 C - Compass Walking

C - Compass Walking

問題文

2 次元平面上の原点に高橋君がいます。
高橋君が 1 歩歩くと、いまいる点からのユークリッド距離がちょうど R であるような点に移動することができます(移動先の座標が整数である必要はありません)。これ以外の方法で移動することはできません。
高橋君が点 (X,Y) に到達するまでに必要な歩数の最小値を求めてください。
なお、点 (x1,y1) と点 (x2,y2) のユークリッド距離は √(x1−x2)2+(y1−y2)2 で与えられます。

制約

・1≤R≤10^5
・0≤X,Y≤10^5
・(X,Y)≠(0,0)
・入力は全て整数

解答例

r, x, y = map(int,input().split())

R_tmp = x**2 + y**2
R = pow(R_tmp, 0.5)

if R < r:
    ans = 2
else:
    ans = -(-R // r)

print(int(ans))

解説

1歩でrだけ進む高橋君が点(X,Y)に到着するのに必要な最小の歩数を答える問題です。

原点から点(X,Y)までの距離を求めます。
問題文にある数式の通りにRとして計算しました。

必要な歩数はこのRを歩幅rで割った余り切り上げた値が答えとなります。
ただし、Rが歩幅rより小さいときは1歩でたどり着くことはできず、遠くに寄り道する必要があるので2歩になります。

このようにして求めた必要な歩数を出力したらACでした。



ABC198の関連記事はこちら
ebisuke33.hatenablog.com

AtCoder-ABC198 A - Div / B - Palindrome with leading zeros【Python解答例】

https://cdn-ak.f.st-hatena.com/images/fotolife/e/ebisuke33/20210411/20210411231954.png
AtCoder Beginner Contest198のA とB問題についてPythonの解答例を記事にしていきます。
atcoder.jp



AtCoder Beginner Contest198 A - Div

A - Div

問題文

N 個の互いに区別できないお菓子を、A君とB君で分け合います。 両者とも 1 個以上の整数個のお菓子を得るような分け方は何通りありますか?

制約

・N は整数
・1≤N≤15

解答例

n = int(input())

print(n-1)

解説

N個のお菓子の分け方が何通りあるか答える問題です。

A君とB君はどちらも1個以上はもらわないといけないので、A君は最大でN-1個のお菓子をもらえます。
最小で1、最大でN-1なので分け方もN-1通りとなります。

入力をnとするとn-1を出力すればOKでした。


AtCoder Beginner Contest198 B - Palindrome with leading zeros

B - Palindrome with leading zeros

問題文

整数 N が与えられます。
N を十進法で表した文字列の先頭に 0 個以上の 0 をつけることで、回文にすることはできますか?

制約

・0≤N≤10^9

解答例

n = input()

if n == "0":
    print("Yes")
    exit()

num = -(-len(n)//2)

for i in range(len(n)):
    if n[-1] == "0":
        n = n[:-1]
    else:
        break


num = len(n)//2

flag = True
for i in range(num):
    if n[i] == n[-(i+1)]:
        continue
    else:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")

解説

与えられたNの先頭に任意の数だけ0を足して回文にできるか答える問題です。

先頭に0を足すことができるので、小さい桁から連続した0を消していきました。

次に判定用のフラグを用意し、0を消した文字列の先頭と末尾を比較します。
先頭と末尾が同じなら回文にできるので比較を続けていきます。
すべての文字を比較し終えることができたらフラグは変更せずYesを出力します。
どこかで違う部分が出たらフラグをFalseにしてNoを出力します。

このようなプログラムでACをとれました。



続いてABC198のC問題も記事にしていきたいと思います。


ABC198の関連記事はこちら
ebisuke33.hatenablog.com

AtCoder-ABC197 C - ORXOR【Python解答例】

f:id:ebisuke33:20210328211923p:plain
AtCoder Beginner Contest197のC - ORXORについてPythonの解答例を記事にしていきます。
atcoder.jp


AtCoder Beginner Contest197 C - ORXOR

C - ORXOR

問題文

長さ N の数列 A が与えられます。
この数列を、1 つ以上の空でない連続した区間に分けます。
その後、分けた各区間で、区間内の数のビット単位 OR を計算します。
こうして得られた全ての値のビット単位 XOR として考えられる最小値を求めてください。

制約

・1≤N≤20
・0≤Ai<2^30
・入力に含まれる値は全て整数である

解答例

n = int(input())
A = list(map(int, input().split()))

# 解答ansはINFで初期化
INF = 1e9

ans = INF

# 数列が1つだけなら演算不可
if len(A) == 1:
    print(A[0])
else:
    # 区間の分け方をbit化
    for bit in range(2**(n-1)):
        # 区間内のbit単位or
        log_sum = A[0]
        # すべての値のbit単位xor
        xor = 0
        # 数列を探索
        for i in range(1,n):
            # bitが1なら区間終了
            if (bit >> (i-1)) & 1:
                # xorを計算
                xor ^= log_sum
                # orは0にしたあと数列A[i]とbit演算
                log_sum = 0
                log_sum |= A[i]
            else:
                # bitが0ならそのまま数列A[i]とbit演算
                log_sum |= A[i]

        # A[n]でループを抜けたらxorを計算
        xor ^= log_sum
        # 最小のxorをansに記録
        ans = min(ans,xor)

    print(ans)

解説

長さNの数列Aが与えられ、空でない任意の区間にわけます。
この区間内の数のビット単位orを計算し、求まったすべての値のビット単位xorの中で最小値を答える問題です。

数列の長さは20までなので、bit全探索を用いて区間の分け方を考えていきます。

入力例1を例にあげると、コードのbitが0のときは区間を分けずに[1,5,7]のビット単位orを求めます。
Pythonではビット演算子|(読み方がわかりません (^_^;))を用いることでビット単位orが求まり、区間を分けないのでビット単位orがそのままビット単位xorです。
bitが1(2進数で01)のときは[1,5]と[7]に分け、区間のビット単位orを求めました。
xorはビット演算子^を用いて計算できますので、区間が終われば順次ビット単位xorを演算していきます。
bitが2(2進数で10)のときは[1]と[5,7]に分け、同様にビット単位xorを演算します。
bitが3(2進数で11)のときは[1]と[5]および[7]の3つの区間分け、xorを求めました。

このようにbitの値によって区間の分け方を決めて、その分け方によってbit演算を行っていきます。
すべての区間の分け方を試して、最も小さいxorをansに代入すればOKです。

この問題はPypyでないとTLEとなりました。
これ以上、計算量の落とし方がわかりませんでしたのでおとなしくPypyで提出してACをとれました。




ABC197の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC197 D - Opposite【Python解答例】

f:id:ebisuke33:20210328104732p:plain
AtCoder Beginner Contest197のD - OppositeについてPythonの解答例を記事にしていきます。
atcoder.jp


AtCoder Beginner Contest197 D - Opposite

D - Opposite

問題文

x 軸の正の向きを右、y 軸の正の向きを上とする 2 次元座標平面上に、p0,p1,p2,…,pN−1 の N 個の頂点からなる正 N 角形があります。
ここで N は偶数であることが保証され、頂点 p0,p1,p2,…,pN−1 はこの順に反時計回りに並んでいます。
pi の座標を (xi,yi) とします。
x0,y0,xN2,yN2 が与えられるので、x1,y1 を求めてください。

制約

・4≤N≤100
・N は偶数
・0≤x0,y0≤100
・0≤xN2,yN2≤100
・(x0,y0)≠(xN2,yN2)
・入力に含まれる値は全て整数である

解答例

import math
from math import pi

n = int(input())

x0, y0 = map(int,input().split())
x_half, y_half = map(int,input().split())

# n角形の中心座標
center_x = (x_half + x0) / 2

center_y = (y_half + y0) / 2

# n角形の中心から各頂点までの距離
r_tmp = (x_half - x0)**2 + (y_half - y0)**2

r = pow(r_tmp,0.5) / 2

# 中心から(x1,y1)への角度
angle_0 = math.atan2(y0 - center_y, x0 - center_x)

angle_tmp = 2 * pi / n

angle_target = angle_0 + angle_tmp

# x1,y1の座標を求める
x1 = center_x + r * math.cos(angle_target)

y1 = center_y + r * math.sin(angle_target)


print(x1,y1)

解説

正n角形のx0,y0とちょうど半分の頂点座標が与えられてとき、x0,y0の次の頂点x1,y1の座標を答える問題です。

この問題の答えは計算で求まりますので、コードの順にそって説明していきます。

問題の条件から正n角形の中心座標が求まりますので、(center_x,center_y)座標とおいて求めました。

この頂点から各頂点までの距離をrとおいて、この距離も三平方の定理から求まります。

続いて中心から(x0,y0)に向かう角度を調べました。
これをベクトルと考えればx成分はx0 - center_x、y成分はy0 - center_yです。
mathモジュールをインポートし、アークタンジェントを用いると中心から(x0,y0)への角度が計算できます。
正n角形の中心から各頂点を結ぶ線分のつくる角はそれぞれ2π/nであり、先ほど求めた角度に2π/nを足した値が、中心から(x1,y1)へ向かう角度angle_targetとなります。

rにcos(angle_target)をかけた値と中心座標のxを足した値がx1、rにsin(angle_target)をかけた値と中心のy座標を足した値が求めるy1となります。

最後にx1,y1を出力してACでした。




ABC197の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com