これはインタラクティブな問題です。
集合 $D$ において、以下の性質を満たす等価関係 $=$ が定義されています。
- 反射律：$\forall a \in D$ に対して $a = a$。
- 推移律：$\forall a, b, c \in D$ に対して、$a = b$ かつ $b = c$ ならば $a = c$。
- 対称律：$\forall a, b \in D$ に対して、$a = b$ ならば $b = a$。
集合 $D$ において、以下の性質を満たす全順序関係 $\leq$ が定義されています。
- 完全律：$\forall a, b \in D$ に対して、$a \le b$ または $b \le a$。
- 推移律：$\forall a, b, c \in D$ に対して、$a \le b$ かつ $b \le c$ ならば $a \le c$。
- 反対称律：$\forall a, b \in D$ に対して、$a \le b$ かつ $b \le a$ ならば $a = b$。
全順序関係 $\leq$ に関連する狭義全順序関係 $<$ は以下を満たします。
- $\forall a, b \in D$ に対して、$a < b$ は $a \le b$ かつ $a \ne b$ と同値。
$D$ の要素からなる多重集合 $S$ の最頻値（厳密な最頻値）とは、その出現回数が集合のサイズの半分を厳密に超える要素のこととします。すなわち、$x$ が最頻値であるための必要十分条件は以下です。 $$\displaystyle \sum_{e \in S} [e = x] > \frac{1}{2}|S|$$
あなたは $D$ の要素からなる多重集合 $S$（初期状態は空集合 $\varnothing$）をオンラインで管理し、以下の操作をサポートする必要があります。
- 挿入：要素 $x \in D$ が与えられ、多重集合 $S$ に $x$ を追加する。
- 削除：要素 $x \in D$ が与えられ、多重集合 $S$ から $x$ を削除する。$x \in S$ であることが保証される。特に、$x$ が $S$ に複数回出現する場合、ちょうど $1$ 回分のみを削除する。
各操作の後、集合 $S$ に最頻値が存在するかを報告してください。存在する場合は、その最頻値を答えてください。
インタラクティブライブラリに対して以下の問い合わせを行うことができます。
- 等価テスト $\mathbf{E}$：要素 $x, y \in D$ を与えると、インタラクティブライブラリは $x = y$ かどうかを返す。
- 順序テスト $\mathbf{C}$：要素 $x, y \in D$ を与えると、インタラクティブライブラリは $x \le y$ かどうかを返す。
各サブタスクにおいて、各テストの回数には制限があります。あなたのスコアは、回答の正確さと、各操作後に行う各問い合わせの回数によって決まります。
実装の詳細
これはインタラクティブな問題であり、C++ 言語のみをサポートしています。
main() 関数を実装する必要はなく、標準入出力やファイルからデータを読み書きしてはいけません。
ヘッダーファイル majority.h をインクルードしてください。
ヘッダーファイルには、データ型 D_t が定義されており、これは $D$ の要素を表します。
インタラクティブライブラリは D_t に対して以下の演算子をオーバーロードしており、前述の二項関係を表します。
- 演算子
<=は二項関係 $\le$ を表し、インターフェースは以下の通りです。
bool operator<= (const D_t &rhs) const;D_t 型の変数 x と y（それぞれ $x, y \in D$ に対応）に対して、x <= y は $x \le y$ ならば true を、そうでなければ false を返します。
演算子 <= を呼び出すと、$1$ 単位の $\mathbf{C}$-コストが発生します。
- 演算子
==は二項関係 $=$ を表し、インターフェースは以下の通りです。
bool operator== (const D_t &rhs) const;D_t 型の変数 x と y（それぞれ $x, y \in D$ に対応）に対して、x == y は $x = y$ ならば true を、そうでなければ false を返します。
演算子 == を呼び出すと、$1$ 単位の $\mathbf{E}$-コストが発生します。
さらに、実装の便宜上、以下の演算子もオーバーロードされています。
a > bは!(a <= b)と同値。この演算子の呼び出しは $1$ 単位の $\mathbf{C}$-コストが発生します。a < bは!(b <= a)と同値。この演算子の呼び出しは $1$ 単位の $\mathbf{C}$-コストが発生します。a >= bはb <= aと同値。この演算子の呼び出しは $1$ 単位の $\mathbf{C}$-コストが発生します。a != bは!(a == b)と同値。この演算子の呼び出しは $1$単位の $\mathbf{E}$-コストが発生します。
デバッグの便宜上、関数 get_value() も提供されています。この関数を呼び出すと、クラス D_t のメンバ変数 info が返されます。このメソッドはサンプルインタラクティブライブラリにのみ含まれており、アルゴリズムのデバッグ用です。評価時には、いかなる手段を用いても変数 info の値を取得してはならず、取得した場合はインタラクティブライブラリへの攻撃とみなされ、スコアは無効となります。
以下の関数を実装する必要があります。
bool insert(const D_t& x);- インタラクティブライブラリが挿入操作を開始したことを表します。
- 操作完了後に集合に最頻値が存在するかどうかを
bool型で返してください。 - 特に、戻り値が
trueの場合、submit関数を呼び出して最頻値を提出する必要があります。詳細は後述のsubmit関数の説明を参照してください。
bool erase(int id);- インタラクティブライブラリが削除操作を開始したことを表します。
- 変数
idは、今回削除される要素が何回目の挿入操作で挿入されたものかを表します。 id回目の挿入操作で挿入された要素は、それ以前に削除されていないことが保証されます。
- 変数
- 操作完了後に集合に最頻値が存在するかどうかを
bool型で返してください。 - 特に、戻り値が
trueの場合、submit関数を呼び出して最頻値を提出する必要があります。詳細は後述のsubmit関数の説明を参照してください。
特に、インタラクティブライブラリは回答を提出するための submit 関数を提供しています。
void submit(const D_t& x);- 操作後に集合に最頻値が存在する場合、この関数をちょうど $1$ 回呼び出す必要があります。引数
xは $S$ 内の最頻値を表します。 - 操作後に集合に最頻値が存在しない場合、この関数を呼び出してはいけません。
関数 subtask_id() は、そのテストケースのサブタスク番号を返します。サンプルインタラクティブライブラリでは、この関数は常に $0$ を返します。
int subtask_id();【小課題】セクションに記載されている採点方法に注意してください。特に、insert および erase の呼び出しにおいて：
- 最頻値の存在を正しく返したが、
submitで提出しなかった、あるいは誤った値を提出した場合。 - 可能な候補解を提示したが、最頻値が存在するかの判定が正しくなかった場合。
これらは部分点となります。（訳注：これらの用語の定義も下にあります。）
サンプルインタラクティブライブラリ
配布ファイルにはサンプルインタラクティブライブラリ grader_majority.cpp が含まれており、これを使用してプログラムを作成できます。
実際のテストで使用されるインタラクティブライブラリはサンプルとは異なるため、その実装に依存してはいけません。
以下のコマンドを使用して、プログラム majority.cpp を実行ファイル majority にコンパイルできます。
g++ majority.cpp grader_majority.cpp -o majority -O2 -std=c++14
最終テストで使用されるインタラクティブライブラリの実装はサンプルとは異なるため、サンプルライブラリの実装に依存してはいけません。
入力
サンプルインタラクティブライブラリは標準入力から以下の形式でデータを読み取ります。
入力の最初の行には、クエリの数 $Q$ が含まれます。
続く $Q$ 行には、各操作を表す $2$ つの整数 $\mathrm{op}~ x$ が含まれます。
- $\mathrm{op} = 0$ の場合、挿入操作を表し、挿入される要素は $x$ です。
- $\mathrm{op} = 1$ の場合、削除操作を表し、削除される要素は $x$ 回目の操作で挿入された要素です。
$\mathrm{op} \in \{0, 1\}$、$0 \le x \le 10^5$ であることが保証されます。挿入操作のデータを読み込む際、各 D_t 型の変数は非負整数で表されます。コンストラクタ D_t(x) を使用して、32ビット符号なし整数 x を対応する D_t 型の変数に変換できます。
出力
サンプルインタラクティブライブラリは標準出力に以下の形式で出力します。
- 出力の最初の行には、インタラクションプロセスの情報が含まれます。（訳注：この行がない場合もあります。）
- 続く $Q$ 行には、それぞれ $2$ つの整数が含まれます。
- 最初の整数は $\{ 0, 1 \}$ のいずれかで、呼び出しの戻り値を表します。$0$ は
false、$1$ はtrueを表します。 - $2$ 番目の整数は、提出した回答に対応する
infoの値です。この操作後に回答を提出しなかった場合、値は $-1$ となります。
- 最初の整数は $\{ 0, 1 \}$ のいずれかで、呼び出しの戻り値を表します。$0$ は
入出力例
入出力例 1
以下の入力を考えます。
5
0 1
0 1
0 2
0 2
1 2期待される出力の一例は以下の通りです。
1 1
1 1
1 1
0 -1
1 2操作 1 のパラメータ $x$ は、要素 $x$ を削除するのではなく、$x$ 回目の挿入操作で挿入された要素を削除することを意味することに注意してください。
入出力例 2
以下の入力を考えます。
13
0 1
0 2
0 3
0 1
0 1
1 4
1 5
0 2
0 2
1 6
1 7
0 3
0 3期待される出力の一例は以下の通りです。
1 1
0 -1
0 -1
0 -1
1 1
0 -1
0 -1
0 -1
1 2
0 -1
0 -1
0 -1
1 3小課題
$Q$ をテストケースにおけるクエリの数とします。
| 小課題番号 | $Q$ | 採点方式 | 点数 |
|---|---|---|---|
| $1$ | $\le 100$ | A | $2$ |
| $2$ | $\le 5\,000$ | $6$ | |
| $3$ | $\le 50\,000$ | $18$ | |
| $4$ | $\le 10^5$ | B | $74$ |
採点方式に関する説明は以下の通りです。
- $C$ を各クエリにおける $\mathbf{C}$-コストの最大値とします。
- $E$ を各クエリにおける $\mathbf{E}$-コストの最大値とします。
- $\max(C, E) \ge 1000$ の場合、採点方式に関わらずスコアは $0$ 点です。
- 採点方式 A：
- 各呼び出しにおいて最頻値の存在を正しく回答した場合、$50\%$ のスコアを得ます。
- 各呼び出しにおいて可能な候補解を提示した場合、$50\%$ のスコアを得ます。
- 最終スコアはこれら $2$ つの合計です。
- インタラクティブライブラリは、スコアを獲得可能な（$\max(C, E) \le 1\,000$ を満たす）任意のインタラクションにおいて、ライブラリの実行時間が $200$ ミリ秒以内、メモリ使用量が $16$ MB 以内であることを保証します。
- 採点方式 B：
- 採点パラメータ $p \in (0, 1)$ を設定します。
- 各呼び出しにおいて最頻値の存在を正しく回答し、かつ可能な候補解を提示した場合、$p = 100\%$。
- 各呼び出しにおいて最頻値の存在を正しく回答した場合、$p = 10\%$。
- 各呼び出しにおいて可能な候補解を提示した場合、$p = 10\%$。
- それ以外の場合、$p = 0$。
- $C > 500$ の場合、スコアは $4 \cdot p$。
- そうでなく $C > 20$ の場合、スコアは $9 \cdot p$。
- そうでなく $C > 0$ の場合、スコアは $15 \cdot p$。
- そうでなく $E > 800$ の場合、スコアは $18 \cdot p$。
- そうでなく $E > 100$ の場合、スコアは $\displaystyle \left(20 + 2 \times \frac{800-E}{100}\right) \cdot p$。
- そうでなく $E > 10$ の場合、スコアは $\displaystyle \left(35 + 2 \times \frac{100-E}{10}\right) \cdot p$。
- そうでなく $E > 5$ の場合、スコアは $(64 - E) \cdot p$。
- そうでなく $E = 5$ の場合、スコアは $60 \cdot p$。
- そうでなく $E = 4$ の場合、スコアは $64 \cdot p$。
- そうでなく $E = 3$ の場合、スコアは $69 \cdot p$。
- そうでない場合、スコアは $74 \cdot p$。
- 採点パラメータ $p \in (0, 1)$ を設定します。
最頻値の存在を正しく回答したとは：- 最頻値が存在するときに
trueを返すこと。 - 最頻値が存在しないときに
falseを返すこと。 submitを呼び出したか、報告した解が正しいかは影響しません。自由に提出しても、提出しなくても構いません。
- 最頻値が存在するときに
可能な候補解を提示したとは：- 最頻値が存在するときに
submitをちょうど $1$ 回呼び出し、報告した解が唯一の最頻値であること。 - 最頻値が存在しない場合、
submitを呼び出したか、どのような解を提示したかは影響しません。 - 関数の戻り値は影響せず、自由に
trueまたはfalseを返せます。
- 最頻値が存在するときに
つまり、すべてのクエリに完全に正しく回答し、かつ $E \le \mathbf{2}$ かつ $C = \mathbf{0}$ を満たす場合、満点を得ることができます。
ヒント
入力データは $0 \le x \le 10^5$ を保証しているため、D_t(-1)、D_t(-2)、…… を使用して、すべての挿入された要素と等しくないオブジェクトを生成できます。