結果

問題 No.5003 物理好きクリッカー
ユーザー matsu7874matsu7874
提出日時 2018-12-01 04:26:24
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 5,094 ms / 10,000 ms
コード長 6,876 bytes
コンパイル時間 63 ms
実行使用メモリ 33,348 KB
スコア 50,169,623,761
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 07:30:29
合計ジャッジ時間 168,344 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5,011 ms
32,864 KB
testcase_01 AC 5,001 ms
33,280 KB
testcase_02 AC 4,967 ms
32,728 KB
testcase_03 AC 4,967 ms
33,208 KB
testcase_04 AC 4,959 ms
33,212 KB
testcase_05 AC 4,982 ms
33,216 KB
testcase_06 AC 5,094 ms
33,236 KB
testcase_07 AC 4,993 ms
33,332 KB
testcase_08 AC 5,021 ms
33,296 KB
testcase_09 AC 5,014 ms
32,916 KB
testcase_10 AC 4,955 ms
32,840 KB
testcase_11 AC 5,001 ms
33,204 KB
testcase_12 AC 4,994 ms
32,936 KB
testcase_13 AC 5,013 ms
32,920 KB
testcase_14 AC 4,979 ms
32,964 KB
testcase_15 AC 4,947 ms
32,936 KB
testcase_16 AC 5,007 ms
33,236 KB
testcase_17 AC 5,006 ms
32,964 KB
testcase_18 AC 4,965 ms
33,236 KB
testcase_19 AC 4,947 ms
33,200 KB
testcase_20 AC 4,946 ms
32,784 KB
testcase_21 AC 4,984 ms
32,948 KB
testcase_22 AC 4,955 ms
33,068 KB
testcase_23 AC 5,009 ms
33,104 KB
testcase_24 AC 5,049 ms
33,048 KB
testcase_25 AC 5,007 ms
32,968 KB
testcase_26 AC 5,034 ms
33,212 KB
testcase_27 AC 4,972 ms
33,048 KB
testcase_28 AC 5,027 ms
32,860 KB
testcase_29 AC 4,979 ms
33,148 KB
testcase_30 AC 4,976 ms
33,212 KB
testcase_31 AC 4,976 ms
32,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import copy
import functools
import math
import sys
FACILITIES = {
    'click': {
        'name': 'click',
        'productivity': 1,
        'price': 1.5,
    },
    'hand': {
        'name': 'hand',
        'productivity': 1,
        'price': 150,
    },
    'lily': {
        'name': 'lily',
        'productivity': 10,
        'price': 2000,
    },
    'factory': {
        'name': 'factory',
        'productivity': 120,
        'price': 30000,
    },
    'casino': {
        'name': 'casino',
        'productivity': 2000,
        'price': 600000,
    },
    'grimoire': {
        'name': 'grimoire',
        'productivity': 25000,
        'price': 10000000,
    },
}

FACILITY_NAMES = [
    'hand',
    'lily',
    'factory',
    'casino',
    'grimoire',
]

ACTIONS = [
    ['click'],
    ['buy', 'hand'],
    ['buy', 'lily'],
    ['buy', 'factory'],
    ['buy', 'casino'],
    ['buy', 'grimoire'],
    ['sell', 'hand'],
    ['sell', 'lily'],
    ['sell', 'factory'],
    ['sell', 'casino'],
    ['sell', 'grimoire'],
    ['reinforce', 'hand'],
    ['reinforce', 'lily'],
    ['reinforce', 'factory'],
    ['reinforce', 'casino'],
    ['reinforce', 'grimoire'],
    ['enhclick'],
]


@functools.lru_cache(maxsize=None)
def get_price(name, num):
    if num == 0:
        return FACILITIES[name]['price']
    return math.ceil(1.2 * get_price(name, num - 1))


@functools.lru_cache(maxsize=None)
def get_reinforce(name, num):
    if num == 0:
        return FACILITIES[name]['price'] * 10
    return get_reinforce(name, num - 1) * 10


@functools.lru_cache(maxsize=None)
def get_productivity(name, num, reinforce):
    return FACILITIES[name]['productivity'] * num * 2**reinforce


def simulate(s, t, actions, specials, facilities=None, reinforces=None, click_enhance=0,  cookie=0, effect=None):
    if facilities is None:
        facilities = {name: 0 for name in FACILITY_NAMES}
    if reinforces is None:
        reinforces = {name: 0 for name in FACILITY_NAMES}
    if effect is None:
        effect = ['', 0]

    for i in range(s, t):
        # 行動フェーズ
        command = actions[i][0]
        if command == 'click':
            if effect[0] == 'F':
                cookie += get_productivity('click', 1, click_enhance) * 7
            else:
                cookie += get_productivity('click', 1, click_enhance)
        elif command == 'buy':
            name = actions[i][1]
            price = get_price(name, facilities[name])
            if effect[0] == 'S':
                price = math.ceil(price * 0.9)
            if cookie >= price:
                cookie -= price
                facilities[name] += 1
            # else:
            #     print(i, actions[i], 'cookie < price', file=sys.stderr)
        elif command == 'sell':
            name = actions[i][1]
            if facilities[name] > 0:
                facilities[name] -= 1
                cookie += math.ceil(get_price(name, facilities[name]) * 0.25)
            # else:
            #     print(i, actions[i], 'cookie < price', file=sys.stderr)
        elif command == 'reinforce':
            name = actions[i][1]
            price = get_reinforce(name, reinforces[name])
            if effect[0] == 'S':
                price = math.ceil(price * 0.9)
            if cookie >= price:
                cookie -= price
                reinforces[name] += 1
            # else:
            #     print(i, actions[i], 'cookie < price', file=sys.stderr)
        elif command == 'enhclick':
            name = 'click'
            price = get_reinforce(name, click_enhance)
            if effect[0] == 'S':
                price = math.ceil(price * 0.9)
            if cookie >= price:
                cookie -= price
                click_enhance += 1
            # else:
            #     print(i, actions[i], 'cookie < price', file=sys.stderr)

        # 施設によるクッキーの生産
        total_productivity = sum(get_productivity(
            name, facilities[name], reinforces[name]) for name in FACILITY_NAMES)
        if effect[0] == 'F':
            cookie += total_productivity * 7
        else:
            cookie += total_productivity

        # 特殊効果のカウントを減少
        special = specials[i]
        if effect[1] <= 1:
            effect = ['', 0]
        else:
            effect[1] -= 1

        # 特殊効果フェーズ
        if special == 'N':
            pass
        elif special == 'B':
            cookie += math.ceil(cookie * 0.1)
        elif special == 'F':
            effect = ['F', 20]
        elif special == 'S':
            effect = ['S', 1]

    return {
        'facilities': facilities,
        'reinforces': reinforces,
        'click_enhance': click_enhance,
        'cookie': cookie,
        'effect': effect,
    }


def get_score(n, now, right_b, right_f, right_s, facilities, reinforces, click_enhance, cookie, effect):
    total_cookies = cookie
    for name in FACILITY_NAMES:
        productivity = get_productivity(
            name, facilities[name], reinforces[name])
        # TODO: B, S, Fも考慮に入れる
        total_cookies += productivity * (n - now + 1 + right_f[now] * 19)
    return total_cookies


def solve(n, s):
    actions = ['click' for i in range(n)]
    best_status = [None for i in range(n + 1)]

    facilities = {name: 0 for name in FACILITY_NAMES}
    reinforces = {name: 0 for name in FACILITY_NAMES}
    effect = ['', 0]

    best_status[0] = {
        'facilities': facilities,
        'reinforces': reinforces,
        'click_enhance': 0,
        'cookie': 0,
        'effect': effect,
    }

    for i in range(0, n):
        max_score = -1
        for a in ACTIONS:
            actions[i] = a
            status = simulate(i, i + 1, actions, s, **
                              copy.deepcopy(best_status[i]))
            score = get_score(n, i, RIGHT_B, RIGHT_F, RIGHT_S,
                              status['facilities'], status['reinforces'], status['click_enhance'], status['cookie'], status['effect'])

            if score > max_score:
                max_score = score
                best_status[i + 1] = copy.deepcopy(status)
                best_action = a
        actions[i] = best_action[:]

    return actions


def main():
    actions = solve(N, S)

    for action in actions:
        print(' '.join(action), flush=True)
        # result = input()


if __name__ == "__main__":
    N = int(input())
    S = [c for c in input()]

    RIGHT_B = [0 for i in range(N + 1)]
    RIGHT_F = [0 for i in range(N + 1)]
    RIGHT_S = [0 for i in range(N + 1)]

    for i in range(N - 1, -1, -1):
        if S[i] == 'B':
            RIGHT_B[i] += 1
        if S[i] == 'F':
            RIGHT_F[i] += 1
        if S[i] == 'S':
            RIGHT_S[i] += 1
        RIGHT_B[i] += RIGHT_B[i + 1]
        RIGHT_F[i] += RIGHT_F[i + 1]
        RIGHT_S[i] += RIGHT_S[i + 1]

    main()
0