[BOJ 27231, Python] 2023年が楽しみな理由

問題リンク

BOJ 27231

分類

ブルートフォースアルゴリズム、バックトラッキング

説明

最近、以前解けなかった問題が何とか解けるようになってきたのを見ると、実力が向上したと感じて気分が良い。

この問題の場合も、最後の挑戦は5ヶ月前に大会で出題された時だが、その間にも解決の兆しが見えない解法を試行錯誤したことが何度かあった。

最後の挑戦が何度もあった理由は、たった一つの条件が欠けていたからだが、この条件が抜けているだけでなぜタイムリミットオーバーになってしまうのか、その理由はまだよく分からない。 後で補足できる理由ならいいのだが。 → 下の内容を整理しているうちに思い出した。やはりブログの整理は最高だ！

問題の解法アプローチを紹介すると

• + 記号を入れる座標をビットマスクを活用して全数チェック

• 集合、あるいは重複を許さないリストに入れてソート

• 累乗のサイズを徐々に増やしながら、最終的に最初に与えられた数（どんなに細かく分割してもこの数より大きくなることはないため）まで存在する数字の個数をカウント

そしてここで問題が発生した。

0、1で構成された数の場合、単一の数字に分割すると、いくら累乗しても値が変わらないため、Hello, BOJ 2023!を出力する必要があるが、私は単純に1の場合だけを除外していた。

いくら二乗しても数値が増加しなかったため、whileループに引っかかり、タイムリミットオーバーとなってしまったのだ！その部分を確認するために、単一の数字について2を超えるかどうかをチェックし、2を超える項がない場合は無条件にHello, BOJ 2023!を出力するようにすることで、エッジケースを処理し、正解を得ることができた。

解答コード

# 2023년이 기대되는 이유

import sys

input = sys.stdin.readline

def pow_target(target_num: int, exponent: int) -> int:

    result = 0

    now_number = target_num

    while now_number:
        result += pow((now_number % 10), exponent)
        now_number //= 10

    return result

testcase = int(input())
result_dict = dict()
output = []

for _ in range(testcase):

    target_number = input().rstrip('\n')

    if result_dict.get(target_number) is not None:
        output.append(result_dict[target_number])

    else:

        is_under_limit = True

        for each_element in list(target_number):
            if int(each_element) > 1:
                is_under_limit = False
                break

        if is_under_limit:
            result_dict[target_number] = 'Hello, BOJ 2023!'
            output.append('Hello, BOJ 2023!')
            continue

        length = len(target_number)

        check_list = []
        check_list.append(int(target_number))

        for i in range(1, 1 << length):

            calc_result = 0

            now_start = 0
            now_end = 0

            for j in range(length):

                if i & (1 << j):
                    now_end = j
                    if now_end:
                        calc_result += int(target_number[now_start : now_end])
                    now_start = now_end
                    
            calc_result += int(target_number[now_start : length + 1])

            if calc_result not in check_list:
                check_list.append(calc_result)

        else:
            result = 0

            check_amount = len(check_list)
            check_list.sort()

            max_value = check_list[-1]
            pointer = 0
            counter = 1

            while pointer < check_amount:
                now_result = pow_target(int(target_number), counter)

                # 종료 조건 1
                if now_result > max_value:
                    break

                while pointer < check_amount and now_result > check_list[pointer]:
                    pointer += 1

                # 종료 조건 2
                if pointer >= check_amount:
                    break

                if now_result == check_list[pointer]:
                    result += 1

                counter += 1

            result_dict[target_number] = result
            output.append(result)

for result in output:
    print(result)