#1149088 (Python3) No.2594 Mix shake!!

• 問題: No.2594 Mix shake!!
• ユーザー: hitonanode
• 提出日時: 2026-02-23 01:38:44
• 言語: Python3 (3.14.3 + numpy 2.4.2 + scipy 1.17.0)
• 結果: WA
• 実行時間: -
• コード長: 3,937 bytes
• コンパイル時間: 1,031 ms
• コンパイル使用メモリ: 20,824 KB
• 実行使用メモリ: 15,496 KB
• 最終ジャッジ日時: 2026-02-23 11:38:58
• 合計ジャッジ時間: 22,119 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 70 WA * 15

ソースコード

import sys
import functools

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    A = [int(x) for x in input_data[1:n+1]]
    B = [int(x) for x in input_data[n+1:2*n+1]]
    C = [int(x) for x in input_data[2*n+1:3*n+1]]
    D = [int(x) for x in input_data[3*n+1:4*n+1]]
    
    V = [(A[i], B[i]) for i in range(n)]
    W = [(C[i], D[i]) for i in range(n)]
    
    # 濃度（りんご a / バナナ b）の降順にソートするための比較関数
    # a1/b1 > a2/b2 <=> a1*b2 > a2*b1
    def cmp(v1, v2):
        val = v1[0] * v2[1] - v1[1] * v2[0]
        if val > 0: return -1
        if val < 0: return 1
        return 0

    # 集合 init_V が target_W を「メジャライズ」しているか（包含しているか）を厳密に判定
    def check(init_V, target_W):
        s_V = sorted(init_V, key=functools.cmp_to_key(cmp))
        s_W = sorted(target_W, key=functools.cmp_to_key(cmp))
        
        # V の折れ線の頂点を構築
        pts_V = [(0, 0)]
        cur_a, cur_b = 0, 0
        for a, b in s_V:
            cur_a += a
            cur_b += b
            pts_V.append((cur_b, cur_a))
            
        cur_a, cur_b = 0, 0
        k = 0
        # 最後の点は両者で完全に一致するはずなので、その手前までの頂点を調べる
        for a, b in s_W[:-1]:
            cur_a += a
            cur_b += b
            
            # cur_b が含まれる V の x 座標区間 [X1, X2] を探す
            # cur_b は単調増加なので、k も前にしか進まない (尺取り法で O(N))
            while k < len(pts_V) - 1 and pts_V[k+1][0] < cur_b:
                k += 1
                
            x1, y1 = pts_V[k]
            x2, y2 = pts_V[k+1]
            
            # Y 座標が V の折れ線を「上回って」しまったら False
            # 浮動小数点を避け、両辺に (x2 - x1) を掛けた整数の不等式で判定する
            # cur_a > y1 + (y2 - y1) * (cur_b - x1) / (x2 - x1) と同値
            if cur_a * (x2 - x1) > y1 * (x2 - x1) + (y2 - y1) * (cur_b - x1):
                return False
                
        return True

    # 1. まず全体として成分的な余裕があるかをチェック
    if not check(V, W):
        print("No")
        return
        
    # 2. 濃度の順序が反転しているペアがあるかチェック
    inversion = False
    for i in range(n):
        for j in range(i + 1, n):
            c_V = cmp(V[i], V[j])
            c_W = cmp(W[i], W[j])
            # 初期と目標で濃度の大小が厳密に逆転しているか
            if (c_V == -1 and c_W == 1) or (c_V == 1 and c_W == -1):
                inversion = True
                break
        if inversion:
            break
            
    # 反転がないならそのままの操作（バッファなし）で目標を達成可能
    if not inversion:
        print("Yes")
        return
        
    # 3. 順序の反転がある場合、任意の2つのグラスを完全に混ぜて「空グラス（バッファ）」を作れるかチェック
    for i in range(n):
        for j in range(i + 1, n):
            V_prime = []
            for k in range(n):
                if k != i and k != j:
                    V_prime.append(V[k])
            # i と j を1つのグラスに完全に混ぜた状態を追加
            V_prime.append((V[i][0] + V[j][0], V[i][1] + V[j][1]))
            
            # それでもなお目標をメジャライズできるなら、そのペアを犠牲にして入れ替え作業が可能
            if check(V_prime, W):
                print("Yes")
                return
                
    # どの2つを混ぜても目標成分を作れなくなるなら、反転は不可能
    print("No")

if __name__ == '__main__':
    solve()