【競技プログラミング】AtCoder Beginner Contest 217_D問題

問題

要約

1. 長さLメートルの直線状の木材がある。

2. 木材の左端から1, 2, ..., L-1メートルの地点には、それぞれ線1, 2, ..., L-1が引かれている。

3. Q個のクエリが与えられ、各クエリは(ci, xi)の形式で表される。

4. クエリは以下の2種類がある：

   • ci = 1の場合：線xiがある地点で木材を2つに切る。
   • ci = 2の場合：線xiを含む木材の長さを出力する。

5. クエリは与えられた順番（iの昇順）に処理する。

6. 各クエリを処理する時点で、指定された線xiはまだ切られていないことが保証されている。

変数情報：

• L: 木材の長さ（メートル）
• Q: クエリの数
• ci: i番目のクエリの種類（1または2）
• xi: i番目のクエリで指定される線の番号

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

一覧ページ

アプローチ

木材の切断と長さの計算を効率的に行うために、セグメント木のような考え方を用いる。
ただし、実際のセグメント木の実装ではなく、ソートされた切断点のリストと、各切断点の上下の接続情報を管理する辞書を使用する。
クエリを逆順に処理することで、木材の状態を最終状態から初期状態に向かって再構築しながら解を求める。

解法手順

1. 入力を受け取り、木材の長さLとクエリの数Qを取得する。

2. すべてのクエリ(ci, xi)を読み込む。

3. 切断点のリスト(nums)を作成し、初期値として木材の両端(0とL)を追加する。

4. タイプ1のクエリ(切断操作)で指定された切断点をnumsに追加する。

5. numsをソートする。

6. 各切断点の上下の接続情報を管理する辞書(memo_u, memo_d)を初期化する。

7. クエリを逆順に処理する：

   • タイプ1(切断操作)の場合：
     • 切断点の位置を二分探索で見つける。
     • 接続情報を更新し、切断点を「接続」する。
   • タイプ2(長さ計算)の場合：
     • 指定された位置を含む木材の両端を見つける。
     • 両端の位置から木材の長さを計算し、結果リストに追加する。

8. 結果リストを逆順にして出力する。

ACコード

ac.py

import sys
from bisect import bisect_left

def io_func():
    # 標準入力から木材の長さとクエリ数を読み込む
    l, q = map(int, input().split())
    # すべてのクエリを読み込む
    cx = [tuple(map(int, input().split())) for _ in range(q)]
    return l, q, cx

def solve(l, q, cx):
    # 切断点のリストを初期化（木材の両端を含む）
    nums = [0, l]
    
    # タイプ1のクエリで指定された切断点をnumsに追加
    for c, x in cx:
        if c == 1:
            nums.append(x)
    
    # 切断点をソート
    nums.sort()
    
    # 各切断点の上下の接続情報を管理する辞書を初期化
    memo_u = {i: i for i in range(len(nums))}
    memo_d = {i: i for i in range(len(nums))}
    
    ans = []
    
    # クエリを逆順に処理
    for c, x in reversed(cx):
        if c == 1:  # 切断操作
            # 切断点の位置を二分探索で見つける
            p = bisect_left(nums, x)
            # 接続情報を更新
            memo_u[p] = memo_u[p + 1]
            memo_d[p] = memo_d[p - 1]
        else:  # 長さ計算
            # 指定された位置を含む木材の両端を見つける
            p = bisect_left(nums, x) - 1
            q = p + 1
            while memo_d[p] != p:
                p -= 1
            while memo_u[q] != q:
                q += 1
            # 木材の長さを計算し、結果リストに追加
            ans.append(nums[q] - nums[p])
    
    # 結果を逆順にして返す
    return ans[::-1]

if __name__ == '__main__':
    # 入力を受け取る
    l, q, cx = io_func()
    # 問題を解く
    result = solve(l, q, cx)
    # 結果を出力
    print(*result, sep='\n')

###
# - l: 木材の初期長さ
# - q: クエリの数
# - cx: クエリのリスト（各要素は(c, x)のタプル）
# - nums: ソートされた切断点のリスト
# - memo_u, memo_d: 各切断点の上下の接続情報を管理する辞書
# - ans: 長さ計算の結果を格納するリスト

# 1. io_func関数:
#    - 標準入力から木材の長さ、クエリ数、およびすべてのクエリを読み込む
#    - 読み込んだデータをタプルとして返す

# 2. solve関数:
#    - 切断点のリスト(nums)を初期化し、タイプ1のクエリで指定された切断点を追加
#    - numsをソートし、各切断点の接続情報を管理する辞書(memo_u, memo_d)を初期化
#    - クエリを逆順に処理:
#      - タイプ1(切断操作)の場合: 切断点の位置を見つけ、接続情報を更新
#      - タイプ2(長さ計算)の場合: 指定された位置を含む木材の両端を見つけ、長さを計算
#    - 計算結果を逆順にして返す

# 3. main関数:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く
#    - 結果を出力する

思考過程

• クエリを逆順に処理することで、木材の状態を最終状態から初期状態に向かって再構築できる。
• 切断点をソートしたリストと接続情報を管理する辞書を使用することで、セグメント木のような効果を得られる。
• 二分探索を使用して、切断点や長さ計算の位置を素早く見つけることができる。

計算量の概算

O(Q log Q)