シコウノストレージ

自分自身の考えを整理するために書いています。

今日のキョウプロ

216D

2N個のボールがあり、各色で塗られたボールはちょうど2個ずつ存在する。

ボールがM本の筒にk個入れられており、色はa[i][j]。

全ての筒の先頭を比べて同じ色なら取り出すことができる。

すべてのボールを取り出すことができるかという問題。

 

ボールがちょうど2つずつ存在するというのがポイントで、筒に2個同じ色があればそれをとればよいので最良の選択肢は存在しない(貪欲に取っていく)。

計算量が問題になってきて、M個の筒を比べる必要があるので必ずO(M)以上は必要。

配列を使えばとりあえずO(M^2)にはならなくて済むが、それをN回やる必要があるのでO(NM)になってしまう。

しかし、よくよく考えてみると2個以上同じ色のボールがないのだから、筒からとったボールをpushした時点で、pushしたボールの色以外の色が2個揃うということはあり得ないし、ボールの数が3個以上になることもあり得ない。

なので、pushした際に2個になったかどうか判定すればO(N+M)まで縮めることができる。

なお、実装が重たいので変数はしっかりわかりやすい名前にしたほうが良い。

 

216E

N個のアトラクションがあって、i個目のアトラクションの楽しさをA[i]とし、アトラクションを1回遊ぶごとに楽しさは1減少していく。

K回乗るときの楽しさの和の最大値はいくつかという問題。

これは、i番目にどれ乗るかというのが重要な問題で、現在の楽しさの大きいアトラクションから順に乗っていけばよいので貪欲法の問題。

降順にソートした上でA[i]からA[i+1]番目の差は、A[i]番目が一番大きい時に乗れる回数で、以降iが増えるにつれて、i+1個のアトラクションが最大値になる。

それを利用して、等差数列の計算をすれば答えがでる。

なお、i+1番目すべてをとるとK回を超えてしまうときは(i+1)個をとれるだけ取って残りを加算する処理が必要。