dwangoプログラミングコンテスト B - ニコニコ文字列
備忘録
問題
回答
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 # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def it(): return tuple(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") S = iss() I = len(S) i, ret = 0, 0 while i <= I: n = 0 while i + 2 <= I: if S[i:i+2] == "25": n += 1 i += 2 else: break ret += (n * (n + 1)) // 2 i += 1 print(ret) if __name__ == '__main__': main()
考え方
25
が連続して出現するほど、ニコニコ文字列として取り出すことができる文字列が増えることが感覚的に分かります。
この取り出し方の通り数について考えます。
25
が出現した場合、ニコニコ文字列の取り出し方は25
の1通りです。
2525
が出現した場合、ニコニコ文字列の取り出し方は25
が2通り、2525
が1通りで計3通りです。
252525
が出現した場合、ニコニコ文字列の取り出し方は25
が3通り、2525
が2通り、252525
が1通りで計6通りです。
25252525
が出現した場合、ニコニコ文字列の取り出し方は25
が4通り、2525
が3通り、252525
が2通り、25252525
が1通りで計10通りです。
以上のことをまとめると、
25が1つのとき = 1
25が2つのとき = 2 + 1
25が3つのとき = 3 + 2 + 1
25が4つのとき = 4 + 3 + 2 + 1
と増えていることが分かります。
以上のことから、"文字列S
の中で25
がいくつ連続しているか"を数えることによって、ニコニコ文字列の取り出し方の通り数を求めることが出来ます。
また25
が連続した数をn
としたとき、ニコニコ文字列の取り出し方の通り数は等差数列の和となるため、(n * (n + 1)) // 2
で求めることが出来ます。