なんどABC(ABC級の企業コンテスト)でC問題を解く！と意気込んで臨んだことでしょう。
今回もAB2完の灰色コーダーがABC174のABC問題を解くために考えたことを、自分の理解を深めるため、また、もしかすると、誰かの役に立つかもしれないと思い書き残します。
Python3のACコード付きです。
A – Air Conditioner
標準入出力と簡単な条件分岐の問題。
標準入力を受け取って、if文で条件分岐させればOKです。
気を付ける部分としては、30度以上の時、ということで
X>=30
と、 = を入れ忘れないようにすることでしょうか。
あと、問題によって、’YES’&’NO’の場合と’Yes’&’No’の場合があるので、毎回良く確認するのは重要だと思います。
統一してもらえるとユーザとして助かるのですが、そこの注意力もプログラミングコンテストの範疇だとも思えるので、毎回良く確認しています。
# AtCoder Beginner Contest 174
# A - Air Conditioner
X=int(input())
if X>=30:
print('Yes')
else:
print('No')B – Distance
座標の2点間の距離を求める問題。
また、その距離と与えられた距離の大小を比較して、条件に合う件数を繰り返し処理を利用して求める問題。
問題文中にある通り原点からの距離をX**2, Y**2の合計したもののルートをとると、計算量や小数点の誤差でTLEやWAになる可能性があるようです。
今回はB問題ということもあり、大丈夫なようでしたが、スマートな解法としては、
X**2 + Y**2 と、 D**2 を比較すれば良いようです。
両辺を二乗しても不等号は同じままというのが重要ということですね。
# AtCoder Beginner Contest 174
# B - Distance
N,D=map(int,input().split())
ans=0
for i in range (N):
X,Y=map(int,input().split())
if X**2+Y**2 <= D**2 :
ans+=1
else:
pass
print(ans)コンテスト中に私が提出したのは、自作した座標関連のクラスを使用しました。
距離を求めるmethodを用意していたのですが、ルートをとっていたので、WAやTLEの可能性があったことは全く意識していなかったので危なかったです。
自作のクラス付きの提出コードは下のおまけに載せておきます。
C – Repsept
倍数判定とmodの性質を問われる問題。
また、規則性のある配列を適切に準備できるかについても問われる問題。
今回もAC出来ませんでした。
解説pdfを見てもよくわからず、Youtubeの解説放送を見て少し理解でき、自分でいろいろ考えて似たような問題を自作してようやく理解できました。
この問題について、まず、
[7, 77, 777, 7777, 77777, ……….]
この配列を準備するのに手間取りました。
コンテスト中に私が考えたのは、こんなのとか、
sevens=[]
for i in range (1,10**1):
sevens.append(int('7'*i))
print(sevens)
# >> [7, 77, 777, 7777, 77777, 777777, 7777777, 77777777, 777777777]こんなのでした。
sevens=[7]
for i in range (1,10**1):
sevens.append(sevens[-1]+7*10**i)
print(sevens)
# >> [7, 77, 777, 7777, 77777, 777777, 7777777, 77777777, 777777777, 7777777777]回答を見た後で見返すとあまりにセンスがないように見えますね。
1つ目のプログラムなんて、入力例3の答えになるような数字を1つ作るだけでTLEになってしまいます。
7恐怖症だよ・・・
解説を見た後で、こうやって作れば良いのか！となったのはこちら。
sevens=[7]
for i in range (10**1):
a=sevens[-1]*10+7
sevens.append(a)
print (sevens)
# >> [7, 77, 777, 7777, 77777, 777777, 7777777, 77777777, 777777777, 7777777777, 77777777777]なんてすっきりしているのでしょう。
こういうのがすぐに作れるように数学的センスも上げていきたいですね。
そして、ここからが倍数判定とmodに関する知見が問われる部分です。
まずは、倍数判定ですが、
任意の数 a が、0以外の数 b で割り切れるかを判定する場合にmodを使用するのに気づく必要があります。
偶奇判定でいつも使っていますよね。
def isEven(num):
if num%2==0:
return True
else :
return False
print(isEven(1)) # >> False
print(isEven(2)) # >> True
print(isEven(3)) # >> False
print(isEven(4)) # >> Trueあとは、modの性質として、厳密性に欠けるとは思いますが、計算途中でmodをとっても、modを使い続ける世界では足し引き掛け算が可能。割り算はちょっと注意が必要。という性質を持っています。(※1)
今回の入力例1で実際に見てみましょう。
sevens=[7]
K=101
for i in range (10**1):
a=sevens[-1]*10+7
sevens.append(a)
mods=[]
for i in range (10**1+1):
mods.append(sevens[i]%K)
print(mods)
# >> [7, 77, 70, 0, 7, 77, 70, 0, 7, 77, 70]これは、7のみから出来ている配列を使用して毎回Kで割り切れるかの判定を行っています。
次に、modを使用したものを利用しつつ、Kで割り切れるかを確認します。
上のプログラムからの変更点は、倍数判定するのに使用する配列を、7のみで作られている配列から作るのではなく、
modをとった配列から新しい判定する数字を作成しています。
modsevens=[7]
K=101
for i in range (1,10**1+1):
a=(modsevens[-1] *10+7)%K # ここが主な変更点
modsevens.append(a)
print(modsevens)
# >> [7, 77, 70, 0, 7, 77, 70, 0, 7, 77, 70]1つ上の出力結果と全く同じになっていることがわかります。
これで、初めにmodKが0になるのを出力すればOKです。
ただし、Kが7の約数の場合は7自身が答えになるので、注意が必要です。
あとは、forのrangeをいくらにするか。ですが、Kで割った余りは必ずK未満のため、最大でK回試せばよいこともわかります。
これらを書けばACできました。
# AtCoder Beginner Contest 174
# C - Repsept
K=int(input())
modsevens=[7]
if K==7 or K==1:
print(1)
exit()
else:
pass
for i in range (1,K):
a=(modsevens[-1] *10+7)%K
if a==0:
print(i+1)
exit()
else:
modsevens.append(a)
print(-1)※1：こちらを主に参考にさせていただきました。
合同式の意味とよく使う６つの性質
今回のこの問題を理解するために、自分で作った問題も下のおまけ記事に書いておきます。
Appendix ～おまけ～
B – Distance (自作のクラスで提出)
OCWで受講しているMITのプログラミングの講義で、クラスの設計が出てきて、そのお題が座標関連でした。
そのお題を自分なりに改良して、2点間の距離、中点、マンハッタン距離を出せるように作っていたので、それを使っています。
上にも書いた通り、距離の大小比較に関しては気を付けるようにしないとダメなことがわかったので、次回以降は気を付けて使用します。
# AtCoder Beginner Contest 174
# B - Distance
class Coodinate (object):
"""Coodinate object
This class contains infomation about the coodinates.
Each instance can have up to 3-dimensional(x,y,z) space coodinates.
params
------------------------------
x : int or floot ,default 0
y : int or floot ,default 0
z : int or floot ,default 0
This class have following methods.
------------------------------
distance : Calculate the straight-line distance between 2 points in Euclidean space.
midpoint : Calculate the midpoint(halfway) between 2 points.
manhattan_distance : Calculate the distance between 2 points that is sum of the absolute values their Cartesian coordinates.
"""
def __init__(self,x=0,y=0,z=0):
self.x=x
self.y=y
self.z=z
def __str__(self):
if self.z==0:
if self.y==0:
return "( {} )".format(self.x)
else :
return "( {} , {} )".format(self.x,self.y)
else:
return "( {} , {} , {} )".format(self.x,self.y,self.z)
def distance(self,other):
"""Calculate the straight-line distance between 2 points in Euclidean space.
params
----------
self : Coodinate object
other : Coodinate object
return
----------
distance : floot
"""
x_diff_sq=(self.x-other.x)**2
y_diff_sq=(self.y-other.y)**2
z_diff_sq=(self.z-other.z)**2
return (x_diff_sq + y_diff_sq +z_diff_sq)**0.5
def midpoint(self,other):
"""Calculate the midpoint(halfway) between 2 points.
params
----------
self : Coodinate object
other : Coodinate object
return
----------
midpoint : tupul
"""
x_midpoint=(self.x+other.x)/2
y_midpoint=(self.y+other.y)/2
z_midpoint=(self.z+other.z)/2
if self.z == other.z ==0 :
if self.y == other.y==0:
return(x_midpoint)
else:
return(x_midpoint,y_midpoint)
return(x_midpoint,y_midpoint,z_midpoint)
def manhattan_distance(self,other):
"""Calculate the distance between 2 points that is sum of the absolute values their Cartesian coordinates.
params
----------
self : Coodinate object
other : Coodinate object
return
----------
manhattan_distance : floot
"""
x_diff_abs=abs(self.x - other.x)
y_diff_abs=abs(self.y - other.y)
z_diff_abs=abs(self.z - other.z)
return(x_diff_abs + y_diff_abs + z_diff_abs)
N,D=map(int,input().split())
O=Coodinate()
ans=0
for i in range (N):
x,y=map(int,input().split())
p=Coodinate(x,y)
if Coodinate.distance(O,p)<=D:
ans+=1
else:
pass
print(ans)
C – Repsept (問題を自作したら理解できた)
youtubeの解説放送を見て、modの性質の話をしてもらっている時に抱いた感想がこの問題を理解するきっかけになりました。
これを見て、「時計みたいだなー。」って思ったんですよね。
そして翌日、いろいろ考えてると、シフト制の勤務が、この問題と本質としては一緒だろうな。って思い、自分で問題を作ってみました。
ネギはW時間勤務の畑で働いています。
畑は24時間稼働でR交代制です。
今日、S時から勤務をスタートしました。
ネギが次に0時から働くのは今日以降、何回目の出勤時でしょうか？
0時に出勤することがない場合は、-1を出力してください。
入力例
W, R, S = 8, 4, 8
この入力例を実際に考えてみます。
自分はシフト1として考えます。
今日の出勤は8時で、8時間働いたら16時退社。次のシフト2の従業員が16時-24時で働いて、シフト3の方が0-8時で勤務。シフト4が8時-16時。
よって、シフト1の自分は次回の出勤時間は16時。
その次の出勤は0時のため、答えは、2 になります。
この自作の問題では、出勤時間をstarttime[]として定義して、今日の出勤時間を要素番号0、翌日の出勤時間を前日の出勤時間+R*W時間として配列を作り、各要素を24で割った余りが0の時が答えになります。
starttime1=[8, 40, 72, 104, 136, 168, …]
これらを24で割った余りを求めていくと、
starttime2=[8, 16, 0, 8, 16, 0, …]
となり、実際に上で考えた結果と一致しています。
日常生活では常にmodを取り続けて、Sを更新していると思います。
starttime3=[8, (8+32)%24 =16, (16+32)%24 =0, (0+32)%24 =8, (8+32)%24 =16, (16+32)%24 =0,…]
倍数判定はmodを使う。
これが当たり前のように出てくるようになりたいです。
コメント