本記事について
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で割り切れる
また，２つの条件をまとめると，
- 7 * (10^i – 1)が9Kで割り切れる
と言うことができる．
また，Kが７の倍数である場合は，(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問題が鬼門だった．．．
コメント