Zenn
✨

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

2024/12/27に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc294/tasks/abc294_e

要約

  1. マス目の情報は連長圧縮された形で与えらる。
  2. 各列について、1行目と2行目の数字が同じである列の数を数える。
  • L: 列の数
  • N1: 1行目の連長圧縮後の長さ
  • N2: 2行目の連長圧縮後の長さ
  • (v1,i, l1,i): 1行目のi番目の連長圧縮データ（値と長さ）
  • (v2,i, l2,i): 2行目のi番目の連長圧縮データ（値と長さ）

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

一覧ページ

アプローチ

連長圧縮されたデータを効率的に処理し、同じ数字が書かれている列の数を数える

解法手順

  1. 入力データを読み込む。L（列数）、N1（1行目の圧縮データ数）、N2（2行目の圧縮データ数）を取得する。

  2. 1行目と2行目の圧縮データをそれぞれ読み込む。各データは（値、長さ）のペアで表される。

  3. 両方の行のデータを同時に走査するポインタを用意する。

  4. 以下の処理を、どちらかの行のデータをすべて処理するまで繰り返す：

    • 現在のポインタが指す1行目と2行目の値を比較する。
    • 値が同じ場合、重なっている範囲の長さを計算し、答えに加算する。
    • ポインタを、処理が終了した方の次のデータに進める。

  5. すべての処理が終わったら、同じ数字が書かれている列の総数を出力する。

ACコード

ac.py
def io_func():
    # 入力データを読み込む
    l, n1, n2 = map(int, input().split())  # L（列数）、N1（1行目の圧縮データ数）、N2（2行目の圧縮データ数）を取得
    a = [list(map(int, input().split())) for _ in range(n1)]  # 1行目の圧縮データを読み込む
    b = [list(map(int, input().split())) for _ in range(n2)]  # 2行目の圧縮データを読み込む
    return l, n1, n2, a, b

def solve(l, n1, n2, a, b):
    ans = 0  # 同じ数字が書かれている列の総数
    a_idx, a_end = 0, 0  # 1行目のデータを走査するポインタと現在の位置
    b_idx, b_end = 0, 0  # 2行目のデータを走査するポインタと現在の位置

    # どちらかの行のデータをすべて処理するまで繰り返す
    while a_idx < n1 and b_idx < n2:
        if a[a_idx][0] == b[b_idx][0]:  # 現在のポインタが指す1行目と2行目の値を比較
            start = max(a_end, b_end)  # 重なりの開始位置
            end = min(a[a_idx][1] + a_end, b[b_idx][1] + b_end)  # 重なりの終了位置
            ans += end - start  # 重なっている範囲の長さを答えに加算

        # ポインタを、処理が終了した方の次のデータに進める
        if a[a_idx][1] + a_end < b[b_idx][1] + b_end:
            a_end += a[a_idx][1]
            a_idx += 1
        else:
            b_end += b[b_idx][1]
            b_idx += 1

    return ans

# メイン処理
l, n1, n2, a, b = io_func()  # 入力データを取得
result = solve(l, n1, n2, a, b)  # 問題を解く
print(result)  # 結果を出力

###
# l: 列数
# n1: 1行目の圧縮データ数
# n2: 2行目の圧縮データ数
# a: 1行目の圧縮データ（各要素は[値, 長さ]のリスト）
# b: 2行目の圧縮データ（各要素は[値, 長さ]のリスト）
# ans: 同じ数字が書かれている列の総数
# a_idx, b_idx: それぞれ1行目と2行目のデータを走査するポインタ
# a_end, b_end: それぞれ1行目と2行目の現在の位置

# 1. io_func関数:
#    - 標準入力から必要なデータを読み込む
#    - 列数、圧縮データ数、圧縮データを返す
# 2. solve関数:
#    - 2つの圧縮データを同時に走査し、同じ数字が書かれている列の数を数える
#    - ポインタを使用して効率的に比較を行う
#    - 重なりがある場合、その長さを計算して結果に加算する
#    - どちらかのデータをすべて処理するまで繰り返す
# 3. メイン処理:
#    - io_func関数を呼び出して入力データを取得
#    - solve関数を呼び出して問題を解く
#    - 結果を出力する```

覚書

L = 10 (10列)とする。
上の行: 1 1 1 2 2 3 3 3 4 4
下の行: 1 1 2 2 2 3 3 4 4 4

問題では、データが「連長圧縮」された形で与えられる。

連長圧縮とは

  1. 同じ数字が連続して現れる部分をまとめる。
  2. (値, 長さ)のペアで表現する。

上の行: 1 1 1 2 2 3 3 3 4 4
下の行: 1 1 2 2 2 3 3 4 4 4
を連長圧縮すると
上の行: (1,3), (2,2), (3,3), (4,2)
下の行: (1,2), (2,3), (3,2), (4,3)

この圧縮されたデータから、元のデータを復元せずに、同じ数字が書かれている列の数を効率的に数える。

解き方の基本的なアイデアは：

  1. 両方の行のデータを同時に走査する。
  2. 同じ値のペアが見つかったら、その重なりの長さを計算する。
  3. 重なりの長さの合計が答えになる。

Discussion