ABC198参戦記

もう少しでABCも200回ですね。
ABC170回からブログで復習も兼ねて参加した記録を付けていますが、もう少しで30回です！
緑までまだ先は長そうな気もしますが、楽しみながら続けられれば良いなと思います。

この記事は、先週はABCが開催されていなかったので、1週間ぶりのABCだったABC198の振り返り記事です。
私は、茶色下位から中位のPython3で参加しています。
ACコードも載っているので、もしかすると、はじめたばかりの方の役に立ったりしたら嬉しいな。と思いつつ、主に私が振り返る用の記事として書いています。

A – Div

標準入出力が出来るかを問われる問題。植木算の問題。

N個のお菓子の間に仕切りを入れれるパターンは何個ですか。と読み解きました。
仕切りを入れれるパターンはN個のお菓子の間の数ですね。
よって、出力する値は、N-1 になります。

# AtCoder Beginner Contest 198
# A - Div

N=int(input())

print(N-1)

B – Palindrome with leading zeros

繰り返し処理と、プログラミングで使用される型の取り扱い、条件分岐と文字列の回文が作れるかどうかを問われる問題。

上記のように書くとプログラミングの基本的な問題である、fizz buzz問題と同じ要素が入っている問題のように見えますね。

問題文中には、先頭に0を何個かつけると書いていますが、末尾が0なら0を取り除くことでも判定が可能になります。末尾が0か否かは、10で割った余りが0か否かを確認すればOKです。

次に、回文判定の部分ですが、
Pythonでは、文字列をスライス操作することで、反転させた文字列を作ることが可能です。

文字列のスライス操作は、Sが文字列として、S [ start_index : stop_index : step ] で、処理できます。
ここのstepに -1 を指定すれば、逆順にした文字列が取得できます。

S="negibose2020"
print(S[3:8]) # stepを省略
 # => ibose
print(S[::-1])
 # => 0202esobigen

これらを組み合わせればOKかと思いきや、制約をよく見ると、Nは0以上であることがわかります。
N=0 の時、いつまでたっても、while分から抜けられなくなり、ACすることは出来ません。

入力を受け取ったときに、N=0 だった場合、すぐに’Yes’を出力してプログラムを終わらせるようにしておきましょう。
私はこれに気づかずに1回WA出しました。

あとは、これらを組み合わせて提出すればOKです。

# AtCoder Beginner Contest 198
# B - Palindrome with leading zeros

N=input()

if N=='0':
    print('Yes')
    exit()

while int(N)%10==0:
    N=N[:len(N)-1]

rN=N[::-1]

if N==rN:
    print('Yes')
    exit()

print('No')

C – Compass Walking

小数点の誤差の問題に見せかけた、幾何の問題。

原点と点 (X,Y)を直線で結び、原点から距離Rで区切っていき、点(X,Y)以上の場所に区切り線が入ったら、その区切り線の数が答えになります。

あとは、この数をAと置くと、

A×R>=(X×X + Y×Y)**0.5

となる最小の整数Aを求めればよいことになって、平方根を外す式変形をすると、

A×A × R×R = X×X + Y×Y
A×A = (X×X + Y×Y) / R×R

少し前のABCで出てきた、正の数での小数点切り上げはceilを使えば一発で答えが出るな。と思って出したコードがこちらです。(ちなみにWAです。)

import math

R,X,Y=map(int,input().split())

xx_yy=X*X+Y*Y
rr=R*R
aa=xx_yy/rr

ans=math.ceil(aa**0.5)

print(ans)

すごいきれいに書けた！と思って提出しましたが、WAが3つのケースで出ています。
ABCのC問題では少数の誤差の問題が出ることがあるため、このWA3つは少数の誤差だと思い、いろいろ試してみましたがうまくいきません。

整数しか扱わないような状態を考えて、forループで書いてみます。
ループの回数は、制約のX,Y=10⁵ ,R=1 の時が最大になるので、A<=100,000 の範囲にあることがわかります。
途中で答えがわかり、処理を抜けるようにすれば、forループの処理回数はrange(10**6)にしておけば十分ですね。提出したコードはこちら(WAです。)

R,X,Y=map(int,input().split())
X*=X
Y*=Y
R*=R

for A in range (10**6):
    A*=A
    if R*A>=X+Y:
        A**=0.5
        print(int(A))
        exit()

少数の誤差がない状態にしているのに、先ほど提出したコードと同じケースでWAになっています。

どうやら少数誤差が問題ではなさそうです。

もう一度問題をよく見て、点(X,Y)とRの関係を見てみると、点(X,Y)が半径Rの内側にあると、提出したコードだと1と出てきますが、実際には2が答えになることがわかります。

ここの部分を追加するとACします。

# AtCoder Beginner Contest 198
# C - Compass Walking

R,X,Y=map(int,input().split())
X*=X
Y*=Y
R*=R

if R>X+Y:
    print(2)
    exit()

for A in range (10**6):
    A*=A
    if R*A>=X+Y:
        A**=0.5
        print(int(A))
        exit()