コンテンツにスキップ

シミュレーション

タグ「シミュレーション」の記事 4 件

競プロキャンプ2026関西 E - Join Wars

NN 人のプレイヤーと MM 個のインスタンスがあり、インスタンス ii の定員は AiA_i です。満員のインスタンスに入ろうとしたプレイヤーは、そのインスタンスの待機列の最後尾に並びます。次の 2 種類のクエリを合わせて QQ 個処理する問題です(1≤N,M,Q≤5×1051 \le N, M, Q \le 5 \times 10^5)。

  • 1 x y:プレイヤー xx が今の居場所を離れ、インスタンス yy に入ろうとする。インスタンスから退出した場合は、そのインスタンスの待機列の先頭のプレイヤーが入場する。待機列に並んでいた場合は、列から外れる。
  • 2 z:プレイヤー zz がインスタンス pp に入場していれば 1 p、インスタンス pp の待機列に並んでいれば 2 p、どちらでもなければ -1 を出力する。

インスタンスごとに、入場しているプレイヤーの集合と、待機列を管理して、書かれているとおりにシミュレーションします。

待機列では、先頭(最も早く並んだプレイヤー)を取り出す操作のほかに、途中のプレイヤーが抜ける操作があります。そのため、通常のキューではなく、(並んだ時刻, プレイヤー) の組を入れた順序付き集合(C++ の std::set)で管理します。集合の最小の要素が待機列の先頭です。

クエリ 1 では、まずプレイヤー xx を今いる場所から取り除きます。インスタンスから退出した場合は、空いた枠に待機列の先頭を入場させます。続けて、xx をインスタンス yy の待機列の最後尾に入れてから、定員に空きがある間は待機列の先頭を入場させます。yy に空きがあれば、待機列は空のはずなので、xx がそのまま入場することになります。

各プレイヤーについて、今いるインスタンスの番号と、並んだ時刻を記録しておきます。こうすると、集合から取り除くときの要素も、クエリ 2 で待機列にいるかどうかも、O(log⁡N)O(\log N) で分かります。全体の計算量は O(M+Qlog⁡N)O(M + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, Q);
VL(A, M);
vec<set<pl>> room(M), que(M);
vl idx(N, -1);
vl tm(N, -1);
rep(i, Q) {
LL(q);
if (q == 1) {
LL(x, y);
x--, y--;
ll &z = idx[x];
if (z >= 0) {
if (room[z].contains({tm[x], x})) {
room[z].erase({tm[x], x});
while (len(room[z]) < A[z] && len(que[z])) {
room[z].insert(que[z].extract(min(que[z])));
}
} else {
que[z].erase({tm[x], x});
}
}
tm[x] = i;
z = y;
que[z].insert({i, x});
while (len(room[z]) < A[z] && len(que[z])) {
room[z].insert(que[z].extract(min(que[z])));
}
} else {
LL(z);
z--;
if (idx[z] >= 0) {
print(1 + que[idx[z]].contains({tm[z], z}), idx[z] + 1);
} else {
print(-1);
}
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

room[z] がインスタンス z に入場しているプレイヤーの集合、que[z] が待機列です。どちらも要素は (インスタンス z に入ろうとしたクエリの番号, プレイヤー) の組です。idx[x] はプレイヤー x がいるインスタンス(どこにもいなければ −1-1)、tm[x] は最後にクエリ 1 で動いたときのクエリの番号です。z は idx[x] への参照なので、z = y で idx[x] が更新されます。

min(que[z]) は待機列の先頭の要素で、extract で que[z] から取り出し、そのまま room[z] に入れています。クエリ 2 では、que[idx[z]] に入っていれば待機列、そうでなければ入場中です。

使用ライブラリ:cpp_include@9c33ee7

DOJ Beginner Contest 7 B - tourist vs rainboy

NN 問の問題が難しさの昇順に並んでいて、ii 番目の問題を解くには時間 AiA_i がかかります(A1≤A2≤⋯≤ANA_1 \le A_2 \le \dots \le A_N)。

tourist と rainboy は時刻 00 に解き始め、休まずに 1 問ずつ解いていきます。各問題を解き終えた時刻の和がペナルティです。tourist は 1,2,…,N1, 2, \dots, N 番の順に、rainboy は N,N−1,…,1N, N - 1, \dots, 1 番の順に解きます。rainboy のペナルティから tourist のペナルティを引いた値を求める問題です。

解く順に AA を並べたとき、kk 問目を解き終える時刻は、最初の kk 問にかかる時間の和(累積和)です。ペナルティはその累積和を全部足したものです。

  • tourist のペナルティは、AA を前から足していったときの累積和の合計です。
  • rainboy のペナルティは、AA を後ろから足していったときの累積和の合計です。

それぞれを O(N)O(N) で計算し、差をとります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 0
x = 0
for a in A:
x += a
ans -= x
x = 0
for a in reversed(A):
x += a
ans += x
print(ans)

x が今の累積和(解き終えた時刻)です。前から足すときは ans から引き、後ろから足すときは ans に加えることで、差を直接求めています。

DOJ Beginner Contest 9 B - Rating Updates

最初のレーティングは R0R_0 です。NN 個のコンテストに順に参加し、ii 番目のパフォーマンスが PiP_i のとき、レーティングは

Ri=3Ri−1+Pi4R_i = \frac{3 R_{i-1} + P_i}{4}

に更新されます。最終的なレーティング RNR_N を求める問題です。どの RiR_i も正の整数になることが保証されています。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

式のとおりに RR を NN 回更新します。計算量はテストケース全体で O(∑N)O(\sum N) です。

RiR_i が整数になることが保証されているので、3Ri−1+Pi3 R_{i-1} + P_i は必ず 44 で割り切れます。そのため、整数の割り算 // で正確に計算できます。

Python
for _ in range(int(input())):
N, R = map(int, input().split())
P = list(map(int, input().split()))
for p in P:
R = (3 * R + p) // 4
print(R)

Codeforces Round 1125 (Div. 3) B - Did Not Go to Print

文書 1,…,n1, \dots, n と、最初は空のプリンターのメモリがあります。ii 番目の操作 sis_i は次のいずれかです。

  • 1:文書 ii をメモリの一番上に積む
  • 2:メモリが空でなければ、一番上の文書を印刷してメモリから取り除く。空なら文書 ii を印刷する
  • 3:文書 ii を印刷する

すべての操作のあとで、一度も印刷されなかった文書の番号を昇順に出力してください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

メモリは「最後に積んだものから取り出す」ので、スタックそのものです。操作を順にシミュレーションして、印刷された文書を記録すれば、残りが答えです。

  • 1:スタックに ii を push する
  • 2:スタックが空でなければ pop した文書を、空なら ii を印刷済みにする
  • 3:ii を印刷済みにする

なお、2 でスタックが空でないときは、文書 ii 自身は印刷されません。2 の操作では文書 ii はメモリにも入らないので、その文書が印刷されることはもうありません。

各操作は O(1)O(1) なので、全体で O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
t = []
l = []
for i, c in enumerate(S):
if c == "1":
l.append(i)
elif c == "2":
if l:
t.append(l.pop())
else:
t.append(i)
else:
t.append(i)
ans = set(range(N)) - set(t)
print(len(ans))
print(*[i + 1 for i in sorted(ans)])

l がメモリのスタック、t が印刷された文書のリストです。文書番号は 0 始まりで持っておき、出力するときに 1 を足しています。k=0k = 0 のときは print(*[]) が空行を出力するので、そのままで大丈夫です。