https://www.codechef.com/COOK88/problems/ONCHESS
N人のプレイヤーが順番に待ち行列に入る。
i番目のプレイヤーは
- レートがR[i]
- 対戦相手のレートはMin[i]～Max[i]を希望
- 対戦時間はT[i]を希望
- レート変化はisRated[i]を希望
- 色はColor[i]を希望
というパラメタを持っている。
i番目のプレイヤーが待ち行列に入った時に以下の条件を満たし、待ち行列のより先頭にいるプレイヤーとマッチングさせる。
満たすプレイヤーがいれば、そのプレイヤーの番号を出力する。
満たすプレイヤーがいないなら、"Wait"と出力して待ち行列に追加する。
なお、マッチングされた側のプレイヤーも待ち行列から取り除かれる。
- 互いのレート希望があっている
- 希望対戦時間が等しい
- 希望レート変化が等しい
- 色は以下のいずれかを満たせば良い
- 互いに"random"である
- 片方が"white"でもう片方が"black"
解法
英語が読めるかどうかの問題。
待ち行列を用意して、各プレイヤーに対して条件を満たすプレイヤーを探してくればいい。
待ち行列から削除するのは大変なので、「done[i] := i番目のキャラクターが取り除かれたか」のフラグを用いると良い。
int N, R[101], Min[101], Max[101], Time[101]; string isRated[101], Color[101]; int done[101]; //--------------------------------------------------------------------------------------------------- void solve() { cin >> N; rep(i, 0, N) done[i] = 0; rep(i, 0, N) cin >> R[i] >> Min[i] >> Max[i] >> Time[i] >> isRated[i] >> Color[i]; rep(i, 0, N) { string ans = "wait"; rep(j, 0, i) if(!done[j]) { if (Time[i] == Time[j] and isRated[i] == isRated[j]) if (Min[i] <= R[j] and R[j] <= Max[i]) if (Min[j] <= R[i] and R[i] <= Max[j]) if ((Color[i] == "random" and Color[j] == "random") or (Color[i] == "black" and Color[j] == "white") or (Color[i] == "white" and Color[j] == "black")) { done[i] = done[j] = 1; ans = to_string(j + 1); break; } } printf("%s\n", ans.c_str()); } } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) solve(); }
