ARC110 B - Many 110
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 # MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() T = iss() if T == '1': print(2 * 10 ** 10) elif T == '11' or T == '110': print(10 ** 10) else: T = T.split('0') # 予め文字列Tの先頭と末尾が文字列Sに在りうるか確認 if len(T[0]) > 2 and len(T[-1]) > 2: # 文字列Tの先頭または末尾に3文字以上の文字の場合 # '11101', '10111'などのケース print(0) exit() # '101101', '10110' などのケースがあるため先頭と末尾は除外して # 間の文字列が文字列Sに在りうるか確認 for t in T[1:-1]: if len(t) != 2: # 先頭と末尾以外に2文字以外の文字が存在しているケース # 1. '101'のような文字 # 2. 文字列Tに'00'が存在している # これらは文字列Sに存在し得ないので回答はゼロ print(0) exit() if T[-1] == '': print(10 ** 10 - len(T[:-1]) + 1) else: print(10 ** 10 - len(T) + 1) if __name__ == '__main__': main()
考え方
基本的には公式の解説PDF通りにケース分けを行う
T = 1
またはT = 11
の場合には回答が明らか。
それ以外についてはあり得ないケースを除外する必要がある。
基本的にはコメントの通り。
公式の解説PDFだけでは理解できなかったので、
他の方の回答を参考に手元で動かしながら確認した。
参考にした回答: Submission #19116004 - AtCoder Regular Contest 110(Sponsored by KAJIMA CORPORATION)