ABC011 C - 123引き算

備忘録

問題

atcoder.jp

回答

import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

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)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    NGList = [ii() for _ in range(3)]

    if N in NGList:
        print('NO')
        exit()

    for i in range(100):
        if N - 3 not in NGList:
            N -= 3
        elif N - 2 not in NGList:
            N -= 2
        elif N - 1 not in NGList:
            N -= 1
        else:
            print('NO')
            exit()

    print('YES' if N <= 0 else 'NO')


if __name__ == '__main__':
    main()

考え方

引き算を行うとき、最大値の3を使用してもNG数字に当てはまらない場合、
2や1を使用するよりも3を使用した方が最もNの数値を減らすことが出来る。
2についても同様。

NG数字は３つ程度であり、引き算を行う数値も1 ~ 3なので、
（感覚的に問題なさそうな）常に最大値を取り続ける貪欲法で考えた。

実装は、100回引き算を行い、常に引くことが出来る最大値を取り続ける。
途中で引くことが出来なくなった場合には回答をNOとし、
100回の試行後、NがN <= 0のときにはYES、N > 0のときにはNOと回答した。