geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Biginner Contest 260 参加記録

ABC Union-Find

コンテスト中AC:A〜D

B - Better Students Are Needed!

配列P,Q,Rを用意し、各要素は以下のようにします。
P_i = (A_i ,\ -i)
Q_i = (B_i ,\ -i)
R_i = (A_i+B_i ,\ -i)

この配列は例えば、C++ならvector<pair< long long, long long >>を使用します。

P,Q,Rについて、各要素の1つ目を第一キーに、2つ目を第二キーとして降順ソートすると、
得点の大きいものが前に来て、同じ得点ならiの小さいものが前に来ます。

このように、第一キーと第二キーで昇順・降順が異なるようにソートしたい場合、一方を負にしておけば、ソート1回でこの並び方を実現できます。

後は、同じ値を2回取らないように配列に記録するなどしながら、問題文の通り、

  • Pの前からX個
  • Qの前からY個
  • Rの前からZ個

を合格にしていけば良いです。

計算量はソートがボトルネックとなって、O(NlogN)だと思います。

Submission #33302936 - AtCoder Beginner Contest 260

C - Changing Jewels

レベルiの赤い宝石をa個、青い宝石をb個持っていたとします。
ここで、次の様に操作します。

  1. レベルiの赤い宝石a個から、レベルi-1の赤い宝石a個と、レベルiの青い宝石をaX個得る。
  2. レベルiの青い宝石b+aX個から、レベルi-1の赤い宝石b+aX個と、レベルi-1の青い宝石を(b+aX)Y個得る。

この一連の操作を1回の操作と考えると、操作1回でレベルiの宝石からレベルi-1の宝石を得ます。この操作をN-1回すれば、レベルNの宝石は全てレベル1になります。

実装では、前述した2つの変数a,bのみを持っていればよいです。操作一回での具体的な更新方法を示します。

b\leftarrow b+aX
a\leftarrow a+b
b\leftarrow b+bY

コンテスト中は再帰で実装しましたが、普通のループで問題ありません。
テキストの公式解説のDPに近い感じですが、ボトムアップかトップダウンかという点が違うかなと思います。

再帰
Submission #33311975 - AtCoder Beginner Contest 260

ループ
Submission #33347207 - AtCoder Beginner Contest 260

D - Draw Your Cards

まず、以下が高速に実現可能なデータ構造が必要です。

  • X以上で最小の整数Yを得る
  • Yを削除する
  • Xを挿入する

これは順序付き集合で実現できます。(C++なら順序付き集合set)

次に、以下を実現する必要があります。ここで、表向きで重ねられたカードを山と呼ぶことにします。

  • Xとそれ以上で最小の整数Yを同じ山にする
  • Xが属する山にあるカードの枚数を取得する
  • iターン目にXが属する山のカード枚数がKとなった時に、山に属するカード全てにiを記録する
  • Xが属する山が何ターン目にK枚となったかを取得する

これはUnion-Findにより実現できます。
AtCoder Libraryのdsu< long long > d(N)の使用例を示しておきます。なお、カードに書かれた整数は全て-1して、0,\ 1,\ ,\ \cdots N-1にしておくことにします。 また、連想配列mを用意し、Xが属する山が何ターン目でK枚となったかをm[X]に記録することとします(普通の配列でも可)。

  • d.merge(X,Y)
  • d.size(X)
  • if (d.size(X)==K) m[d.leader(X)] = i
  • m[d.leader(X)]

ポイントとしては、同じ山の全てにターン数を記録するのではなく、Union-Findにおける同一グループの根にだけターン数を記録します。
各整数から根を辿ることで、自分が属する山が何ターン目にK枚となったかわかります。

計算量はsetの各種操作がO(logN)で、Union-Findの各種操作が\alpha (N)なので、O(N(logN + \alpha (N)))かなと思います。