コンテスト中AC:A〜D
B - Better Students Are Needed!
配列を用意し、各要素は以下のようにします。
この配列は例えば、C++ならvector<pair< long long, long long >>
を使用します。
について、各要素の1つ目を第一キーに、2つ目を第二キーとして降順ソートすると、
得点の大きいものが前に来て、同じ得点ならの小さいものが前に来ます。
このように、第一キーと第二キーで昇順・降順が異なるようにソートしたい場合、一方を負にしておけば、ソート1回でこの並び方を実現できます。
後は、同じ値を2回取らないように配列に記録するなどしながら、問題文の通り、
の前から
個
の前から
個
の前から
個
を合格にしていけば良いです。
計算量はソートがボトルネックとなって、だと思います。
Submission #33302936 - AtCoder Beginner Contest 260
C - Changing Jewels
レベルの赤い宝石を
個、青い宝石を
個持っていたとします。
ここで、次の様に操作します。
- レベル
の赤い宝石
個から、レベル
の赤い宝石
個と、レベル
の青い宝石を
個得る。
- レベル
の青い宝石
個から、レベル
の赤い宝石
個と、レベル
の青い宝石を
個得る。
この一連の操作を1回の操作と考えると、操作1回でレベルの宝石からレベル
の宝石を得ます。この操作を
回すれば、レベル
の宝石は全てレベル
になります。
実装では、前述した2つの変数のみを持っていればよいです。操作一回での具体的な更新方法を示します。
コンテスト中は再帰で実装しましたが、普通のループで問題ありません。
テキストの公式解説のDPに近い感じですが、ボトムアップかトップダウンかという点が違うかなと思います。
再帰
Submission #33311975 - AtCoder Beginner Contest 260
ループ
Submission #33347207 - AtCoder Beginner Contest 260
D - Draw Your Cards
まず、以下が高速に実現可能なデータ構造が必要です。
以上で最小の整数
を得る
を削除する
を挿入する
これは順序付き集合で実現できます。(C++なら順序付き集合set
)
次に、以下を実現する必要があります。ここで、表向きで重ねられたカードを山と呼ぶことにします。
とそれ以上で最小の整数
を同じ山にする
が属する山にあるカードの枚数を取得する
ターン目に
が属する山のカード枚数が
となった時に、山に属するカード全てに
を記録する
が属する山が何ターン目に
枚となったかを取得する
これはUnion-Findにより実現できます。
AtCoder Libraryのdsu< long long > d(N)
の使用例を示しておきます。なお、カードに書かれた整数は全て-1して、にしておくことにします。
また、連想配列
を用意し、
が属する山が何ターン目で
枚となったかを
に記録することとします(普通の配列でも可)。
d.merge(X,Y)
d.size(X)
if (d.size(X)==K) m[d.leader(X)] = i
m[d.leader(X)]
ポイントとしては、同じ山の全てにターン数を記録するのではなく、Union-Findにおける同一グループの根にだけターン数を記録します。
各整数から根を辿ることで、自分が属する山が何ターン目に枚となったかわかります。
計算量はset
の各種操作がで、Union-Findの各種操作が
なので、
かなと思います。