AtCoder Beginner Contest (ABC) 182 PythonでC問題解いてみた
前回解いたやつ
本日2回目の問題解説です。
書いてるうちに日付変わっちゃった・・・。
たまにはこういうのもいいよね・・・。
というわけで、元気にAtCoder Beginner Contest (abc) 182 C問題やっていきます。
今回は自力で解けたので成長を実感！！！
言語はPython、提出はPyPyです。
目次
poblem C "To 3"
To 3
問題文
整数Nが与えられます。
この整数の各桁のうち、k個の数字を消して残った数字をそのまま連結させます。
この時の数字が3の倍数になるとき、最小のkを求めてください。
という問題です。
さて、3の倍数になる数とはどのような数なのでしょうか？
学校の数学でやりましたよね。
そうです、各桁の数を全て足して、その数が3の倍数なのであれば、3の倍数なのです。
というわけで3の倍数かどうか、全探索することを考えましょう。
桁数が最大でも18桁なので、どんな全探索でも行けそうですね。
この問題を全探索するにあたって、どういう風にコードを組もうかなと考えた時、
各桁の数字に関して、その数字を「消す」、「消さない」の2択を繰り返すことで、全パターンを調べることができそうです。
そうです。bit全探索が使えそうですね。
というわけで方針をまとめます。
1. bit全探索で全探索する。
2. 各ループで、3の倍数か否か判別する。
3. 3の倍数であれば、最小になるように答えを更新する。
4. 答えを出力する。
というわけで書いたコードがこちら。
n = input()
ans = float('inf')
for i in range(2 ** len(n)):
num = []
pop = 0
num1 = 0
for j in range(len(n)):
if (i >> j) & 1:
num.append(n[j])
else:
pop += 1
for l in range(len(num)):
num1 += int(num[l])
if num1 % 3 == 0:
ans = min(ans,pop)
else:
if ans == len(n):
print(-1)
else:
print(ans)
解説していきます。
ans = float('inf')はansを更新していく関係上、ansの初期値はできるだけ大きい数字の方が望ましいのです。
少なくとも、nの桁数よりは大きくしないと、更新ができない場合があるので。
なので、無限大で定義しました。
float('inf')で無限大を生成できます。
for i in range(2 ** len(n)):
num = []
pop = 0
num1 = 0
for j in range(len(n)):
if (i >> j) & 1:
num.append(n[j])
else:
pop += 1
for l in range(len(num)):
num1 += int(num[l])
if num1 % 3 == 0:
ans = min(ans,pop)
この問題の根幹です。
bit全探索の部分ですね。
普通のbit全探索です。
最初に初期化しているのは、
num → 整数Nからk桁削除した後に残った整数。 pop → 削除した桁数。k。 num1 → 整数Nからk桁削除した後に残った整数の各桁を足したもの。
です。
その後のfor jのループでは、
その桁を削除した場合にはpopの数字を1増やし、削除しなかった場合は、numにその数字を格納します。
その後のfor lのループでは、
削除しなかった各桁を足しています。この足したものが3の倍数であれば条件クリアです。
その後のif文で条件チェックしてます。
3の倍数である = 3で割ったときの余りが0である
なので、その場合、ansとpopを比較して、小さい方をansとして更新していきます。
この時に、もともとのansの初期値が小さすぎると、その値が答えになっちゃうことがあるので注意。
という感じでACできました！！
過去問結構bit全探索出ますね。
それでは！！
