CODE FESTIVAL 2017 qual B B - Problem Set

備忘録

問題

atcoder.jp

回答

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 numpy import linalg as LA

# 時々使う
# 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()
    D = collections.Counter(il())
    M = ii()
    T = collections.Counter(il())

    for k, v in T.items():
        if D[k] < v:
            print('NO')
            break
    else:
        print('YES')


if __name__ == '__main__':
    main()

考え方

問題セットを作成することが出来るのは、ある得点Tiの問題の必要な個数が
用意した問題案Dに存在しているときです。
つまり、Tに出現する値の数よりも多く、Dに存在している必要があります。

配列に出現する値の個数をカウントする必要がありますが、
Pythonにおいてはcollections.Counterで何も考えずに配列の値の数をカウントすることが出来ます。
あとは、各値が必要な数以上存在しているか否かを確かめます。