ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 170 E - Smart Infants

お題箱より。実装方法に関するリクエストだったので実装中心で書きます。

E - Smart Infants

解法

解法としてはシミュレーションです。園児が移動したときに、どのようなデータを管理しておけば効率的に答えを更新できるかを考えます。

今回は以下のようなデータの流れを構築することにします。それぞれのデータに対してどのような操作が必要になるか順番に見ていきます。

f:id:betrue12:20200804105421p:plain

まず園児が移動するときに、レートいくつの園児がどこからどこに移動するのか分からないといけません。それを知るために各園児のレート A と所属幼稚園 B を管理します。必要な機能は数列の1点を取得または変更することなので、配列でOKです。

園児の移動は、「ある幼稚園から指定したレートの園児を1人削除」して、「ある幼稚園に指定したレートの園児を1人追加」する操作です。またその操作の前後で、幼稚園の最強園児のレートがいくつになったか分かる必要があります。つまり幼稚園ごとのレートの集合 st に求められる機能は

  • 重複を含む値の集合を管理する。
  • ある値を1つ削除する。
  • ある値を1つ追加する。
  • 集合内の最大値を調べる。

となります。

そしてこの変更で最強園児のレートが変わった場合、それを maxes に反映する必要があります。そして maxes の最小値が答えとなります。つまり maxes に求められる機能は、st とほぼ同様の

  • 重複を含む値の集合を管理する。
  • ある値を1つ削除する。
  • ある値を1つ追加する。
  • 集合内の最小値を調べる。

となります。このようにデータの流れを整理して各段階で必要な操作を列挙することで、各データをどのようなデータ構造で持てば良いのかが分かり、操作回数も合わせて見積もることで計算量を把握することができます。

あとは、この操作を効率的に行えるデータ構造を適切に選びます。

実現方法(C++

C++であれば言語機能として std::multiset というものが提供されています。これを使うと、操作時点での要素数 n として必要な操作は全て  O(\log n) で実現可能です。

これは値の集合を、順序(大小関係)を保持しながら管理してくれるデータ構造です。各操作は以下のように行うことができます。

  • st からある値 a を1つ削除する:st.erase(st.find(a))
  • st にある値 a を1つ追加する:st.insert(a)
  • st の最小値を求める:*st.begin()
  • st の最大値を求める:*st.rbegin()

存在しない値を削除しようとしたり、要素数  0 であるときに最小値や最大値を求めようとすると異常な挙動になる可能性があるので注意です。

begin()rbegin()find() などの関数によって得られるイテレータというものについては以下を参考にしてください。

C++のイテレータを視覚的に理解する(競プロ向け) - ARMERIA

実現方法(それ以外)

C++以外の言語の場合は少し面倒です。今回の場合、必要になる操作のうち

  • 重複を含む値の集合を管理する。
  • ある値を1つ追加する。
  • 集合内の最小値/最大値を調べる。

という操作であれば優先度付きキューで実現できるので、これに値を削除する仕組みを入れることを考えます。(Rubyなど優先度付きキューもない言語の場合は自作しましょう…)

具体的には、メインの優先度付きキューとは別に、「削除予約」をするための優先度付きキューを用意します。そして各操作は以下のように行います。

  • 値を追加する:メインキューに値を追加する。
  • 値を削除する:削除予約キューに値を追加する。
  • 最小値/最大値を調べる:まず、メインキューと削除予約キューの最小値/最大値が一致する限り、それらをともに除外することを繰り返す。その後、メインキューの最小値/最大値を調べる。

ACコード

C++です。

Submission #15686906 - AtCoder Beginner Contest 170