問題
要約
-
長さLメートルの直線状の木材がある。
-
木材の左端から1, 2, ..., L-1メートルの地点には、それぞれ線1, 2, ..., L-1が引かれている。
-
Q個のクエリが与えられ、各クエリは(ci, xi)の形式で表される。
-
クエリは以下の2種類がある：
- ci = 1の場合：線xiがある地点で木材を2つに切る。
- ci = 2の場合：線xiを含む木材の長さを出力する。
-
クエリは与えられた順番（iの昇順）に処理する。
-
各クエリを処理する時点で、指定された線xiはまだ切られていないことが保証されている。
変数情報：
- L: 木材の長さ（メートル）
- Q: クエリの数
- ci: i番目のクエリの種類（1または2）
- xi: i番目のクエリで指定される線の番号
既存投稿一覧ページへのリンク
独り言
別解はこちら。
学習中の身としてはこちらの解き方の方が理解しやすかった。
アプローチ
ソート済み集合を使用して、木材の切れ目の位置を管理する。
初期状態では木材の両端（0とL）のみが集合に含まれる。
各クエリに対して、切る操作の場合は新しい切れ目を集合に追加し、長さを求める操作の場合は指定された位置の前後の切れ目を見つけて、その差を計算する。
解法手順
-
入力を受け取る
木材の長さL、クエリの数Q、各クエリの情報(ci, xi)を読み込む。 -
ソート済み集合Sを初期化し、木材の両端（0とL）を追加する。
-
各クエリに対して以下の処理を行う
- クエリの種類ciが1の場合（木材を切る操作）
- 指定された位置xiをソート済み集合Sに追加する。
- クエリの種類ciが2の場合（長さを求める操作）
- 指定された位置xiが集合S内でどの位置に挿入されるかを二分探索で求める。
- その位置の直前の要素と、xiの差を計算し、結果として出力する。
- クエリの種類ciが1の場合（木材を切る操作）
-
すべてのクエリを処理し終えたら終了する。
ACコード
ac.py
from sortedcontainers import SortedSet # ソート済み集合を使用するためのライブラリをインポート
def io_func():
# 入力を受け取る関数
L, Q = map(int, input().split()) # 木材の長さLとクエリの数Qを入力
queries = [list(map(int, input().split())) for _ in range(Q)] # 各クエリの情報を入力
return L, Q, queries
def solve(L, Q, queries):
# メインの処理を行う関数
S = SortedSet([0, L]) # ソート済み集合Sを初期化し、木材の両端（0とL）を追加
for c, x in queries: # 各クエリに対して処理を行う
if c == 1: # クエリの種類が1（木材を切る操作）の場合
S.add(x) # 指定された位置xをソート済み集合Sに追加
else: # クエリの種類が2（長さを求める操作）の場合
pos = S.bisect_left(x) # 指定された位置xが集合S内でどの位置に挿入されるかを二分探索
print(S[pos] - S[pos-1]) # その位置の直前の要素と、xの差を計算し出力
# メイン処理
L, Q, queries = io_func() # 入力を受け取る
solve(L, Q, queries) # 問題を解く
###
# L: 木材の長さ
# Q: クエリの数
# queries: 各クエリの情報（種類と位置）を格納したリスト
# S: 木材の切れ目の位置を管理するソート済み集合
# c: クエリの種類（1: 切る、2: 長さを求める）
# x: クエリで指定される位置
# pos: 二分探索で求めた位置
# 1. 必要なライブラリ（sortedcontainers）をインポートする。
# 2. io_func関数で入力を受け取る。
# 3. solve関数で主な処理を行う。
# a. ソート済み集合Sを初期化し、木材の両端（0とL）を追加する。
# b. 各クエリに対して以下の処理を行う：
# - クエリの種類が1の場合、指定された位置をSに追加する。
# - クエリの種類が2の場合、指定された位置の前後の切れ目を見つけ、その差を出力する。
# 4. メイン処理で、io_func関数とsolve関数を呼び出す。
思考過程
- 木材の切れ目を管理するためには、順序付きのデータ構造が必要。
- 頻繁な挿入と検索が行われる。
- ソート済み集合（SortedSet）を使用することで、挿入と検索を効率的に行える。
- 二分探索を利用することで、特定の位置の前後の切れ目を素早く見つけられる。
計算量の概算
O(Q log Q)
その他周辺知識
順序付き集合
from sortedcontainers import SortedSet
S = SortedSet([0, L])
ここでは、SortedSetという順序付き集合を使用している。
この集合は、要素が常にソートされた状態を保つ特殊な集合である。
初期状態では、木材の両端である0とLを要素として持つ。
二分探索
pos = S.bisect_left(x)
二分探索アルゴリズムを使用して、指定された位置xが集合S内でどの位置に挿入されるべきかを効率的に探索している。
これにより、ログ時間で適切な位置を見つけることができる。
区間の長さ（2点間の距離計算）
else:
pos = S.bisect_left(x)
print(S[pos] - S[pos-1])
クエリ種類が2の場合：
- S.bisect_left(x)で、xが挿入されるべき位置posを二分探索で求める。
- S[pos]はx以上の最小の要素、S[pos-1]はx未満の最大の要素を表す。
- これらの差を計算し、print関数で出力する。
エッセンス
sample_code.py
from sortedcontainers import SortedSet
class IntervalManager:
def __init__(self, start, end):
"""
区間マネージャーを初期化する
:param start: 区間の開始位置
:param end: 区間の終了位置
"""
self.intervals = SortedSet([start, end])
def split(self, position):
"""
指定された位置で区間を分割する
:param position: 分割する位置
"""
self.intervals.add(position)
def get_interval_length(self, position):
"""
指定された位置を含む区間の長さを取得する
:param position: 長さを取得したい位置
:return: 区間の長さ
"""
pos = self.intervals.bisect_left(position)
return self.intervals[pos] - self.intervals[pos-1]
# 使用例
def example_usage():
# 区間マネージャーを初期化（例：0から100までの区間）
manager = IntervalManager(0, 100)
# 区間を分割
manager.split(30)
manager.split(70)
# 特定の位置での区間の長さを取得
print(manager.get_interval_length(20)) # 出力: 30 (0から30の区間)
print(manager.get_interval_length(50)) # 出力: 40 (30から70の区間)
print(manager.get_interval_length(80)) # 出力: 30 (70から100の区間)
# 使用例を実行
example_usage()