ABC055 C - Scc Puzzle
備忘録
問題
回答
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque sys.setrecursionlimit(10000000) ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, M = il() ret = 0 if N * 2 <= M: ret += N ret += (M - N * 2) // 4 else: ret += M // 2 print(ret) if __name__ == '__main__': main()
回答
Scc
の文字列を作るためには、
S
が1つとc
が2つ、またはc
が4つ必要となる。
愚直にループ文などで文字列を作るシミュレートを行った場合、
N
、M
ともに最大で10 ** 12
なため、時間が足りない。
そのため、ケースを分けて考える。
N * 2 <= M
のとき、
全てのN
を使用してScc
を作ってもM
が余る。
そのため、最低でも文字列をN
組作ることができる。
さらに、c
が4つで文字列を作ることができるため、
余ったM
を4で割り切ることが出来る回数だけ、文字列を作ることが出来る。
そのため、回答はN + (M - N*2)//4
組となる。
N * 2 > M
のとき、
全てのN
を使用してScc
を作ることができない。
必ず文字S
が余る状況にあるため、
文字c
から文字S
を作る必要性がない。
このことから、M
を2で割り切ることができる回数だけ、文字列を作ることが出来る。
そのため、回答はM // 2
組となる。