#1174869 (PyPy3) No.2718 Best Consonance

• 問題: No.2718 Best Consonance
• ユーザー: LyricalMaestro
• 提出日時: 2026-08-03 01:00:17
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,608 ms / 4,000 ms
• コード長: 3,392 bytes
• コンパイル時間: 220 ms
• コンパイル使用メモリ: 96,496 KB
• 実行使用メモリ: 358,720 KB
• 最終ジャッジ日時: 2026-08-03 01:00:50
• 合計ジャッジ時間: 31,052 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	AC * 4
other	AC * 36

ソースコード

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

from collections import deque

def main():
    N = int(input())
    ab = []
    for _ in range(N):
        a, b = map(int ,input().split())
        ab.append((a, b))

    # aの取りうる値でチェック
    a_map = {}
    for a, b in ab:
        if a not in a_map:
            a_map[a] = []
        a_map[a].append(b)

    answer = 0

    # 同じ値を取る項が2つ以上ある場合は答えを計算し、その上でBがでかいやつだけ残す
    a_map2 = {}
    for a, b_array in a_map.items():
        b_array.sort()

        if len(b_array) >= 2:
            answer = max(answer, b_array[-2])

        a_map2[a] = b_array[-1]

    max_a = max(a_map2.keys())
    for p in reversed(range(1, max_a + 1)):

        targets = []
        x = p
        while x <= max_a:
            if x in a_map2:
                y = (x // p) * a_map2[x]
                targets.append((x // p, y))
            x += p

        if len(targets) >= 2:
            y_map = {}
            for a, x in targets:
                if x not in y_map:
                    y_map[x] = []
                y_map[x].append(a)
            y_map2 = {}
            for x, a_array in y_map.items():
                a_array.sort()
                if len(a_array) >= 2:
                    y = x // (a_array[1] * a_array[0])
                    answer = max(answer ,y)
                y_map2[x] = a_array[0]
            targets = [(a, x) for x, a in y_map2.items()]
                

            # bについて座標圧縮
            b_set = set()
            for a, x in targets:
                b_set.add(x)
            b_list = list(b_set)
            b_list.sort()
            b_map = {}
            for i, b in enumerate(b_list):
                b_map[b] = i

            # Xi <= X1の場合
            b_array = [(1, 0) for _ in range(len(b_list))]
            for a, x in targets:
                b_index= b_map[x]
                t0 = b_array[b_index]
                t = (x, a)

                if t0[0] * t[1] < t[0] * t0[1]:
                    b_array[b_index] = t
            b_cum_max_array = []
            b_cum = (1, 0)
            for i in range(len(b_list)):
                t = b_array[i]
                if b_cum[0] * t[1] < t[0] * b_cum[1]:
                    b_cum = t
                b_cum_max_array.append(b_cum)

            # X1 < Xi の場合
            c_array = [float("inf") for _ in range(len(b_list))]
            for a, x in targets:
                b_index = b_map[x]
                t0 = c_array[b_index]
                c_array[b_index] = min(t0, a)
            c_cum_min_array = [-1] * len(c_array)
            c_cum = float("inf")
            for i in reversed(range(len(c_array))):
                c = c_array[i]
                c_cum = min(c_cum, c)
                c_cum_min_array[i] = c_cum

            for a, x in targets:
                b_index = b_map[x]

                if b_index > 0:
                    t0 = b_cum_max_array[b_index - 1]
                    if t0[1] != 0:
                        y = t0[0] // (t0[1] * a)
                        answer = max(answer, y)
                if b_index + 1 < len(b_list):
                    a0 = c_cum_min_array[b_index + 1]
                    y = x // (a * a0)
                    answer = max(answer , y)
    print(answer)





 



if __name__ == "__main__":
    main()