AtCoder Beginner Contest 182 A〜C問題
前書き
AtCoder Beginner Contest 182 A〜C問題を解いていきます。
B問題
難易度：灰
時間；10分
もっと早く解かないとなと反省。
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
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)
