三井住友信託銀行プログラミングコンテスト2019 C - 100 to 105

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# 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
INF = float('inf')


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

    X = ii()
    ret = [0] * 100106
    ret[100], ret[101], ret[102], ret[103], ret[104], ret[105] = 1, 1, 1, 1, 1, 1
    for i in range(100, 100000):
        if ret[i] == 0:
            continue
        for j in range(100, 106):
            ret[i+j] = 1

    print(1 if ret[X] == 1 else 0)


if __name__ == '__main__':
    main()

考え方

動的計画法で、購入可能な合計金額を全て求めます。

• 回答概要
  • 購入可能な金額 + 6種類の品物の値段は買うことが出来る合計金額となる
  • Xの範囲で購入可能な合計金額を動的計画法で探索する

---

まず、必ず買うことができる合計金額は100, 101, 102, 103, 104, 105の6種類です。
これらの金額は6種類の品物を１つ買うことにより、この6種類の金額にすることが出来ます。

次にこの6種類を元に、次に購入可能な合計金額を求めます。
既に購入可能であることが判明している金額から6種類の品物の値段が加算された値は購入することが可能です。
あとは以上の処理をXの範囲全てに対して行うことで、Xが購入可能か否かを判定することが出来ます。