Python3で解く AtCoder Beginner Contest 182 C - To 3

3の倍数になるかどうかなので、mod3で場合分け、そしてさらにその結果で場合分けっていうふうに愚直にやる。

概要

各桁に $0$ を含まない正の整数 $N$ が与えられる。
$N$ の桁数を $k$ として $k$ 未満個ある桁を消すことができる。
その結果左から順に結合した数値が3の倍数であるようにできる最小限の消す数は？

解くときに考えた内容

ポイントは、答えが0, 1, 2, -1しかないということ。なぜなら、
- $N$ が3で割り切れるか(0が答えのパターン)
- わりきれない場合は、のどこかの桁を消す。
  - $N \% 3 = 1$ の時だと、 $N$ のある桁の値（ $n$ とする）が $n \% 3 = 1$ が１つか $n \% 3 = 2$ が２つあれば、結果的に結合した値は3で割り切れる。
  - $N \% 3 = 2$ の時だと、 $N$ のある桁の値（ $n$ とする）が $n \% 3 = 2$ が１つか $n \% 3 = 1$ が２つあれば、結果的に結合した値は3で割り切れる。
- この時点で、1か2が答えのパターン
- ただし、桁がの時は消せる数が自身の桁数未満であることに注意する。
  - 例えば1とか11は-1が答え
- $n \% 3 = 1$ と $n \% 3 = 2$ の数をそれぞれカウントして、1つでいいパターンがあれば1が答え、2つでいいパターンがあれば2が答え。（ここで、なりで数えた順とかでやるとミスる。最後まで数えて、あるなしを判定する。）
- あとは1-2桁対策用の処理

コード

N = list(input())
N = [int(x) for x in N]
k = len(N)
sum_n = sum([int(x) for x in N])
mod = sum_n % 3
# Nが3で割り切れる場合
if mod == 0:
    print(0)
    exit()
# Nが3で割ると1余る場合
elif mod == 1:
    cnt_1 = 0
    cnt_2 = 0
    for n in N:
        # 各桁に3で割って余り1になる桁があるかカウント
        if n % 3 == 1:
            cnt_1 += 1
        # 各桁に3で割って余り2になる桁があるかカウント
        elif n % 3 == 2:
            cnt_2 += 1
    # 一つでもあればいい方を優先
    if cnt_1 >= 1 and 1 < k:
        print(1)
        exit()
    elif cnt_2 >= 2 and 2 < k:
        print(2)
        exit()
    else:
        print(-1)
        exit()
elif mod == 2:
    cnt_1 = 0
    cnt_2 = 0
    for n in N:
        # 各桁に3で割って余り2になる桁があるかカウント
        if n % 3 == 2:
            cnt_1 += 1
        # 各桁に3で割って余り1になる桁があるかカウント
        elif n % 3 == 1:
            cnt_2 += 1
    # 一つでもあればいい方を優先
    if cnt_1 >= 1 and 1 < k:
        print(1)
        exit()
    elif cnt_2 >= 2 and 2 < k:
        print(2)
        exit()
    else:
        print(-1)
        exit()

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。