ABC216参戦記

ABC216の参加記録です。
結果はABCの3完で終了しました。この記事では、AからC問題までを私が理解した内容で記載していきます。
私は茶色レートです。使用言語はPython3です。

A – Signed Difficulty

標準入出力と条件分岐とデータの型に関する問題。

A問題にしては、ものすごく難しいように思いました。

1行に2変数入っている入力受け取りは難しいとずっと言ってきましたが、今回の入力は特別難しいように思います。

Python3で1行に複数の変数が含まれている場合は、map を利用すると良いですね。
今回は、区切り文字が ' . ' として、変数二つを受け取ればOKです。型は int にしておきます。

あとは、if とelif , else で条件分岐を書いて、それぞれ指定されたフォーマットで出力すればOKですね。
出力に関しても、int型とstr型はそのまま組み合わせることは出来ないので、str 型にして結合するのが良いと思います。

# AtCoder Beginner Contest 216
# A - Signed Difficulty

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

if 0<=Y<=2:
    print(str(X)+'-')
elif 3<=Y<=6:
    print(X)
else:
    print(str(X)+'+')

B – Same Name

繰り返し処理と、重複したデータの効率的な取り扱いが出来るかを問われる問題。

私は、名前(SとT)を空白含めた一つの文字列として受け取り、そのまま set に入れていくようにしました。setに入れる前に、setに既に同じ名前があったらその段階で”Yes”を出力してプログラムを終了させます。最後まで”Yes”が出力されずにfor文がN回実施されたら”No”を出力します。

# AtCoder Beginner Contest 216
# B - Same Name

N=int(input())

s=set()

for i in range (N):
    st=input()
    if st in s:
        print("Yes")
        exit()
    s.add(st)

print("No")

このほかにも、全部 set に入れてしまってから、set に入っているデータの個数をNと比較して、Nより少なければ”Yes”を出力。データの個数がNと一致していれば”No”を出力することでもAC出来ますね。

N=int(input())
s=set()
for i in range (N):
    s.add(input())
print("Yes") if len(s)<N else print("No")

C – Many Balls

二進数の取り扱いに関する問題。
これも難しくないですかね。

Nが2の累乗の場合は、すぐわかりやすいと思います。例えば、Nが2の時は、ボールを1つ追加して2倍すればよいですね。
同様にNが4の時は、ボールを1つ追加して、2倍するのを2回くらい返したらよいですね。
奇数の場合を考えてみます。
２の累乗で作れる数(例えば4)の次の数字である5の場合は、4にしてからボールを1つ追加すればよいですね。

次に、2の累乗で作れる数ではないけれども、偶数はどのように考えればよいでしょうか。
例えば、6は、4+2でも、3×2でも作れますが、Nが大きい数の場合、足し算で調整するのは得策ではなさそうです。
3×2で作る方向を考えますが、3は2+1で作れます。2は作れることがわかっているため、(2+1)×2で6を作れることがわかりました。

7については、6+1で作れるため、6で作ったものに+1すればよいですね。

ここまでの考察により、以下のことが言えそうです。

• 奇数は、一つ前の偶数から+1して作られる。
• 偶数は、ある数からの2倍して作られる。
• これらを0になるまで繰り返す。

例えば、87で考えてみます。

87=86+1　…A
86=43×2　…B
43=42+1　…A
43=21×2　…B
21=20+1　…A
20=10×2　…B
10=5×2 　…B
5=4+1　 …A
4=2×2　 …B
2=1×2　 …B
1=0+1　 …A
0=0×2　　…B

これを下から読むと答えになりそうです。
十進数を二進数にする方法とほぼ同じですね。

あとは、これらの処理をコードにしたらOKです。

# AtCoder Beginner Contest 216
# C - Many Balls

N=int(input())
ans=[]
while N>0:
    if N%2==1:
        ans.append("A")
        N-=1
    ans.append("B")
    N//=2
ans=ans[::-1]
print("".join(ans))

二進法にするのは、Python3では、bin() で出来るため、二進数にして、bitが立っていたらBAを、bitが立っていなかったらBにしてもACしますね。

N=int(input())
ans=str(bin(N))[2:]
print(ans.replace('0','B').replace('1','BA'))