Submission #68094224

---

Source Code Expand

import sys
import time
import tracemalloc
from typing import Tuple, List, NamedTuple, Optional, Callable, Any, TypeVar
from dataclasses import dataclass

# 型変数の定義
T = TypeVar('T')
P = TypeVar('P')


@dataclass(frozen=True)
class PerformanceMetrics:
    """パフォーマンス測定結果を格納するデータクラス"""
    execution_time_ms: float
    memory_used_mb: float
    peak_memory_mb: float


class Card(NamedTuple):
    """カード情報を表すNamedTuple（メモリ効率最適化）"""
    a: int
    b: int


def solve_card_score_optimized(input_str: str) -> int:
    """
    カードスコア最大化問題を解く関数（最適化版）
    
    アルゴリズム:
    スコア = |表の総和| + |裏の総和| を最大化
    4つのパターンを同時計算:
    1. 表≥0, 裏≥0: スコア = 表の総和 + 裏の総和
    2. 表≥0, 裏<0: スコア = 表の総和 - 裏の総和  
    3. 表<0, 裏≥0: スコア = -表の総和 + 裏の総和
    4. 表<0, 裏<0: スコア = -表の総和 - 裏の総和
    
    Args:
        input_str (str): 標準入力の文字列
        
    Returns:
        int: 最大スコア
        
    Time Complexity: O(N)
    Space Complexity: O(1)
    """
    lines: List[str] = input_str.strip().split('\n')
    n: int = int(lines[0])
    
    # 4つのパターンのスコアを同時に計算（型ヒント付き）
    score1: int = 0  # パターン1: a + b (両方非負)
    score2: int = 0  # パターン2: a - b (表非負、裏負)
    score3: int = 0  # パターン3: -a + b (表負、裏非負)
    score4: int = 0  # パターン4: -a - b (両方負)
    
    # 各カードを1回だけ読み込んで処理（メモリ効率最大化）
    for i in range(1, n + 1):
        # split()の結果を直接アンパック（中間リスト削除）
        a_str, b_str = lines[i].split()
        a: int = int(a_str)
        b: int = int(b_str)
        
        # 各パターンでの貢献度を計算（インライン計算）
        contrib1: int = a + b
        contrib2: int = a - b
        contrib3: int = -a + b
        contrib4: int = -a - b
        
        # 条件分岐で効率的に加算（Python 3.11の最適化活用）
        if contrib1 > 0:
            score1 += contrib1
        if contrib2 > 0:
            score2 += contrib2
        if contrib3 > 0:
            score3 += contrib3
        if contrib4 > 0:
            score4 += contrib4
    
    # max()関数を使わず条件分岐で最大値を効率的に求める
    max_score: int = score1
    if score2 > max_score:
        max_score = score2
    if score3 > max_score:
        max_score = score3
    if score4 > max_score:
        max_score = score4
    
    return max_score


def solve(input_str: str) -> str:
    """
    標準入力から問題を読み込み、解答を出力する関数
    
    Args:
        input_str (str): 標準入力の文字列
        
    Returns:
        str: 解答文字列
    """
    return str(solve_card_score_optimized(input_str))


def measure_performance(func: Callable[..., T], *args: Any) -> Tuple[T, PerformanceMetrics]:
    """
    関数のパフォーマンスを測定する関数
    
    Args:
        func (Callable[..., T]): 測定対象の関数
        *args (Any): 関数の引数
        
    Returns:
        Tuple[T, PerformanceMetrics]: 実行結果とパフォーマンス指標
    """
    # メモリトレースを開始
    tracemalloc.start()
    
    # 実行時間測定開始
    start_time: float = time.perf_counter()
    
    # 関数実行
    result: T = func(*args)
    
    # 実行時間測定終了
    end_time: float = time.perf_counter()
    
    # メモリ使用量取得
    current_memory: int
    peak_memory: int
    current_memory, peak_memory = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    
    # パフォーマンス指標計算
    execution_time_ms: float = (end_time - start_time) * 1000
    memory_used_mb: float = current_memory / 1024 / 1024
    peak_memory_mb: float = peak_memory / 1024 / 1024
    
    metrics: PerformanceMetrics = PerformanceMetrics(
        execution_time_ms=execution_time_ms,
        memory_used_mb=memory_used_mb,
        peak_memory_mb=peak_memory_mb
    )
    
    return result, metrics


def generate_large_test_case(n: int) -> str:
    """
    大きなテストケースを生成する関数
    
    Args:
        n (int): カードの枚数
        
    Returns:
        str: テスト用入力文字列
    """
    import random
    
    lines: List[str] = [str(n)]
    
    # シード固定で再現可能なテスト
    random.seed(42)
    
    for _ in range(n):
        # -10^9 to 10^9 の範囲でランダム生成
        a: int = random.randint(-1_000_000_000, 1_000_000_000)
        b: int = random.randint(-1_000_000_000, 1_000_000_000)
        lines.append(f"{a} {b}")
    
    return '\n'.join(lines)


def validate_input(input_str: str) -> bool:
    """
    型安全な入力検証関数
    
    Args:
        input_str (str): 検証対象の入力
        
    Returns:
        bool: 入力が有効かどうか
    """
    try:
        lines: List[str] = input_str.strip().split('\n')
        
        if len(lines) < 1:
            return False
        
        n: int = int(lines[0])
        if n < 1 or n > 100_000:
            return False
        
        if len(lines) != n + 1:
            return False
        
        for i in range(1, n + 1):
            parts: List[str] = lines[i].split()
            if len(parts) != 2:
                return False
            
            a: int = int(parts[0])
            b: int = int(parts[1])
            
            if abs(a) > 1_000_000_000 or abs(b) > 1_000_000_000:
                return False
        
        return True
        
    except (ValueError, IndexError):
        return False


def run_tests() -> None:
    """テスト実行関数"""
    print("=== Python版 カードスコア最大化問題 テスト ===\n")
    
    # 基本テストケース
    test_input: str = """5
2 8
4 -5
5 -3
-4 1
-2 -3"""
    
    print("基本テストケース:")
    result: str
    metrics: PerformanceMetrics
    result, metrics = measure_performance(solve, test_input)
    print(f"結果: {result} (期待値: 18)")
    print(f"実行時間: {metrics.execution_time_ms:.3f} ms")
    print(f"メモリ使用量: {metrics.memory_used_mb:.3f} MB")
    print(f"ピークメモリ: {metrics.peak_memory_mb:.3f} MB\n")
    
    # パフォーマンステスト
    sizes: Tuple[int, ...] = (1_000, 10_000, 50_000, 100_000)
    
    for size in sizes:
        print(f"パフォーマンステスト (N={size:,}):")
        large_input: str = generate_large_test_case(size)
        perf_result: str
        perf_metrics: PerformanceMetrics
        perf_result, perf_metrics = measure_performance(solve, large_input)
        
        print(f"結果: {perf_result}")
        print(f"実行時間: {perf_metrics.execution_time_ms:.3f} ms")
        print(f"メモリ使用量: {perf_metrics.memory_used_mb:.3f} MB")
        print(f"ピークメモリ: {perf_metrics.peak_memory_mb:.3f} MB")
        print(f"1カードあたりの処理時間: {perf_metrics.execution_time_ms / size * 1000:.3f} μs\n")


def main() -> None:
    """メイン処理関数"""
    try:
        # 標準入力から一度に全て読み込み
        input_str: str = sys.stdin.read()
        
        # 入力検証（デバッグ時のみ有効化）
        # if not validate_input(input_str):
        #     print("Invalid input format", file=sys.stderr)
        #     sys.exit(1)
        
        result: str = solve(input_str)
        print(result)
        
    except Exception as e:
        print(f"Error: {e}", file=sys.stderr)
        sys.exit(1)


if __name__ == "__main__":
    # テストを実行したい場合はコメントアウト
    # run_tests()
    
    # 本番実行
    main()

Submission Info

Judge Result