本記事について
AtCoder Beginner Contest 第74回のA~D問題を,Python3で解いてみた.
https://atcoder.jp/contests/abc174
特にC問題は「等比数列の和」,D問題は「ひらめき(笑)」を使えば解けるらしいので,それを使って解いてみた.
A問題 「Air Conditioner」
入力値が30以上なら,「Yes」.そうでないなら「No」を返す.
x=int(input())
if x >=30:
print("Yes")
else:
print("No")
B問題 「Distance」
「入力された点(a,b)と原点(0,0)間の直線距離がd以下となる点の数はいくつか」という問題.
import math
#入力:N,M(int:整数)
def input2():
return map(int,input().split())
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
return list(map(int,input().split()))
n,d=input2()
xy=[]
for _ in range(n):
xy.append(input_array())
count=0
for i in xy:
di=math.sqrt(float(i[0]**2 + i[1]**2))
if di <= d:
count+=1
print(count)
C問題 「Repsept」
「7, 77, 777, 7777,…」という数列があり,入力Kの倍数の最小値がこの配列の何項目に出現するかという問題.
出現しなければ-1を返す.
ただし,配列の上限が存在しないため,配列全てに対してKを割っても計算量は0[オーダ](∞)である.
ここで,この数列のi項目に注目する.
数列は以下の通り.
1項目:7 = 7 * 1 2項目:77 = 7*10+7*1 3項目:777 = 7*100 + 7*10 + 7*1 4項目:7777 = 7*1000 + 7*100 + 7*10 + 7*1 ... i項目:7.....7 = 7*(1+10+10^2+...+10^(i-1)) = 7 * (10^i - 1) /9
i項目では,()内が等比数列の和で表現されているため,上記のような一般項で示すことができる.
つまり,以下の条件を満たすKを求めれば良い.
- i項目がKで割り切れる
- 7 * (10^i – 1) が9で割り切れる
また,2つの条件をまとめると,
- 7 * (10^i – 1)が9Kで割り切れる
と言うことができる.
また,Kが7の倍数である場合は,(10^i – 1)が9Kで割り切れるかどうかだけを考えれば良い.
ここまでをまとめると,以下の通り.
【Kが7の倍数】 (10^i - 1)が9K[=L]で割り切れる 【Kが7の倍数以外】(10^i - 1)が9K/7[=L] で割り切れる
つまり,10^i をLで割ると1になるかを逐次判定すれば良い.
ここまでの考え方を踏まえて書いたソースコードが以下の通り.
k=int(input())
num=1
L=0
ans=-1
if k%7==0: #kが7の倍数
L=(9*k)/7
else: #kが7の倍数以外
L=9*k
for i in range(k+1):
if num*10%L==1: #Lで割ると1になる
ans=i+1
break
num=num*10%L
print(ans)
D問題「Alter Altar」
公式の解説(https://img.atcoder.jp/abc174/editorial.pdf)だとよく分からなかったので,私独自の手法で説明していこうと思う.
白石(W)と赤石(R)がN個連続で並んでいて,WRという並びにならないように「入れ替え」もしくは「色の変更」を行うという問題.
つまり,目標状態は以下の通り
- 全てが赤石 ( RR…R )
- 全てが白石 ( WW…W )
- “ある地点”から左側が全て赤石,右側が白石 ( R…RW…W )
1と2に関しては操作を行う必要がないので,操作回数が0.
そのため,3のみを考える.
ここで重要なのは,3での”ある地点“と言う部分.
以下の図で説明する
【初期状態】WRWWR| RRR
【目標状態】RRRRR | WWW
この”ある地点( | )”から左側を全て赤石(R),右側を白石(W)とすれば目標状態になる.この”ある地点( | )”は初期状態に存在する赤石の総数を数えれば良い.
そのため,手順としては以下の通り.
- “ある地点“の位置を決める( = 赤石の総数を数える)
- “ある地点“から左側に存在する赤石の数(cnt)を数える
- 初期状態の赤石の総数から,cntを引く
最終的なソースコードは以下の通り.
n=int(input())
c=str(input())
R=c.count("R")
cnt=0
for i in range(R):
if c[i]=="R":
cnt+=1
print(R-cnt)
さいごに
今回はC問題が鬼門だった...
コメント