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

• 問題: No.2594 Mix shake!!
• ユーザー: hitonanode
• 提出日時: 2026-02-23 00:00:15
• 言語: Python3 (3.14.3 + numpy 2.4.2 + scipy 1.17.0)
• 結果: WA
• 実行時間: -
• コード長: 3,114 bytes
• コンパイル時間: 873 ms
• コンパイル使用メモリ: 20,820 KB
• 実行使用メモリ: 15,524 KB
• 最終ジャッジ日時: 2026-02-23 11:38:12
• 合計ジャッジ時間: 19,371 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

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

ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    n = int(data[0])
    A = [int(x) for x in data[1:n+1]]
    B = [int(x) for x in data[n+1:2*n+1]]
    C = [int(x) for x in data[2*n+1:3*n+1]]
    D = [int(x) for x in 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 > c/d は a*d > b*c と同値
    import functools
    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

    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))
            
        # W の各頂点が V の折れ線の下にあるか判定
        cur_a, cur_b = 0, 0
        for a, b in s_W:
            cur_a += a
            cur_b += b
            # x座標が cur_b となる V の折れ線上の y座標 を求める
            # pts_V は x(バナナ) について単調増加
            for k in range(len(pts_V) - 1):
                x1, y1 = pts_V[k]
                x2, y2 = pts_V[k+1]
                if x1 <= cur_b <= x2:
                    if x1 == x2:
                        max_y = max(y1, y2)
                    else:
                        max_y = y1 + (y2 - y1) * (cur_b - x1) / (x2 - x1)
                    if cur_a > max_y + 1e-9: # 浮動小数点の誤差対策
                        return False
                    break
        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 を混ぜたものを追加
            V_prime.append((V[i][0] + V[j][0], V[i][1] + V[j][1]))
            
            if check(V_prime, W):
                print("Yes")
                return
                
    print("No")

if __name__ == '__main__':
    solve()