パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）

橙 perf 域から外れてしまった．

A - Health M Death

H % M == 0 ? "Yes" : "No"

B - Many Oranges

個数 を決め打って，実現可能かどうかを考える． 個のみかんの重さとしてあり得る最小値 は で，最大値 は である．従って， が実現可能であるための必要条件である．実はこれは十分条件にもなっている．

理由としては，すべてのみかんの重みを にすれば， かつ が成立するためである．

なお，みかんの重みが整数に限られている場合でも，全てのみかんの重みを にしてから， 個のみかんの重みを してあげればよい． の場合は すると より大きくなってしまうが，このとき なので問題ない．

C - Comma

まず， 桁の数に打つコンマの数は である．

の桁数を とすると， 桁の任意の数は 以下であり，各 に対して 個存在する．

また， 桁でかつ 以下の数の個数は である．

以上より，求める答えは以下のように表せる．

D - Shipping Center

まず，クエリ毎に解法を考えてみる．

使える箱の個数を とする．価値の高い順に，箱のサイズが出来るだけ小さいものを選択して荷物を入れていくという貪欲法により解くことが出来る．

このような貪欲法を考えるのは，直感的には以下のような理由による．

• 先に価値の低い荷物が箱を使ってしまった場合，後から価値の高い荷物を入れる箱がなくなってしまって損する可能性がある
• 先に大きい箱を使ってしまった場合，後で大きい荷物が来た場合に入れられなくなって損する可能性がある

クエリ毎の計算量は，荷物のソートを事前に済ませておけば入れる箱を毎回線形探索しても である．従って，全体 でこの問題を解くことが出来る．

E - Lucky 7 Battle

次のような DP を考える．

ゲームのルールから， の場合に関して以下が成り立つ．

ゲームを後ろから見る関係上，以降は および を反転しておくことにする．

残り ターンの時点で が加えられた場合， の値は へと変化する．従って，DP の遷移は次のように書くことが出来る．

答えは， が なら高橋君，そうでなければ青木君である．

F - Coprime Present

未証明．追加可能な数の集合を状態としてメモ化再帰をすると間に合って解ける．

from math import gcd

A, B = map(int, input().split())
W = B - A + 1
coprime = [[i < j and gcd(A + i, A + j) == 1 for j in range(W)] for i in range(W)]
memo = {}

def dfs(s):
    if s in memo:
        return memo[s]
    res = 1
    bits = [i for i in range(W) if s >> i & 1]
    for i in bits:
        t = 0
        for j in bits:
            t |= coprime[i][j] << j
        res += dfs(t)
    memo[s] = res
    return res

print(dfs((1 << W) - 1))

functools.lru_cache を使えばメモ用の dict を持たなくてもよい．

from functools import lru_cache
from math import gcd

A, B = map(int, input().split())
W = B - A + 1
coprime = [[i < j and gcd(A + i, A + j) == 1 for j in range(W)] for i in range(W)]

@lru_cache(maxsize=1 << 32)
def dfs(s):
    res = 1
    bits = [i for i in range(W) if s >> i & 1]
    for i in bits:
        t = 0
        for j in bits:
            t |= coprime[i][j] << j
        res += dfs(t)
    return res

print(dfs((1 << W) - 1))