結果

問題 No.5003 物理好きクリッカー
ユーザー matsu7874matsu7874
提出日時 2018-12-01 03:59:42
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 5,247 ms / 10,000 ms
コード長 6,392 bytes
コンパイル時間 310 ms
実行使用メモリ 33,372 KB
スコア 49,490,932,037
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 07:29:49
合計ジャッジ時間 179,873 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,995 ms
32,904 KB
testcase_01 AC 5,181 ms
32,800 KB
testcase_02 AC 5,175 ms
32,976 KB
testcase_03 AC 5,220 ms
33,096 KB
testcase_04 AC 5,095 ms
33,124 KB
testcase_05 AC 5,098 ms
33,120 KB
testcase_06 AC 5,050 ms
32,980 KB
testcase_07 AC 5,092 ms
33,196 KB
testcase_08 AC 5,139 ms
33,076 KB
testcase_09 AC 5,085 ms
33,140 KB
testcase_10 AC 5,097 ms
33,192 KB
testcase_11 AC 5,066 ms
33,024 KB
testcase_12 AC 5,098 ms
33,144 KB
testcase_13 AC 5,120 ms
33,208 KB
testcase_14 AC 5,095 ms
33,044 KB
testcase_15 AC 5,150 ms
33,204 KB
testcase_16 AC 5,085 ms
33,092 KB
testcase_17 AC 5,165 ms
33,196 KB
testcase_18 AC 5,103 ms
33,148 KB
testcase_19 AC 5,056 ms
32,868 KB
testcase_20 AC 5,063 ms
33,020 KB
testcase_21 AC 5,034 ms
33,060 KB
testcase_22 AC 5,033 ms
33,256 KB
testcase_23 AC 5,092 ms
32,980 KB
testcase_24 AC 5,130 ms
33,196 KB
testcase_25 AC 5,139 ms
33,164 KB
testcase_26 AC 5,247 ms
33,200 KB
testcase_27 AC 5,134 ms
32,940 KB
testcase_28 AC 5,083 ms
33,188 KB
testcase_29 AC 5,133 ms
33,096 KB
testcase_30 AC 5,159 ms
33,132 KB
testcase_31 AC 5,117 ms
32,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import copy
import functools
import math

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
        elif command == 'sell':
            name = actions[i][1]
            if facilities[name] > 0:
                facilities[name] -= 1
                cookie += math.ceil(get_price(name, facilities[name]) * 0.25)
        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
        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

        # 施設によるクッキーの生産
        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)
    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