【ABC174 A~D問題】等比数列の和を有効に使う【Python】

AtCoder
この記事は約4分で読めます。
スポンサーリンク

本記事について

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という並びにならないように「入れ替え」もしくは「色の変更」を行うという問題.

つまり,目標状態は以下の通り

  1. 全てが赤石 ( RR…R )
  2. 全てが白石 ( WW…W )
  3. “ある地点”から左側が全て赤石,右側が白石 ( R…RW…W )

1と2に関しては操作を行う必要がないので,操作回数が0.
そのため,3のみを考える.

ここで重要なのは,3での”ある地点“と言う部分.
以下の図で説明する

【初期状態】WRWWR| RRR
【目標状態】RRRRR | WWW

この”ある地点( | )”から左側を全て赤石(R),右側を白石(W)とすれば目標状態になる.この”ある地点( | )”は初期状態に存在する赤石の総数を数えれば良い.
そのため,手順としては以下の通り.

  1. ある地点“の位置を決める( = 赤石の総数を数える)
  2. ある地点“から左側に存在する赤石の数(cnt)を数える
  3. 初期状態の赤石の総数から,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問題が鬼門だった...

おーよしの紹介
院卒Webエンジニアマン

「プログラミング」や「開発技術」,「大学院の苦労話」について情報発信してます.これからのIT時代を生き抜くため,自分のスキルを磨き続けます.将来は起業できたらいいなという思いがあります.

oyoshiをフォローする
スポンサーリンク
AtCoder python アルゴリズム プログラミング
スポンサーリンク
にほんブログ村に参加中(^~^)
PVアクセスランキング にほんブログ村
おーよしぶろぐ

コメント

タイトルとURLをコピーしました