結果

問題 No.5003 物理好きクリッカー
ユーザー matsu7874matsu7874
提出日時 2018-12-01 04:35:52
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 5,484 ms / 10,000 ms
コード長 6,985 bytes
コンパイル時間 79 ms
実行使用メモリ 33,308 KB
スコア 50,239,564,959
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 07:33:09
合計ジャッジ時間 182,398 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5,436 ms
33,184 KB
testcase_01 AC 5,405 ms
33,196 KB
testcase_02 AC 5,430 ms
32,984 KB
testcase_03 AC 5,425 ms
33,068 KB
testcase_04 AC 5,434 ms
32,992 KB
testcase_05 AC 5,427 ms
32,940 KB
testcase_06 AC 5,474 ms
33,024 KB
testcase_07 AC 5,434 ms
32,904 KB
testcase_08 AC 5,447 ms
33,144 KB
testcase_09 AC 5,417 ms
33,212 KB
testcase_10 AC 5,423 ms
32,724 KB
testcase_11 AC 5,456 ms
32,964 KB
testcase_12 AC 5,484 ms
33,188 KB
testcase_13 AC 5,437 ms
32,908 KB
testcase_14 AC 5,447 ms
33,080 KB
testcase_15 AC 5,448 ms
32,964 KB
testcase_16 AC 5,416 ms
33,240 KB
testcase_17 AC 5,431 ms
33,188 KB
testcase_18 AC 5,436 ms
32,932 KB
testcase_19 AC 5,444 ms
32,932 KB
testcase_20 AC 5,457 ms
33,192 KB
testcase_21 AC 5,458 ms
32,900 KB
testcase_22 AC 5,430 ms
33,220 KB
testcase_23 AC 5,426 ms
33,004 KB
testcase_24 AC 5,432 ms
32,848 KB
testcase_25 AC 5,458 ms
33,264 KB
testcase_26 AC 5,474 ms
32,828 KB
testcase_27 AC 5,444 ms
33,224 KB
testcase_28 AC 5,437 ms
32,880 KB
testcase_29 AC 5,418 ms
33,172 KB
testcase_30 AC 5,435 ms
32,904 KB
testcase_31 AC 5,451 ms
32,876 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, special, right_b, right_f, right_s, action, facilities, reinforces, click_enhance, cookie, effect):
    total_cookies = cookie
    if special == 'S' and action[0] in ['buy', 'reinforce', 'enhclick']:
        return -1
    for name in FACILITY_NAMES:
        productivity = get_productivity(
            name, facilities[name], reinforces[name])
        # TODO: Bも考慮に入れる
        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, s[i], RIGHT_B, RIGHT_F, RIGHT_S, a,
                              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