提出 #68284856

---

ソースコード 拡げる

#!/usr/bin/env python3
"""
配列内で条件を満たすペア数を効率的に計算するプログラム

問題: 1 ≤ j < i ≤ N かつ Aj = Ai を満たすペア(i, j)の数を求める
制約: N ≤ 100,000, Ai ≤ 10^9, 実行時間 ≤ 2秒, メモリ ≤ 1024MB
"""

import sys
from typing import Dict, List, Tuple
from collections import defaultdict


def read_input() -> str:
    """
    標準入力から全データを読み込む
    
    Returns:
        str: 入力データの文字列（改行文字を含む）
    
    Notes:
        - sys.stdin.read()を使用してメモリ効率を最適化
        - strip()で末尾の不要な改行を除去
    """
    return sys.stdin.read().strip()


def parse_input(input_data: str) -> Tuple[int, List[int]]:
    """
    入力データを解析して配列サイズと要素のリストに変換
    
    Args:
        input_data (str): 標準入力から読み込んだ生データ
    
    Returns:
        Tuple[int, List[int]]: (配列サイズN, 要素のリスト)
    
    Raises:
        ValueError: 入力フォーマットが不正な場合
        
    Notes:
        - 型安全性を保証するためにint()変換を明示
        - メモリ効率のためリスト内包表記を使用
    """
    lines: List[str] = input_data.split('\n')
    
    if len(lines) < 1:
        raise ValueError("入力データが不正です")
    
    n: int = int(lines[0])
    
    if len(lines) != n + 1:
        raise ValueError(f"期待される行数: {n + 1}, 実際の行数: {len(lines)}")
    
    # リスト内包表記でメモリ効率を向上
    arr: List[int] = [int(lines[i]) for i in range(1, n + 1)]
    
    return n, arr


def count_pairs_optimized(arr: List[int]) -> int:
    """
    条件を満たすペア(i, j)の数を効率的に計算
    
    1 ≤ j < i ≤ N かつ Aj = Ai を満たすペアの数を返す
    
    アルゴリズム:
    1. 各値の出現回数をカウント（O(N)）
    2. 同じ値がk個ある場合、ペア数はC(k,2) = k * (k-1) // 2
    3. 全ての値についてペア数を合計
    
    Args:
        arr (List[int]): 入力配列
    
    Returns:
        int: 条件を満たすペアの総数
        
    Time Complexity: O(N)
    Space Complexity: O(K) where K is number of distinct values (worst case O(N))
    
    Notes:
        - defaultdict(int)を使用してメモリアクセスを最適化
        - 整数除算(//)を使用してオーバーフローを防止
        - Pylanceの型チェックに準拠
    """
    # 各値の出現回数をカウント
    # defaultdict(int)はキーが存在しない場合に0を返すため、
    # get()メソッドよりも高速でメモリ効率が良い
    count_map: Dict[int, int] = defaultdict(int)
    
    # O(N)で配列をスキャンして出現回数をカウント
    for num in arr:
        count_map[num] += 1
    
    total_pairs: int = 0
    
    # 各値について組み合わせ数を計算
    # O(K)で処理（Kは異なる値の数、最悪でもO(N)）
    for count in count_map.values():
        if count >= 2:
            # k個の要素から2個を選ぶ組み合わせ数
            # C(k,2) = k * (k-1) / 2
            # 整数除算を使用してfloat型への変換を回避
            pairs_for_this_value: int = count * (count - 1) // 2
            total_pairs += pairs_for_this_value
    
    return total_pairs


def validate_constraints(n: int, arr: List[int]) -> None:
    """
    入力データが制約条件を満たしているかを検証
    
    Args:
        n (int): 配列のサイズ
        arr (List[int]): 入力配列
        
    Raises:
        ValueError: 制約違反が検出された場合
        
    Notes:
        - 実行前に制約をチェックすることでランタイムエラーを防止
        - Pylanceの型チェックに準拠した例外処理
    """
    # 配列サイズの制約チェック
    if not (1 <= n <= 100_000):
        raise ValueError(f"Nが制約を満たしません: N = {n} (1 ≤ N ≤ 100,000)")
    
    # 配列長の整合性チェック
    if len(arr) != n:
        raise ValueError(f"配列長が不一致: 期待値 = {n}, 実際 = {len(arr)}")
    
    # 各要素の値域チェック
    for i, value in enumerate(arr):
        if not (1 <= value <= 10**9):
            raise ValueError(f"A[{i}]が制約を満たしません: {value} (1 ≤ Ai ≤ 10^9)")


def main() -> None:
    """
    メイン処理関数
    
    入力の読み込み、解析、検証、計算、出力を統括
    
    Notes:
        - try-except文による堅牢なエラーハンドリング
        - 型注釈により静的解析ツールでの検証を可能にする
        - sys.exit()による適切なプロセス終了コード設定
    """
    try:
        # Step 1: 入力データの読み込み
        input_data: str = read_input()
        
        # Step 2: データの解析
        n: int
        arr: List[int]
        n, arr = parse_input(input_data)
        
        # Step 3: 制約の検証
        validate_constraints(n, arr)
        
        # Step 4: ペア数の計算
        result: int = count_pairs_optimized(arr)
        
        # Step 5: 結果の出力
        print(result)
        
    except ValueError as e:
        print(f"入力エラー: {e}", file=sys.stderr)
        sys.exit(1)
    except Exception as e:
        print(f"予期しないエラー: {e}", file=sys.stderr)
        sys.exit(1)


if __name__ == "__main__":
    main()

提出情報

ジャッジ結果