[BOJ 2473, Python] 3つの溶液

問題リンク

BOJ 2473

カテゴリ

二分探索、ソート、ツーポインター

説明

典型的なツーポインター問題から少し発展した問題のようだ。

最初にこの問題を解く際、3つの溶液を混ぜ合わせなければならないことから、何か別の解法があるだろうと考えてしまい、意外にも正攻法を使わなかった。その結果、実際の解法が遅れることになってしまった。

この問題で注意すべき点は、溶液の総数が5000以下であるという点だ。この条件がなければ、この問題を絶対に制限時間内に解くことはできない……当初、この条件を注意深く見ていなかったために、他の解法を探し続けてしまった点は、今思っても残念な点だった。

したがって、この問題の解決方法は次のように提示できるだろう。

順序ソート → 溶液1つを固定 → 残りの溶液について、その溶液と合算して0に最も近くなるように2点法アルゴリズムを使用 → すべて巡回したか、0に達した場合は終了

解答コード

# 세 용액

import sys

input = sys.stdin.readline

solution_number = int(input())
solution_list = list(map(int, input().split()))

solution_list.sort()
characteristic_value = 3000000000

for idx in range(solution_number):

    pointer_1 = 0
    pointer_2 = solution_number - 1

    while pointer_1 < pointer_2:

        if pointer_1 == idx:
            pointer_1 += 1
        if pointer_2 == idx:
            pointer_2 -= 1

        if pointer_1 >= pointer_2:
            break

        now_value = sum([solution_list[idx], solution_list[pointer_1], solution_list[pointer_2]])

        if abs(now_value) < characteristic_value:
            characteristic_value = abs(now_value)
            result = [solution_list[idx], solution_list[pointer_1], solution_list[pointer_2]]

            if not characteristic_value:
                break

        if now_value < 0:
            pointer_1 += 1
        elif now_value > 0:
            pointer_2 -= 1

    if not characteristic_value:
        break

result.sort()

print(*result)