AtCoder Beginner Contest 179 A〜C問題

前書き

AtCoder Beginner Contest 179 A〜C問題を解いていきました。

A問題

• 難易度：灰
• 時間：3分

atcoder.jp

S = input()
SS = S+'es' if S[-1]=='s' else S+'s'
print(SS)

B問題

• 難易度：灰
• 時間：5分

atcoder.jp

3回連続で2つのサイコロの値がゾロ目になるかを検証。

import sys
N = int(input())
D = [list(map(int, input().split())) for n in range(N)]
count_ = 0
for d in D:
  if d[0]==d[1]: count_+=1
  else: count_=0
  if count_>2:
    print('Yes')
    sys.exit()
print('No')

C問題

• 難易度：灰
• 時間：7分

atcoder.jp

与えられた正整数N（2≤N≤10**6）に対して、A×B+C=NとなるABCの組を答えろという問題。
一重ループが限界であるので、頭を柔らかくして考える必要があります。

A×B=N-Cとなる組を探していきます。

例えばN=5の時

• A=1 B=4 C=1
• A=1 B=3 C=2
• A=1 B=2 C=3
• A=1 B=1 C=4
• A=2 B=2 C=1
• A=2 B=1 C=3
• A=3 B=1 C=2

するとある法則が見つかります。
A=kの時のABCの組数は、「A÷Bの切り上げ商-1」であると判明します。
これを下記のコードにて実装します。ACです。

import math
N = int(input())
count_=0
for n in range(1,N):
  count_+= (math.ceil(N/n)-1)
print(count_)

後書き

歴代最速15分3完です！

AtCoder Beginner Contest 193 A〜C問題

前書き

AtCoder Beginner Contest 193 A〜C問題を解きました。

A問題

難易度：灰
時間：2、３分

atcoder.jp

A,B = map(int, input().split())
print((A-B)/A*100)

B問題

難易度：灰
時間：10分

atcoder.jp

1≤N≤10**5なので一重ループである可能性が高いです。
在庫 - 所要時間による減少量 > 0となる店舗から値段が最小となる価格を調べれば良いです。

N = int(input())
APX = [list(map(int, input().split())) for n in range(N)]
_min,clear = 1000000000,0
for apx in APX:
  A,P,X = apx[0],apx[1],apx[2]
  if X-A>0:
    clear += 1
    _min = min(P, _min)
if clear==0: print(-1)
else: print(_min)

C問題

難易度：灰〜茶
時間：50分

atcoder.jp

正直苦戦しました。
1以上N以下の値で、a ** b（2以上N以下のab）で再現できない個数を調べる問題です。
1≤N≤10**10なので１つずつ調査できないです。

数学的な問題かと思いきや、泥臭く調べていく手法でAC。
ただその過程で工夫をしなければいけません。

ただa、bは2以上だと明言されているので、
b = 2だとしたらaは最大でも2**5の値になります。
すると2≤a≤10**5を調べるのは一重ループで可能です。

a**b≤nとなるまでaとbの組み合わせを調べ続けます。
n=10**10としても、b=log(2)10**10になりますので、bはそこまで大きくならず、計算できそうです。
以下のコードでACです。

import math
n = int(input())
c = math.ceil(math.sqrt(n))

i,count = 2,[]
while i<=c:
  j = 2
  while i**j<=n:
    count.append(i**j)
    j+=1
  i += 1
print(n-len(set(count)))

AtCoder Beginner Contest 182 A〜C問題

前書き

AtCoder Beginner Contest 182 A〜C問題を解いていきます。

A問題

難易度：灰
時間：2分

atcoder.jp

A,B = map(int, input().split())
print((2*A+100)-B)

B問題

難易度：灰
時間；10分

atcoder.jp

もっと早く解かないとなと反省。
GCD度を求める問題で、二重ループを駆使すれば解けます。

import sys
N = int(input())
A = list(map(int, input().split()))
_max = max(A)
_maxCount, ans = 0, []

for k in range(2,_max+1):
  count = 0
  for j in A:
    if j%k==0: 
      count+=1
  if _maxCount<=count: 
    _maxCount = count
    ans.append(k)
    
print(max(ans))

C問題

難易度：灰
時間：WA

atcoder.jp

WAに囚われてタイムオーバー(ABC含めて45分想定）。
アルゴリズム・考え方自体は良い線ついていましたが、数個のWAが解決できませんでした。

各桁に0を含まないL桁の数字から最小k桁の数字を消して3の倍数にしてくださいという問題です。
3の倍数ということは各桁の合計値を3の倍数となることが求められます。
消す桁数は0以上L未満であり、消せない場合は-1を出力します。

ここで最初に気づくべきなのは答えが「0」「1」「2」「-1」のいずれかになります。
ではどのような場合にこの回答になるのでしょう。

• 「0」→3の倍数時
• 「-1」→3の倍数でない&各桁の剰余の合計値が3未満&各桁の剰余値に「0」を含まない
• 「1」→ 値Nの剰余値が1&各桁に1が存在 もしくは 値Nの剰余値が2&各桁に2が存在
• 「2」→ 値Nの剰余値が1&各桁に1が存在しない もしくは 値Nの剰余値が2&各桁に2が存在しない

特に-1になる時の条件について
「-1」→3の倍数でない（反証：12(→0),21(→0)など）
「-1」→各桁の剰余の合計値が3未満（反証：112(→1),221(→2)など）
「-1」→各桁の剰余値に「0」を含まない（反証：31(→1),122(→2)など）

最初の段階で「-1」「0」の条件を全て洗い出してやります。

以下のコードは一応自力で解いたコードを載せています。
かなり簡潔な方だと思いますが、いわゆる「抜け」が生じやすく
一発で以下のコードを書けたら結構強いなと思います。

import numpy as np
import sys
input_ = input()
N = np.array(list(map(int, str(input_))))
N = N%3
_sum = np.sum(N)

c_1 = np.count_nonzero(N == 1)
c_2 = np.count_nonzero(N == 2)

if _sum%3!=0 and len(N)<3 and (c_1+c_2)==len(N):
  print(-1)
  sys.exit()
  
if _sum%3==0: 
  print(0)
elif _sum%3==1:
  if c_1>0: print(1)
  else: print(2)
elif _sum%3==2:
  if c_2>0: print(1)
  else: print(2)

参考

このやり方が一番無難そう。

qiita.com

AtCoder Beginner Contest 181 A〜C問題

前書き

D問題よりA~C問題を高速で解くトレーニングを積みたいと思います。

A問題

atcoder.jp

難易度：灰

n = int(input())
if n %2==0: print('White')
else: print('Black')

B問題

atcoder.jp

難易度：灰色
時間：AとBを合わせて8分

N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
sum_ = 0
for ab in AB:
  sum_+=((ab[0]+ab[1])*(ab[1]-ab[0]+1)/2)
print(int(sum_))

C問題

難易度：灰色
時間：37分+(TLEペナル5分)

灰色問題の中では難しい方。
「3つの座標点が一直線上に存在する組み合わせ」が存在するかという問題。

3≤N≤10**2だったので、3つの座標店の組み合わせを知りたければだいたい10**6通りのパターンを全探索すればいけるやんと思いました。そこから傾きと切片の値を取得して、3つの座標を結ぶ数直線の一次関数式が一致しているか確認すればいいと思いました。

数学的なイメージとしてはこちら
examist.jp

check()では2座標点間の傾き・切片を取得しています。

場合分けは以下の通りです。

• x座標と並行
• y座標と並行（傾き∞、切片なしなのでどちらも暫定的に100000とします）
• 他

結果

TLE →(Pypy3)で実行するとAC。
Pythonで実行すべきかPypyで実行すべきかを見極めたいですよね。

import itertools
import sys

N = int(input())
XY = [list(map(int, input().split())) for n in range(N)]

xylis = list(list(itertools.permutations(XY, 3)))

def check(xy1, xy2):
  x1, y1 = xy1[0], xy1[1]
  x2, y2 = xy2[0], xy2[1]
  
  if y1==y2:
    return 0,y1
  elif x1==x2:
    return 100000,100000
    sys.exit()
  else:
    a = (y2-y1)/(x2-x1)
    b = a*(-x1)+y1
    return a,b

for j in range(len(xylis)):
  a1,b1 = check(xylis[j][0],xylis[j][1])
  a2,b2 = check(xylis[j][1],xylis[j][2])
  a3,b3 = check(xylis[j][0],xylis[j][2])
  if (a1==a2==a3)and(b1==b2==b3):
    print('Yes')
    sys.exit()
print('No')

反省

もっと賢い方。
qiita.com