AtCoder Beginner Contest 478に参加しました。

結果

A, B, C, D問題の4問正解でした。

なんだかC問題からずっと難しかった印象。 D問題が割とギリギリになったけど正解できたから満足。

https://atcoder.jp/contests/abc478/tasks/abc478_a

M個のぶどうをN人に配っていく。番号順に配った時、度の番号の人に何個配れるかを答える問題。

とりあえず愚直に番号順に1個ずつ配っていって解いていった。

もしくは、 M/N個は最低でも配れて、M mod Nの値に応じて先頭からM mod N人には1つ多く配れる。

これを計算して何番の人が何個かを計算して出力しても解けそう。

トッピングがN種類ある。i番目のトッピングは価格がi、嬉しさが $W _ {i}$ 。この時、価値の総和がV以下になるように3種類のトッピングを選んだときの嬉しさの最大値を求める問題。

そこまで難しい設定はないので愚直に実装して解いた問題。

長さNの整数列Aがある。幅Kの区間をソートできる。1回だけソートすることで整数列Aの全体をソート可能かどうかを答える問題。

なんだか難しかった。

AとAをソートした数列Bを用意した。A[i]とB[i]を比較して一致していればソートの必要なし、一致していなければソートの対象とする必要があると判断できるようにした。

そこから、ソートの必要がある要素が何個あるかとか、ソートの必要ありの要素の最初と最後の距離がK以下なのかとか、こういう時は1回のソートで全体のソートは無理だなと思う条件を色々チェックして最終的に1回のソートで全体のソートが可能かどうかを判定した。

解けてる気はしないけど通れば良いなと思いながら提出したコードがACしたので、本当に解けているのか自分のことながら不安。

空集合がN個あって、ある区間の集合に対してある値Xを追加するという処理をQ回繰り返した後の各集合の要素数を出力する問題。

追加する値のXが全部異なるならimos法で簡単に解けるけれど、同じ集合に同じ値を追加する可能性があるのでそこまで単純じゃないと思った。

まずQ回分の入力を受け取って、X別に区間（L,R）を整理して、複数の区間で重なっているものをマージしていった。その後imos法でどの集合に何個の値が入っているのかを計算して出力していった。