【競技プログラミング】AtCoder Beginner Contest 371_E問題

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

ステップ 1: 辞書を用いた最新インデックス管理

• 配列 $ A $ を左から順に走査し、各値が最後に登場したインデックスを記録する辞書 last_index を使用する。
• これにより、「現在のインデックスまでにその値が初めて登場したかどうか」を効率的に判定できる。

ステップ 2: 各インデックスでの種類数の更新

• 現在のインデックス $ i $ において、以下を行う
  • 値 $ A[i] $ が初めて登場する場合:
    • 種類数を増加させるため、区間内で新しい値が追加されたとみなす。
    • 種類数の合計 sum_g に $ i + 1 $ を加算する。
  • 値 $ A[i] $ が既に登場している場合
    • 最新登場位置との差分 ($ i - last_index[A[i]] $) を sum_g に加算する。

ステップ 3: 累積和の計算

• 各インデックスで得られた sum_g を累積する。
• 最終的な答えはこの累積値となる。

解法手順の補足

1. 問題の性質を理解する

• 問題では、全ての区間 $[i, j]$ における異なる値の種類数 $f(i, j)$ の総和を計算する必要がある。
• 単純に全ての区間を列挙して $f(i, j)$ を計算すると、区間ごとに重複を除いた値を数える必要があり、計算量は $O(N^3)$ となる（区間数が $O(N^2)$、各区間で重複チェックが $O(N)$）。

---

2. 効率化のための観察

観察1: 各要素の「最後に登場した位置」を記録する

• 配列 $A$ を左から右へ順に走査しながら、各要素が最後に登場したインデックスを記録することで、その要素が新しい区間でどのように寄与するかを管理できる。
• この情報を利用すれば、現在のインデックス $i$ までの種類数（新規性）を効率的に計算できる。

観察2: 累積的な種類数の管理

• 現在のインデックス $i$ までに含まれる値の種類数を累積して管理する。
• 新しい値が登場した場合は種類数が増加し、既知の値が再登場した場合はその位置関係から種類数を調整します。

観察3: 全体の累積和として答えを構築

• 各インデックスで計算した累積的な種類数を逐次加算していくことで、全ての区間 $[i, j]$ の総和を効率的に求める。

---

3. 解法設計

これらの観察から、次のような手順で解法を設計する

1. 配列 $A$ を左から右へ走査しながら処理する。
2. 各要素について「最後に登場したインデックス」を記録する辞書 last_index を用意する。
3. 現在のインデックス $i$ において：
   • 要素が初めて登場する場合：その要素は新しい値として種類数に寄与する。
   • 要素が再登場する場合：その要素が最後に登場した位置との差分だけ種類数を調整する。
4. 累積的な種類数 sum_g を更新し、それを答え ans に加算していく。
5. 最後に答え ans を出力する。

---

4. アルゴリズムの直感的理解

この方法では、「全ての区間 $[i, j]$」について明示的に処理するわけではなく、「現在まで処理した部分配列」に対して効率的に情報を更新する。

---

5. 実装とその流れ

以下は具体的な実装手順です：

1. 初期化：

   • 答え ans = 0 を初期化。
   • 種類数合計 sum_g = 0 を初期化。
   • 辞書 last_index = {} を初期化。

2. 配列走査：

   • 各インデックス $i$ について：
     • 要素 $A[i]$ が初めて登場する場合：
       • 種類数合計 sum_g に $(i + 1)$ を加算。
     • 要素 $A[i]$ が再登場する場合：
       • 前回登場位置との差分 $(i - last_index[A[i]])$ を sum_g に加算。

3. 累積更新：

   • 現在までの累積結果 sum_g を答え ans に加算。

4. 結果出力：

   • 最終結果 ans を出力。

ACコード1

ac.py

import logging

# ロガーセットアップ関数
def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')

        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)

    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

# 入力処理関数（AtCoder用のため、入力促進メッセージはなし）
def io_func():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

# メインの問題解決処理
def solve(N, A, logger):
    ans = 0  # 最終的な答えを格納する変数
    last_index = {}  # 各数値が最後に登場したインデックスを記録する辞書
    sum_g = 0  # 現在までの種類数の合計値

    for i, value in enumerate(A):
        if value not in last_index:
            sum_g += i + 1
            logger.debug(f"値 {value} は初登場。sum_g に {i + 1} を加算し、sum_g={sum_g}")
        else:
            sum_g += i - last_index[value]
            logger.debug(f"値 {value} は再登場。前回登場位置 {last_index[value]} との差 {i - last_index[value]} を sum_g に加算し、sum_g={sum_g}")

        ans += sum_g
        logger.debug(f"現在のインデックス: {i}, 値: {value}, 累積答え: ans={ans}")

        last_index[value] = i  # この数値の最新のインデックスを更新

    print(ans)  # 最終結果を出力
    logger.debug(f"最終結果: {ans}")

# メイン関数
def main():
    debug_mode = False  # 必要に応じてFalseに変更可能
    logger = setup_logger(debug_mode)
    
    N, A = io_func()
    logger.debug(f"入力完了 N={N}, A={A}")

    solve(N, A, logger)

if __name__ == "__main__":
    main()