前書き
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)