ARMERIA

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

University of Aizu Programming Contest 2012(AOJ 1508)RMQ

お題箱より。

Aizu Online Judge

解法

1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存在する要素のインデックスがずれます。そのため、インデックスに基づいて固定された構造を持つセグメント木では対応できません。

ではどうすれば良いのかというと、インデックスに依存しない構造を持つ平衡二分木を用いれば良いです。これなら要素の削除と追加ができます。

ということで、残りはこの問題と言うより平衡二分木の解説になってしまいますが…平衡二分木については非常に有名なスライドがあるのでこれを紹介します。

プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~

平衡二分木の話は少し紛らわしくて、解説やサンプルコードなどを読む際には以下の2種類のどちらを目的としたものなのかを意識する必要があります。

  • C++std::set のような順序付き集合としての機能。要素を順序付きで保持する。値の追加や削除、小さい方から  k 番目の要素の取得、大小関係に基づく二分探索、区間クエリの処理などができる。
  • 数列の拡張としての機能。要素を列としての並びに基づいて保持する。 k 番目の要素の取得・挿入・削除、区間クエリの処理などができる。

個人的には前者を特に「平衡二分探索木」と呼び、主に後者を指す時に「平衡二分木」という言葉を使うようにしていますが、競プロerの中でも確かな呼び分けがされていないように思います。先ほどのスライドで紹介されているTreapの実装は後者で、この問題で必要なのも後者です。

このスライドの実装に区間クエリの処理機能を追加します。やることはセグメント木と同様で、まず各ノードは自身以下の部分木の値を全てマージした計算済みの値(今回の問題では最小値)を常に持つようにしておきます。この値はスライドの実装の cntsum と同様に、自身以下の部分木が変化した時に計算し直せば良いです。

クエリ処理する時には根から再帰的に見ていって、各ノードは親に以下のような値を返すようにします。

  • 対象ノード以下の部分木が受け持っているインデックス範囲が、
    • クエリ対象範囲と全く重複していないならば、単位元を返す。
    • クエリ対象範囲に完全に含まれているならば、計算済みの値を返す。
    • そうでないならば、左の子が返した値、(もしノード自身のインデックスが範囲に含まれているならば自身の値、)右の子が返した値をマージした値を返す。

セグメント木とは異なり各ノードが受け持つインデックス範囲が固定されていませんが、部分木のサイズ cnt は分かるので、根から再帰的に呼び出すときに各ノードのオフセット(その部分木より左にいくつ要素があったか)を渡していくことで知ることができます。

ACコード

Aizu Online Judge

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

CPSCO2019 Session3 F - Flexible Permutation O(N^2)解法

お題箱より。 O(N^{2}) 解法が知りたいというリクエストだったので考えてみました。

F - Flexible Permutation

解法

後に扱うDPの都合上、個人的にはインデックスよりも値に注目したほうが理解しやすいので、条件を値中心の言葉に言い換えます。 P_{i} \gt i であるような値  P_{i} を「左に動いた」、 P_{i} \lt i であるような値  P_{i} を「右に動いた」、 P_{i} = i であるような値  P_{i} を「動かない」と呼ぶことにします。

まず、動かない値  N-A-B 個を固定します。この選び方は  _{N}C_{N-A-B} 通りあり、これらの値を除くと残りは  A+B 個の必ず動く値だけを考えれば良いことになります。

公式解説の  O(N^{3}) 解法と同様に、値を順番に足していきながら以前の値とswapしていくDPを考えます。ただしそのまま適用した場合、DPの途中では相変わらず「左に動いている」「右に動いている」「(一時的に)動いていない」値がいくつあるかという情報を管理する必要があり、状態数が落ちません。

そこで以下のようなものを数える包除原理を考えます。

  • 予め指定したある  k 個の要素の集合について、値が動かない(違反状態である)。
  •  A 個の要素について、値が左に動く。
  • 残りの  B-k 個の要素について、値が動かないか、または右に動く。

つまり「ちょうど  A 個の値が左に動く」という条件は絶対に満たすとして、 B 個の要素について包除原理を適用する、ということです。こうすると先に  k 個の値を除いておけば、値の扱いで区別するべきものは「左に動いている」「それ以外」の2種類になり、状態数が  O(N^{2}) に落ちます。

  •  dp\lbrack i \rbrack\lbrack a\rbrack = 既に  i 個の値を置いていて、そのうち左に動いている値が  a 個あり、それ以外の値が  i-a 個あるような並べ方の数

遷移は次に置く値を「そのまま右端に置いた」「左に動いている値とswapした」「それ以外の値とswapした」ときにそれぞれ  a がどのように変化するかを考えれば良いです。具体的には「それ以外の値とswapした」ときだけ  a 1 つ増えることになります。

包除原理に基づいて結果を集計します。違反状態として指定した要素の個数が  k である場合、その  k 個の選び方が  _{A+B}C_{k} 通り、残りの場所の置き方が  dp\lbrack A+B-k\rbrack\lbrack A\rbrack 通りあるので、これらの積に  (-1)^{k} を掛けて全て合計すれば良いです。最後に  _{N}C_{N-A-B} を掛けると答えになります。

ACコード

Submission #15585152 - CPSCO2019 Session3

Educational Codeforces Round 92 F. Bicolored Segments

お題箱より。

Problem - F - Codeforces

問題概要

 n 個の閉区間  \lbrack l_{i}, r_{i}\rbrack が与えられ、それぞれは赤または青のいずれか1色に塗られている。

「異なる色の2つの区間が共有点を持ってはいけない」という条件のもとで、これらのうちできるだけ多くの区間を選びたい。選ぶ個数の最大値を求めよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  1 \le l_{i} \le r_{i} \le 10^{9}

解法1:DP

あらかじめ区間を右端でソートしておき、右端の値が小さいものから順に見ていくDPを考えます。インデックスもソート後の順番で振り直します。

赤の区間を採用できる条件は、これまで最後に採用した青の区間の右端が、採用しようとしている赤の区間の左端よりも小さいことです。逆も然りです。なので素直に考えると、

  •  dp\lbrack i\rbrack\lbrack j\rbrack = これまで最後に採用した赤の区間 i で、最後に採用した青の区間 j であるときの、採用した区間数の最大値

というDPを構成することができます。区間を1-indexedで扱い、「まだその色の区間を採用していない」をインデックス  0 で表すと都合が良いです。これで計算量  O(n^{2}) では解けますが、間に合いません。

ではどうするのかというと、さらに状態をまとめます。以下のように2色それぞれで状態をまとめ、区間を順番に見ていきながら同時に更新していきます。

  •  dp_{1}\lbrack i\rbrack = 今までに見た区間だけを使って、最後に採用した赤の区間 i であるときの、採用した区間数の最大値
  •  dp_{2}\lbrack i\rbrack = 今までに見た区間だけを使って、最後に採用した青の区間 i であるときの、採用した区間数の最大値

これは先ほどの  dp\lbrack i\rbrack\lbrack j\rbrack という2次元テーブルで管理していた状態について、それぞれの軸方向ごとに最大値を取ったものになります。このDPテーブルをどのように更新するのか考えます。

まず2次元テーブルを用いたDPがどのような遷移になるのか確認しましょう。見ようとしている区間が赤だとします。更新対象となるのは、最後に採用した青の区間の右端が見ようとしている赤の区間の左端よりも小さいものです。つまり  j がある値以下の範囲で更新が行われることになり、図で表すと以下のようになります。

f:id:betrue12:20200801153434p:plain

これを両軸方向に串刺しにして最大値を取った  dp_{1},  dp_{2} はどうなるでしょうか。図のインデックスを用いて説明します。まず  dp_{2} について考えると、更新対象となっている  dp_{2}\lbrack 0\rbrack, dp_{2}\lbrack 1\rbrack をそれぞれ  1 増やせば良いことが分かります。そして  dp_{1}\lbrack 3 \rbrack は増やした後のこれらの値の最大値になります。

つまり2次元テーブルで状態を管理しなくても、これらの  dp_{1}, dp_{2} だけで遷移を計算することができます。全ての区間を見終わったら、 dp_{1}, dp_{2} のどちらか(どちらでもOK)について最大値を取ったものが答えになります。

必要な操作は区間への加算と区間の最大値取得なので、遅延伝播セグメント木などで実現することができます。

ACコード1

Submission #88638709 - Codeforces

解法2:二部グラフ

公式解説で解説されている方法です。

区間を頂点とみなし、同時に採用してはいけない区間の間に辺を結ぶグラフを考えると、これは二部グラフになります。求めたいのはこのグラフの最大独立集合の頂点数です。

二部グラフでは最大独立集合の頂点数は全頂点数から最大マッチングの数を引いたものになります。つまり最大マッチングを求めれば答えを計算できます。

参考:二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理! - Qiita

ということで結局、赤と青の区間の組で共有点を持つものをなるべく多くマッチングさせることを考えれば良いです。これは例えば以下のように求めることができます。

  1. 赤の区間の左端と青の区間の右端を混ぜてソートする。値が同じ場合、赤の区間のほうが前になるようにする。
  2. 区間を順番に見ていきながら以下の処理を行う。
    • 赤の区間の場合は、「マッチング待ち区間」として右端をプールする。
    • 青の区間の場合は、プールされているマッチング待ち区間であって共有点を持つ(つまり右端が青の区間の左端以上である)もののうち、最も右端が小さいものを取り出しマッチングする。

このマッチング待ち区間のプールに必要な操作は「ある値を追加する」「プールに存在する値のうち、ある値以上で最も小さい値を取り出し、それを削除する」なので、C++であれば multiset 、このようなものが言語機能にない場合は座標圧縮+BIT+二分探索などで実現することができます。

ACコード2

Submission #88626147 - Codeforces

エイシング プログラミング コンテスト 2020 F - Two Snuke

F - Two Snuke

公式解説とは違う解法です。

解法

 N \lt 5 のときは答えは  0 なので、 N \ge 5 とします。

まずは  O(N) 解法を

まず答えを  O(N) で求める方法を考えます。

 s_{1} + n_{1} + u_{1} + k_{1} + e_{1} の値を  x として、これを全通り試しましょう。そうすると、この  x 5 つに分ける分け方が  _{x+4}C_{4} 通りあります。 x 個並んだボールを  4 本の仕切りで  5 つの領域に分ける場合の数です。

 s = s_{2} - s_{1} として、 n, u, k, e も同様に定義します。そうすると「全部足して  N 以下」という条件は  s + n + u + k + e \le N-2x と表記することができます。これを満たす  (s, n, u, k, e) の組それぞれについて  snuke (人名ではなく積です)を計算し、全て合計したものを求めたいです。これは、以下のような場合の数と等しくなります。

  •  N-2x 個のボールに  5 本の仕切りを入れて  s, n, u, k, e, (あまり) 6 つの領域に分け、さらに  s, n, u, k, e に相当する  5 つの領域から  1 つずつのボールを選ぶような場合の数。

これは言い換えると、ボールと仕切りを並べる合計  N-2x+5 箇所のスペースから、仕切りと選んだボールに相当する  10 箇所を選び、その  10 箇所には左から順に「選んだボール、仕切り、…、選んだボール、仕切り」と割り当てるような場合の数に等しいです。つまり、この値は  _{N-2x+5}C_{10} と計算できます。

f:id:betrue12:20200712052630p:plain

 x の範囲としては  s, n, u, k, e が全て正になれるもの、つまり  N-2x \ge 5 である範囲を考えます。そうすると答えは

 \displaystyle \sum_{x=0}^{\lfloor\frac{N-5}{2}\rfloor} \left({}_{x+4}C_{4} \times {}_{N-2x+5}C_{10}\right)

と計算することができます。階乗を前計算して  x についてループを回すことで  O(N) で解くことができますが、間に合いません。

偶奇に分けて多項式と見る

先ほどのシグマの中身を見てみましょう。 {}_{x+4}C_{4} という値は、具体的には  \frac{1}{24}(x+4)(x+3)(x+2)(x+1) という  x についての  4多項式です。同様に  {}_{N-2x+5}C_{10} (N-2x) についての  10多項式です。つまりシグマの中身は  x N についての  14多項式です。より正確には、全ての項で  x N の次数合計が  14 以下であるような多項式となっています。

ここで重要な性質として、 x についての  d多項式の値を  x=0, ..., n まで合計したものは  n についての  d+1多項式になります。

今回の計算式におけるループ終端は  \lfloor\frac{N-5}{2}\rfloor でした。このままでは扱いにくいので  N の偶奇で場合分けします。例えば  N が奇数である場合、 n = \frac{N-5}{2} と置きます。そうするとループの終端は  n となり、 N 2n+5 で置き換えるとシグマの中身は  x n についての  14多項式になります。先ほどの性質から、このシグマを処理した結果は  n についての  15多項式になることが分かります。

具体的に冪乗和の公式を当てはめて大量の計算をすればこの多項式の係数が求められますが、絶対にやりたくないです。「ラグランジュ補間」という方法を使いましょう。これは「 n についての  d多項式  f(n) の自由度は  d+1 であり、 d+1 通りの相異なる  (n, f(n)) の組から多項式を一意に決定することができる」という性質を用いるものです。特に、ある1つの  n に対する  f(n) の値であれば  O(d) で計算することができます。

つまり、 n=0, 1, ..., 15 (すなわち  N=5, 7, ..., 35)に対する答えをそれぞれ  O(N) で計算し、これらを用いてラグランジュ補間を行えば、入力  N が奇数である場合の答えを高速に求めることができます。

 N が偶数である場合も  n = \frac{N-6}{2} と置くことで同様に計算することができます。

ACコード

Submission #15191688 - AIsing Programming Contest 2020

ラグランジュ補間のライブラリを持っていれば実装は楽です。ラグランジュ補間の実装は、長くはないですが計算式がややこしいです。

実は  N \ge 5 かどうかを場合分けせずに  N=0, 2, ... または  N=1, 3, ... の結果からラグランジュ補間しても良いのですが、一応説明に従い場合分けをしています。

Codeforces Round #654 (Div. 2) E2. Asterism (Hard Version)

Problem - E2 - Codeforces

問題概要

長さ  n の数列  a = \lbrace a_{0}, ..., a_{n-1} \rbrace素数  p が与えられる。まず、以下の問題を考える。

  • 整数  x が与えられる。 \lbrace 0, 1, ..., n-1\rbrace を並び替えた順列  q_{0}, ..., q_{n-1} であって、全ての  i について  a_{q_{i}} \le x + i が成り立つようなものは何通りか?

この問題の答えが  p の倍数とならないような  x を全て列挙せよ。

制約

  •  2 \le p \le n \le 10^{5}
  •  1 \le a_{i} \le 10^{9}

解法

説明と実装を合わせるために0-indexedで表記します。また、与えられた数列  a をソートしておきます。

まず数え上げ問題の答えがどうなるかを考えます。 i 番目(最初を  0 番目とします)の選択において  q_{i} として選べるインデックス  k の候補は、 a_{k} \le x+i が成立するものから、 q_{i-1} までで既に使っている  i 個を除外したものです。この選択肢の数は  x が増えるほど増えていき、それ以前の選択で何を選んだかに依存しません。 n 個全てにおける選択肢の個数の積が数え上げ問題の答えになります。

 p素数であることから、NGになるのはこの選択肢の個数に  p の倍数が含まれているときだけです。このNGになる条件を、選択肢が  0 個になる場合と  p, 2p, 3p, ... 個になる場合でそれぞれ考えます。

選択肢が  0 個になる場合

 i 番目の選択において選択肢が  0 個になる条件は、 a_{k} \le x+i が成立する  k i 個以下であること、つまり  a_{i} \gt x+i が成立することです。どれか1つ以上の選択において選択肢が  0 通りとなる条件は、これら全ての和集合を取って

 \displaystyle \max_{i \ge 0}(a_{i}-i) \gt x

が成立することです。

選択肢が  p, 2p, 3p, ... 個になる場合

まずは選択肢がちょうど  p 個になる場合だけ考えましょう。

 i 番目の選択において選択肢が  p 個になる条件は、 a_{k} \le x+i が成立する  k がちょうど  i+p 個であること、つまり

 \displaystyle a_{i+p-1} \le x+i \lt a_{i+p}

が成立することです。これらのNG条件を順番に書き下して、 x が単独になるように移項すると

  •  a_{p-1} \le x \lt a_{p}
  •  a_{p}-1 \le x \lt a_{p+1}-1
  •  a_{p+1}-2 \le x \lt a_{p+2}-2
  • ...
  •  a_{n-1} -n+p \le x

となります。これらの式の並びを見ると、前の区間の終点より小さいところから次の区間が始まり、それを繰り返して最後は終点なく  x \to \infty までNG区間が続いています。このことからこれら全ての和集合は、全区間の始点のうち最も小さいものだけを用いて

 \displaystyle \min_{i \ge p-1}(a_{i}-i+p-1) \le x

と1つにまとめることができます。

f:id:betrue12:20200707220311p:plain

選択肢の個数が  2p, 3p, ... 個になるNG条件がまだ残っていますが、これらは選択肢が  p 個になるような  x より大きいので、これらも全て上記の条件に含まれます。

まとめ

以上でNG条件が全て考慮できて、これらは非常に扱いやすい形をしています。これらの2つの条件に当てはまらない  x の範囲は

 \displaystyle \max_{i \ge 0}(a_{i}-i) \le x \lt \min_{i \ge p-1}(a_{i}-i+p-1)

と1つの区間(あるいは空集合)として表現できるので、両端の値を求めることで答えを列挙することができます。

ACコード

Submission #85690039 - Codeforces

Codeforces Global Round 9 E. Inversion SwapSort

Problem - E - Codeforces

問題概要

長さ  n の数列  A = \lbrace a_{1}, ..., a_{n}\rbrace が与えられる。この数列についてインデックスのペア  (i, j) i \lt j かつ  a_{i} \gt j を満たすとき、このペアは転倒していると呼ぶ。

与えられた  A について転倒している全てのペアを並べた列であって、「列に並んでいる順に、ペアが示すインデックスの要素をスワップさせる」という操作によって  A を昇順ソートできるものが存在すればその一例を求め、存在しなければ -1 を出力せよ。

制約

  •  1 \le n \le 1000
  •  1 \le a_{i} \le 10^{9}

解法

まずは簡単のため、 a_{i} が全て異なる場合を考えます。

末尾から順番に、正しい値になるように操作していきます。操作順番を上手く選ぶことで以下のような操作をすることが可能です。

  • 末尾のインデックス  n が関わる転倒ペアについてのスワップ操作を全て消化する。
  • 操作後、末尾に全ての要素の中で最大の値が置かれている。
  • 末尾以外の要素同士のスワップは一切行わず、それらの大小関係も変化しない。

具体的には、末尾と転倒ペアをなしている(つまり末尾より要素の値が大きい)インデックス全てについて、要素の値が小さいものから順番に末尾とスワップしていけば良いです。

f:id:betrue12:20200705145707p:plain

この操作によって末尾以外の場所では転倒ペアの使用状況も要素同士の大小関係も変化しないので、これを後ろから順番に繰り返し適用していくことで必ず数列をソートすることができます。

もし値が同じ要素が複数存在するときには、それらの間には転倒ペアがないので、「初期状態で前にある要素ほど値として小さい」と順序を付けてしまうことで同じように解くことができます。

ACコード

Submission #86025608 - Codeforces