LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@o_chan_t(おー ちゃん)

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

Last updated at Posted at 2024-12-01

問題

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

一覧ページ

独り言

解くだけなら累積和で良かったけど、前の状態からの遷移を考慮したかったので動的計画法を使いました。
動的計画法は、机上トレースすると分かりやすい。というか、机上トレースせず頭の中で組む能力がまだ持てていないのですよね。
EDPCもO問題で止まってしまっているし・・・

解法手順

  1. 入力から区間の情報を読み取り、左端の値でソートする。
  2. 動的計画法のためのDPテーブルを初期化する。
  3. ソートされた右端値を保持するためのSortedListを用意する。
  4. ソートされた区間リストを順に走査する：
    a. 現在の区間の開始点以下の右端値の数を二分探索で求める。
    b. 現在の区間と重なる前の区間の数を計算する。
    c. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    d. 現在の区間の右端値をSortedListに追加する。
  5. DPテーブルの最後の要素（総ペア数）を出力する。

ACコード

ac.py

# SortedListをインポート
from sortedcontainers import SortedList

# bisectモジュールをインポート（二分探索に使用）
import bisect

# 入力から区間の数Nを読み取る
N = int(input())

# N個の区間を読み取り、タプルのリストとして保存
sections = [tuple(map(int, input().split())) for _ in range(N)]

# 区間を左端の値でソート
sections = sorted(sections, key=lambda x: x[0])

# 動的計画法のためのDPテーブルを初期化
dp = [0] * N

# ソートされた右端値を保持するためのSortedListを用意
end_sec = SortedList()

# ソートされた区間リストを順に走査
for i in range(N):
    # 現在の区間の開始点と終了点を取得
    start, end = sections[i]
    
    # 現在の区間の開始点以下の右端値の数を二分探索で求める
    idx = end_sec.bisect_left(start)
    
    # 現在の区間と重なる前の区間の数を計算
    count = i - idx
    
    # DPテーブルを更新（前の状態に新たに重なった区間の数を加える）
    if i > 0:
        dp[i] = dp[i - 1] + count
    
    # 現在の区間の右端値をSortedListに追加
    end_sec.add(end)

# DPテーブルの最後の要素（総ペア数）を出力
print(dp[N - 1])

動的計画法の復元

ac.py
# SortedListをインポート
from sortedcontainers import SortedList

# bisectモジュールをインポート（二分探索に使用）
import bisect

# 入力から区間の数Nを読み取る
N = int(input())

# N個の区間を読み取り、タプルのリストとして保存
sections = [tuple(map(int, input().split())) for _ in range(N)]

# 区間を左端の値でソート
sections = sorted(sections, key=lambda x: x[0])

# 動的計画法のためのDPテーブルを初期化
dp = [0] * N

# ソートされた右端値を保持するためのSortedListを用意
end_sec = SortedList()

# ★ 復元用の配列を初期化
reconstruction = [[] for _ in range(N)]

# ソートされた区間リストを順に走査
for i in range(N):
    # 現在の区間の開始点と終了点を取得
    start, end = sections[i]
    
    # 現在の区間の開始点以下の右端値の数を二分探索で求める
    idx = end_sec.bisect_left(start)
    
    # 現在の区間と重なる前の区間の数を計算
    count = i - idx
    
    # DPテーブルを更新（前の状態に新たに重なった区間の数を加える）
    if i > 0:
        dp[i] = dp[i - 1] + count
        # ★ 前の状態の復元結果をコピー
        reconstruction[i] = reconstruction[i-1].copy()
    
    # ★ 新たに重なった区間を復元結果に追加
    for j in range(idx, i):
        reconstruction[i].append((sections[j], sections[i]))
    
    # 現在の区間の右端値をSortedListに追加
    end_sec.add(end)

# DPテーブルの最後の要素（総ペア数）を出力
print(dp[N - 1])

# ★ 復元結果を出力
print("重なっている区間のペア:")
for pair in reconstruction[N-1]:
    print(f"{pair[0]} と {pair[1]}")

机上トレース

例1

N=7
section = [(3, 15), (4, 7), (5, 8), (7, 14), (8, 11), (8, 13), (12, 14)]

入力から区間の情報を読み取り、左端の値でソートする。

section = [(3, 15), (4, 7), (5, 8), (7, 14), (8, 11), (8, 13), (12, 14)]

動的計画法のためのDPテーブルを初期化する。

dp = [0, 0, 0, 0, 0, 0, 0]

ソートされた区間リストを順に走査する：

1回目のループ

  1. 現在の区間の開始点以下の右端値の数を二分探索で求める。
    3以下が存在するインデックスは0
  2. 現在の区間と重なる前の区間の数を計算する。
    count = 0-0 = 0
  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    -> 初回ループはスキップ
  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [15]

2回目のループ（(3, 15), (4, 7)について考える）

  1. 現在の区間の開始点以下の右端値の数[15]を二分探索で求める。
    4以下が存在するインデックスは0
  2. 現在の区間と重なる前の区間の数を計算する。
    count = 1-0 = 1 -> (3, 15), (4, 7)は区間が重なっている
  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    dp[1] = dp[0]+1 = 1
    dp = [0, 1, 0, 0, 0, 0, 0]
  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [7, 15]

3回目のループ（(3, 15), (4, 7), (5, 8)について考える）

  1. 現在の区間(5, 8)の開始点以下の右端値の数[7, 15]を二分探索で求める。
    5以下が存在するインデックスは0
  2. 現在の区間と重なる前の区間の数を計算する。
    count = 2-0 = 2 -> (3, 15), (4, 7), (5, 8)は区間が重なっている
  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    dp[2] = dp[1]+3 = 3
    dp = [0, 1, 3, 0, 0, 0, 0]
  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [7, 8, 15]

4回目のループ（(3, 15), (4, 7), (5, 8), (7, 14)について考える）

  1. 現在の区間(7, 14)の開始点以下の右端値の数[7, 8, 15]を二分探索で求める。
    7以下が存在するインデックスは0
  2. 現在の区間と重なる前の区間の数を計算する。
    count = 3-0 = 3 -> (3, 15), (4, 7), (5, 8), (7, 14)は区間が重なっている
  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    dp[3] = dp[2]+3 = 6
    dp = [0, 1, 3, 6, 0, 0, 0]
  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [7, 8, 14, 15]

5回目のループ（(3, 15), (4, 7), (5, 8), (7, 14), (8, 11)について考える）

  1. 現在の区間(8, 11)の開始点以下の右端値の数[7, 8, 14, 15]を二分探索で求める。
    8以下が存在するインデックスは1
  2. 現在の区間と重なる前の区間の数を計算する。
    count = 4-1 = 3
    -> (3, 15), (4, 7), (5, 8), (7, 14), (8, 11)のうち、(4, 7), (8, 11)は重なっていないので減算
  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    dp[4] = dp[3]+3 = 9
    dp = [0, 1, 3, 6, 9, 0, 0]
  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [7, 8, 11, 14, 15]

6回目のループ（(3, 15), (4, 7), (5, 8), (7, 14), (8, 11), (8, 13)について考える）

  1. 現在の区間(8, 13)の開始点以下の右端値の数[7, 8, 11, 14, 15]を二分探索で求める。
    8以下が存在するインデックスは1
  2. 現在の区間と重なる前の区間の数を計算する。
    count = 5-1 = 4
    -> (3, 15), (4, 7), (5, 8), (7, 14), (8, 11), (8, 13)のうち、前のループで検出した重なっていない区間に加え、(4, 7), (8, 13)が重なっていないので減算
  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    dp[5] = dp[4]+4 = 13
    dp = [0, 1, 3, 6, 9, 13, 0]
  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [7, 8, 11, 13, 14, 15]

7回目のループ（(3, 15), (4, 7), (5, 8), (7, 14), (8, 11), (8, 13), (12, 14)について考える）

  1. 現在の区間(8, 13)の開始点以下の右端値の数[7, 8, 11, 13, 14, 15]を二分探索で求める。
    12以下が存在するインデックスは3

  2. 現在の区間と重なる前の区間の数を計算する。
    count = 6-3 = 3
    -> (3, 15), (4, 7), (5, 8), (7, 14), (8, 11), (8, 13), (12, 14)のうち、前のループで検出した重なっていない区間に加え、(4, 7), (12, 14) / (5, 8), (12, 14) / (8, 11), (12, 14) が重なっていないので減算

  3. DPテーブルを更新する（前の状態に新たに重なった区間の数を加える）。
    dp[6] = dp[5]+3 = 16
    dp = [0, 1, 3, 6, 9, 13, 16]

  4. 現在の区間の右端値をSortedListに追加する。
    end_sec = [7, 8, 11, 13, 14, 14, 15]

  5. DPテーブルの最後の要素（総ペア数）を出力する。
    ans = 16

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?