【ABC182 C】「To 3」を解く【Python3】

コンテスト一覧へ

 

Nの桁を0個以上k個未満(kはNの桁数)消したとき、残った桁をそのままの順序で結合することで3の倍数を作れるかどうか判定し、消す桁数の最小値を求める問題です。

提出
n = input()
ans = len(n)

if int(n)%3==0:
    print(0)
    exit()

for i in range(2**len(n)):
    num = 0
    cnt = 0
    for j in range(len(n)):
        if (i >> j) & 1:
            num += int(n[j])
            cnt += 1
    if num%3==0:
        ans = min(ans, len(n)-cnt)

if ans == len(n):
    print(-1)
else:
    print(ans)

入力はNのみです。

すべての桁の数を足したものが3の倍数であれば、その数字は3の倍数となります。

複数の方法がありますが、ここでは、bit全探索を使って求めています。

Nの桁の中で、「消す桁」と「消さない桁」の全パターンは、Nの最大値が1018であるため、最大「218 = 262144」通りになります。

このすべてのパターンを調べていき、「3の倍数」かつ「消す桁が最小のもの」を求めます。

具体的には、数字Nが10桁の場合、「0000000000」~「1111111111」までのパターンをすべて調べ、ビットが1である部分の桁を足し、それが「3の倍数」かどうかを判定します。

 

「>>」はビットシフト演算子といい、2進数を指定の数だけ右にシフトします

「<<」は同様に左にシフトします。

x = 13
print(bin(x))                       # > 0b1101
print(x << 1)                       # > 26
print(bin(x << 1))                  # > 0b11010
print(x >> 1)                       # > 6
print(bin(x >> 1))                  # > 0b110

「0b」は2進数の先頭につく文字列です。

 

「&」は論理積といい、2つの数字の両方が1の場合のみ、1を返します。

x = 7
y = 19
print(bin(x),bin(y))                # > 0b111 0b10011
print(x & y)                        # > 8
print(bin(x & y))                   # > 0b1000

 

プログラム内の

if (i >> j) & 1:
    num += int(n[j])
    cnt += 1

の部分で、iをj回シフトさせ、1との論理積が1の場合、桁の数字を「num」に足していきます。

足した桁数を数えるために「cnt」にも1を加えます。

論理積が1だった桁の数字をすべて足し終えた後、numが「3の倍数」だった場合に、「ans」と「len(n)-cnt」を比較し、小さいほうをansに入れます。

最終的に、消す桁数が最小のものが「ans」に入っているので、これを出力します。

【ABC182】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。