D - 病院の受付窓口 / Hospital Reception Window Editorial by admin
gemini-3.5-flash-thinking概要
この問題は、患者の待ち行列に対して「末尾への追加」「指定位置への割り込み（挿入）」「先頭の取り出し（削除）」を高速に行う問題です。
行列の要素数が多くなるため、通常の配列（リスト）をそのまま使うと時間切れ（TLE）になってしまいます。そこで、データをいくつかの塊（ブロック）に分割して管理する「平方分割（バケット分割）」というテクニックを用いて、すべての操作を高速に処理します。
考察
素朴なアプローチとその限界
Pythonの通常のリスト queue を使って、愚直に操作をシミュレーションすることを考えてみます。
- 操作 1（末尾追加）: queue.append(x) \(\rightarrow\) \(O(1)\) 時間で高速。
- 操作 2（指定位置挿入）: queue.insert(k - 1, x) \(\rightarrow\) 挿入位置より後ろの要素をすべて後ろにずらす必要があるため、最悪 \(O(N)\) 時間。
- 操作 3（先頭削除）: queue.pop(0) \(\rightarrow\) 残ったすべての要素を前にずらす必要があるため、最悪 \(O(N)\) 時間。
最悪の場合、1回の操作に \(O(N)\) 時間がかかります。クエリの個数 \(Q\) は最大で \(2 \times 10^5\) なので、全体での計算量は最悪 \(O(Q^2)\) となり、実行時間制限に間に合いません。
高速化のアイデア：平方分割
要素の「ずらし」にかかるコストを減らすために、待ち行列をいくつかの小さなブロックに分割して管理します。
例えば、全体で \(9\) 個の要素があるとき、サイズ \(3\) のブロック \(3\) つに分割して管理します。
[1, 2, 3, 4, 5, 6, 7, 8, 9] \(\rightarrow\) [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
このようにすると、 1. 位置の特定: 各ブロックの要素数を足し合わせることで、目的の \(k\) 番目の要素が「何番目のブロックの、何番目の位置にあるか」を高速に特定できます。 2. 挿入・削除: 特定した1つのブロック内だけで要素の挿入・削除を行います。ずらす必要があるのはそのブロック内の要素だけ（高々ブロックのサイズ分）なので、非常に高速になります。
アルゴリズム
各ブロックの最大サイズを \(B \approx 1000\) 程度に設定します。
1. データの管理方法
blocks: 各ブロックの要素（患者番号）を格納する2次元リスト。初期状態は[[]]。sizes: 各ブロックの要素数を格納するリスト。初期状態は[0]。
2. 操作 1 : 末尾に患者 \(x\) を追加
- 最後のブロック
blocks[-1]の末尾に \(x\) を追加し、sizes[-1]を \(1\) 増やします。 - もし最後のブロックのサイズが制限（
LIMIT = 1000）を超えた場合、ブロックを半分に分割します。- 後半半分の要素を新しいブロックとして、
blocksとsizesの末尾に追加します。
- 後半半分の要素を新しいブロックとして、
3. 操作 2 : 先頭から \(k\) 番目に患者 \(x\) を挿入
sizesを先頭から順に累積していき、累計が \(k\) 以上になる最初のブロックのインデックスidxを探します。- そのブロック内での相対的な挿入位置
posを計算します。 blocks[idx]のpos番目に \(x\) を挿入し、sizes[idx]を \(1\) 増やします。- もし挿入後のブロックのサイズが
LIMITを超えた場合、ブロックを半分に分割します。- 後半半分の要素を新しいブロックとして、
idx + 1の位置に挿入（insert）します。
- 後半半分の要素を新しいブロックとして、
4. 操作 3 : 先頭の患者を対応（削除）
- 先頭のブロック
blocks[0]の先頭要素をpop(0)で取り出して出力用リストに格納し、sizes[0]を \(1\) 減らします。 - もし先頭のブロックが空（
sizes[0] == 0）になり、かつ他にもブロックが存在する場合は、空になった先頭のブロックをblocksとsizesから削除（pop(0)）します。
計算量
ブロックの最大サイズを \(B\) とします（実装では \(B = 1000\)）。全体の要素数を \(N\)（最大 \(Q\)）とすると、ブロックの個数は最大で \(O(N/B)\) 個になります。
時間計算量:
- 操作 1: ブロックの末尾追加は \(O(1)\)。分割が発生した場合は \(O(B)\)。
- 操作 2: 挿入するブロックの探索に \(O(N/B)\)、ブロック内への挿入に \(O(B)\)、分割が発生した場合に \(O(B)\)。よって \(O(N/B + B)\)。
- 操作 3: 先頭ブロックからの削除は \(O(B)\)。先頭ブロックの削除が発生した場合は \(O(N/B)\)。よって \(O(N/B + B)\)。
- \(B \approx \sqrt{Q}\) と設定することで、1クエリあたりの計算量は最悪でも \(O(\sqrt{Q})\) となります。
- 全クエリを通じた最悪時間計算量は \(O(Q \sqrt{Q})\) です。\(Q = 2 \times 10^5\) のとき、Pythonの高速なリスト操作も相まって、制限時間内に余裕で間に合います。
空間計算量:
- 待ち行列に存在する要素を分散して保持するため、\(O(Q)\) です。
実装のポイント
ブロックの分割（スプリット）: 要素の挿入を繰り返すと、特定のブロックだけが極端に長くなってしまい、そのブロック内での挿入・削除に時間がかかるようになってしまいます。サイズが
LIMITを超えたときに半分に分割することで、常に各ブロックのサイズを \(O(B)\) 以下に保ち、最悪計算量を保証しています。高速な入出力: Pythonで大量の入出力を扱うため、
sys.stdin.readlineとsys.stdout.writeを使用して入出力のボトルネックを防いでいます。ソースコード
import sys
def solve():
input = sys.stdin.readline
Q = int(input())
LIMIT = 1000
blocks = [[]]
sizes = [0]
out = []
for _ in range(Q):
query = input().split()
t = query[0]
if t == '1':
x = int(query[1])
blocks[-1].append(x)
sizes[-1] += 1
if sizes[-1] > LIMIT:
half = LIMIT // 2
new_block = blocks[-1][half:]
blocks[-1] = blocks[-1][:half]
sizes[-1] = half
blocks.append(new_block)
sizes.append(len(new_block))
elif t == '2':
x = int(query[1])
k = int(query[2]) - 1
idx = 0
curr_size = 0
n_blocks = len(sizes)
while idx < n_blocks:
if curr_size + sizes[idx] >= k:
break
curr_size += sizes[idx]
idx += 1
else:
idx = n_blocks - 1
curr_size -= sizes[-1]
pos = k - curr_size
blocks[idx].insert(pos, x)
sizes[idx] += 1
if sizes[idx] > LIMIT:
half = LIMIT // 2
new_block = blocks[idx][half:]
blocks[idx] = blocks[idx][:half]
sizes[idx] = half
blocks.insert(idx + 1, new_block)
sizes.insert(idx + 1, len(new_block))
else:
val = blocks[0].pop(0)
sizes[0] -= 1
if sizes[0] == 0 and len(sizes) > 1:
blocks.pop(0)
sizes.pop(0)
out.append(str(val))
sys.stdout.write('\n'.join(out) + '\n')
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。