AtCoder ABC174
2020-08-02(日)に行われたAtCoderBeginnerContest174の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF
A問題 Air Conditioner
問題文
あなたは、室温が$30$度以上のとき、またそのときに限り、冷房の電源を入れます。
今の室温は$X$度です。冷房の電源を入れますか？
出力
冷房の電源を入れるならば'Yes'、入れないならば'No'を出力せよ。
x = int(input())
if x >= 30:
print("Yes")
else:
print("No")
B問題 Distance
問題文
$2$次元平面上に$N$個の点があります。$i$個目の点の座標は$(X_i,Y_i)$です。
これらのうち、原点からの距離が$D$以下であるような点は何個ありますか？
なお、座標$(p,q)$にある点と原点の距離は$\sqrt{p^2+q^2}$で表されます。
平方根の計算で誤差が出るのが嫌なので，$\sqrt{p^2+q^2} \leqq D$の両辺を二乗した$p^2+q^2 \leqq D^2$を用いて判定を行った．
n, d = map(int, input().split())
d = d * d
count = 0
for i in range(n):
x, y = map(int, input().split())
if x * x + y * y <= d:
count+= 1
print(count)
C問題 Repsept
問題文
高橋君は$K$の倍数と$7$が好きです。
$7,77,777,…$という数列の中に初めて$K$の倍数が登場するのは何項目ですか？
存在しない場合は代わりに'-1'を出力してください。
苦戦しました．
すぐに，$5$の倍数と$2$の倍数は存在しないことはわかったのですが，そこからが個人的には難しく感じました．
かなりの時間をレピュニットの性質を調べるのに使ってしまいました．
個人的な解釈としては，$7,77,777,…$という数列は初項を$a_1=7$とすると，
$a_{n+1}=10a_n+7$
と表すことができる．
これを$mod K$における数列を考えることで解くことができます．
例えば，$K=9$のとき，
$7,77,777,…$の数列を$9$で割った余りの数列は，$7,5,3,1,8,6,4,2,0,7,…$となり$9$項目が$9$の倍数であることがわかる．この数列を$b_n$とする．
例えば$3$項目に着目すると$777$を$9$で割った余りは，$b_3 \equiv 10b_2+7 (mod 9)$で計算することができるため，もし$K$の倍数が存在するならば初項から$K$項目までに少なくとも一回は出現するため($K$で割った余りは，$0 \leqq x \leqq K-1$となるため)，その範囲で余りが$0$のものが出現すれば出力し，出現しなければ'-1'を出力する．
実装では，$b_{n+1} \equiv 10b_n+7 (mod K)$から，$K$が$5$の倍数または$2$の倍数の場合，$b_n \equiv 7 (mod K)$となるためそこで場合分けを行い，それ以外の場合は必ず存在するため答えが出るまでループを繰り返すように実装した．
k = int(input())
if k % 2 == 0 or k % 5 == 0:
print(-1)
else:
c = 7
count = 1
while True:
if c % k == 0:
print(count)
break
else:
c = (10 * c + 7) % k
count += 1
前半はここまでとなります．
最近は公式の解説がとても丁寧に記述してあったので，詳しい解法はそちらを参考にしてもらえたらと思います．
前半の最後まで読んでいただきありがとうございました．
後半はDEF問題の解説となります．
後半に続く．