insects
IOI 2022 Day 2 Tasks
Japanese (JPN)

最も珍しい昆⾍

Pak Blangkon の家の周りでは，0 から N − 1 までの番号が付けられた N 匹の昆⾍が⾛り回っている．
それぞれの昆⾍には，0 以上 109 以下の整数で表される 種類 が決まっている．2 匹以上の昆⾍が同じ種類であるかもしれない．
昆⾍たちを種類でグループ分けすることを考える．最も頻出の種類の出現頻度を，最も昆⾍の数が多いグループにおける昆⾍の数と定義する．同様に，最も珍しい種類の出現頻度を，最も昆⾍の数が少ないグループにおける昆⾍の数と定義する．
例えば，種類の値が [5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9] である 11 匹の昆⾍がいる場合を考える．この場
合，最も頻出の種類の出現頻度は 3 である．最も頻出の種類は，共に 3 匹の昆⾍が含まれる種類 9 と種類 11 である． 最も珍しい種類の出現頻度は 1 である．最も珍しい種類は，それぞれ 1 匹の昆⾍のみが含まれる種類 7，種類 0，および種類 100 である．
Pak Blangkon はどの昆⾍の種類も知らない．彼は，昆⾍の種類についての情報を与えてくれる機械を持っていて，その機械には1 つのボタンがついている．最初機械は空である．機械を使うために 3 種類の操作をすることができる:
1. 昆⾍を 1 匹機械の中に⼊れる．
2. 昆⾍を 1 匹機械から取り出す．
3. 機械についているボタンを押す．
3 種類の操作はそれぞれ 40 000 回まで⾏うことができる．
ボタンを押すと機械は，機械の中にいる昆⾍のみを考えた時の最も頻出の種類の出現頻度を報告する．
あなたの課題は，機械を使うことで，Pak Blangkon の家にいる N 匹全ての昆⾍の中での最も珍しい種類の出現頻度を求めることである．いくつかの⼩課題では，あなたの得点は各種類の操作を⾏った回数の最⼤値に依存する．(詳細は⼩課題の項を参照．)

実装上の注意あなたは次の関数を実装する必要がある:
int min_cardinality(int N)N: 昆⾍の数
insects (1 of 4)

この関数は，Pak Blangkon の家にいる N 匹全ての昆⾍の中での最も珍しい種類の出現頻度を返さなければならない．
この関数はちょうど 1 回呼び出される．
上の関数は以下の関数を呼び出すことができる．
void move_inside(int i): 機械の中に⼊れる昆⾍の番号．i は 0 以上 N − 1 以下でなければならない．
もし指定した昆⾍が既に機械の中にいる場合，この呼び出しは効果を持たないが，依然として 1回の呼び出しとみなされる．
この関数は 40 000 回まで呼び出すことができる．
ivoid move_outside(int i): 機械から取り出す昆⾍の番号．i は 0 以上 N − 1 以下でなければならない．
もし指定した昆⾍が既に機械の外にいる場合，この呼び出しは効果を持たないが，依然として 1回の呼び出しとみなされる．
この関数は 40 000 回まで呼び出すことができる．
iint press_button()

この関数は，機械の中にいる昆⾍のみを考えた時の最も頻出の種類の出現頻度を報告する．
この関数は 40 000 回まで呼び出すことができる．
採点プログラムは適応的ではない．すなわち，min_cardinality が呼び出される前にN 匹すべての種類は決定されている．

⼊出⼒例

種 類 の 値 が そ れ ぞ れ [5, 8, 9, 5, 9, 9] で あ る よ う な 6 匹 の 昆 ⾍ が い る 状 況 を 考 え る ． 関 数
min_cardinality は次のように呼び出される．
min_cardinality(6)この関数は move_inside，move_outside，press_button を次のように呼び出すことができる．

insects (2 of 4)

呼び出し

戻り値 機械の中の昆⾍ 機械の中の昆⾍の種類
{}

[]{0}

[5]{0}[5]{0, 1}[5, 8]{0, 1}[5, 8]{0, 1, 3}[5, 8, 5]{0, 1, 3}[5, 8, 5]

move_inside(2){0, 1, 2, 3}[5, 8, 9, 5]

move_inside(4){0, 1, 2, 3, 4}[5, 8, 9, 5, 9]

move_inside(5){0, 1, 2, 3, 4, 5}[5, 8, 9, 5, 9, 9]{0, 1, 2, 3, 4, 5}[5, 8, 9, 5, 9, 9]{0, 1, 2, 3, 4, 5}[5, 8, 9, 5, 9, 9]{0, 1, 2, 3, 4, 5}[5, 8, 9, 5, 9, 9]{0, 1, 2, 3, 4}[5, 8, 9, 5, 9]{0, 1, 2, 3, 4}[5, 8, 9, 5, 9]

move_inside(0)press_button()1

move_inside(1)press_button()1

move_inside(3)press_button()press_button()2

3

move_inside(5)press_button()3

move_outside(5)press_button()2

この時点で，最も珍しい種類の出現頻度は 1 であると結論づけるのに⼗分な情報が得られている． 従って，関数 min_cardinality は 1 を返さなければならない．
この例では，move_inside は 7 回，move_outside は 1 回，そして press_button は 6 回呼び出されている．

制約2 ≦ N ≦ 2000

⼩課題

1. (10 点) N ≦ 200
2. (15 点) N ≦ 1000
3. (75 点) 追加の制約はない．
いずれかのテストケースで，move_inside，move_outside，もしくは press_button への呼び出
しが実装上の注意の項にある制約を満たさなかった場合，または min_cardinality の戻り値が正しくない場合，その⼩課題におけるあなたの得点は 0 となる．
insects (3 of 4)

を，次の 3 つの値の最⼤値とする: move_inside の呼び出し回数，move_outside の呼び出し回数，press_button の呼び出し回数
⼩課題 3 では部分点を得ることができる． m を，⼩課題中のすべてのテストケースについての Nq の最⼤値とする． この⼩課題におけるあなたの得点は次の表に従って計算される．
q

条件
20 < m得点0(CMS 上では "Output isn’t correct" と表⽰される)

6 < m ≦ 20225
m−23<m≦681 − 23 m2m≦375

採点プログラムのサンプルを，T [i] が i 番⽬の昆⾍の種類であるような配列とする．
採点プログラムのサンプルは，以下の形式で⼊⼒を読み込む．
1 ⾏⽬: N
2 ⾏⽬: T [0] T [1] … T [N − 1]
採点プログラムのサンプルがプロトコル違反を検出した場合，採点プログラムのサンプルの出⼒はProtocol Violation: <MSG> となる．<MSG> は次のいずれかである．
invalid parameter: move_inside または move_outside の呼び出しにおいて i が 0 以上
N − 1 以下でない．
too many calls: move_inside，move_outside，press_button のいずれかへの呼び出し
回数が 40 000 を超えている.
その他の場合，採点プログラムのサンプルの出⼒は以下の形式である．
1 ⾏⽬: min_cardinality の戻り値
2 ⾏⽬: qTinsects (4 of 4)