Python3で解く AtCoder Regular Contest 110 B - Many 110

きれいに条件分岐ができればいい。

最初'0'にアサインできたら、最後、左から数えて何番目の'0'にアサインできるかを考える問題

概要
解くときに考えた内容
コード
- 全部場合分け
- 最低限
参考になる書籍

概要

問題

文字列 $s$ は'110'が $10^10$ 個連結したものである。
$n$ 文字の文字列 $t$ が与えられる。
$s$ に $t$ が連続する部分文字列としていくつ含まれる？

解くときに考えた内容

$t$ の長さ別に考える。
が1文字の場合
- = '1'の場合
  - $2 \times 10^{10}$ ('110'に2つ'1'があるから)
- = '0'の場合
  - $10^{10}$ ('110'に1つ'1'があるから)
が2文字の場合
- = '11'と'10'の場合
  - $10^{10}$ ('110'に1つ'11'または'11'があるから)
- = '01'の場合
  - $10^{10}-1$ (最後の1つは取れないので-1)
- = '00'の場合
  - $0$ （このパターンはないので）
が3文字以上の場合は0ががあるので、の0のどこまでアサインできるかということになる。
- $t$ の長さを3で割って切り上げる。
- この値は $t$ に含まれる0の個数であり、cntとする。
- ここで、'110'をcnt分連結した文字列に含まれるかどうかで、カウント対象であるかと、その文字列が0で終わっているのか1で終わっているのかを同時に判定する（結構キモ）
- '110'をcnt分連結した文字列にtが含まれるなら、tが0終わりでsに存在ということ。
  - 例えば、
    - 0110とすると、cnt = 2であり、 $s$ の0の最後……11'0110'、 $10^{10} - 1$ 個目まで取れる。
    - 0110110とすると、cnt = 3であり、 $s$ の0の最後……11'0110110'、 $10^{10} - 2$ 個目まで取れる。
  - 一般に、 $10^{10} - (cnt - 1)$ となる。
- '110'をcnt分連結した文字列にtが含まれず、'110'をcnt分+1連結した文字列にtが含まれるなら、tが1終わりでsに存在ということ。
  - 例えば、
    - 011とすると、cnt = 1であり、 $s$ の0の最後……11'011'0、 $10^{10} - 1$ 個目まで取れる。
    - 011011とすると、cnt = 2であり、 $s$ の0の最後……11'011011'0、 $10^{10} - 2$ 個目まで取れる。
  - 一般に、 $10^{10} - cnt$ となる。
  - これらに当てはまらないものは $s$ に $t$ が含まれないので $0$

f:id:black_tank_top:20201206095202j:plain — 部分文字列のカウントイメージ

上図のように、 $t$ が3文字以上で $s$ に含まれるその他のパターンも同じ様に書いてみると、最初'0'にアサインできたあと、最後の左から数えて何番目の'0'にアサインできるかを考える問題であると言うことがわかる。

コードは全場合分けベースで書いたものと、 $t$ が2文字のものも3文字のものと同様に考えて問題ないので、２種類にかき分けた。

コード

全部場合分け

n = int(input())
t = input()
m = 10**10
# 切り上げ
if len(t) % 3 == 0:
    cnt = len(t) // 3
else:
    cnt = len(t) // 3 + 1
# sにｔが存在する出力パターン
# tのサイズが1のとき
if t == '1':
    print(2*m)
elif t == '0':
    print(m)
# tのサイズが2のとき
elif t == '11' or t == '10':
    print(m)
elif t == '01':
    print(m-1)
elif t == '00':
    print(0)       
# tのサイズが3以上のとき
elif len(t) >= 3:
    # この書き方ならt = 0, 11などもここに含めても可能
    # 個数倍復元して含まれているなら、tが0終わりでsに存在
    if t in '110' * cnt:
        print(m-cnt+1)
        exit()
    # 上記でなくて個数倍+1で復元して含まれているなら、tが1終わりでsに存在
    elif t in '110' * (cnt+1):
        print(m-cnt)
        exit()
    # 上記以外はsにｔが存在しない出力パターン  
    else:
        print(0)

最低限

n = int(input())
t = input()
m = 10**10
if len(t) % 3 == 0:
    cnt = len(t) // 3
else:
    cnt = len(t) // 3 + 1
# tが1のとき
if t == '1':
    print(2*m)
    exit()
# それ以外の時（tが0や、2文字以上のときはこの記述で集約できる）
if t in '110' * cnt:
    print(m-cnt+1)
    # 上記でなくて個数倍+1で復元して含まれているなら、tが1終わりでsに存在
elif t in '110' * (cnt+1):
    print(m-cnt)
# 上記以外はsにｔが存在しない出力パターン  
else:
    print(0)

参考になる書籍

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

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

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