結果

問題 No.2553 Holidays
ユーザー LyricalMaestro
提出日時 2025-01-27 00:16:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,410 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 88,064 KB
最終ジャッジ日時 2025-01-27 00:16:23
合計ジャッジ時間 8,406 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2553

from functools import cmp_to_key

# 比較関数
def compare_items(a, b):
    if a[0] * b[1] > a[1] * b[0]:
        return 1
    elif a[0] * b[1] < a[1] * b[0]:
        return -1
    else:
        if a[2] < b[2]:
            return 1
        elif a[2] > b[2]:
            return -1
        else:
            return 0


def main():
    N, M = map(int, input().split())
    S = input()

    s_array = [s for s in S]
    for i in range(1, N - 1):
        if s_array[i - 1] == "o" and s_array[i + 1] == "o" and s_array[i] == "-":
            s_array[i] = "o"
    
    # xで分解
    ss_array = []
    flg = False
    for s in s_array:
        if s != "x":
            if not flg:
                ss_array.append([s])
                flg = True
            else:
                ss_array[-1].append(s)
        else:
            flg = False

    type_array = []
    for ss_array0 in ss_array:
        ss_array00 = "x" + "".join(ss_array0) + "x"
        sss = ss_array00.split("o")
        for s_ in sss:
            if s_.startswith("x") and s_.endswith("x"):
                if len(s_) > 2:
                    type_array.append((2, len(s_) - 2))
            elif s_.startswith("x") or s_.endswith("x"):
                if len(s_) > 1:
                    type_array.append((1, len(s_) - 1))
            else:
                if len(s_) > 0:
                    type_array.append((0, len(s_)))
    new_type_array = []
    for t, length in type_array:
        if t == 0:
            new_type_array.append((length, length // 2, 0))
        elif t == 1:
            new_type_array.append((length, (length + 1) // 2, 1))
        elif t == 2:
            new_type_array.append((length, (length + 2) // 2, 2))
    
    new_type_array = sorted(new_type_array, key=cmp_to_key(compare_items), reverse=True)

    ans = 0
    for i in range(len(new_type_array)):
        l, c, t = new_type_array[i]
        if M >= c:
            ans += l
            M -= c
        else:
            if t == 0:
                ans += 2 * M
                M = 0
            elif t == 1:
                ans += 2 * M
                M = 0
            else:
                ans += 2 * M - 1
                M = 0
        if M == 0:
            break
    
    for i in range(N):
        if s_array[i] == "o":
            ans += 1
    print(ans)



            



if __name__ == "__main__":
    main()
0