Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 329)

ABCDFの5完1TLE

各問題

A - Spread

いわれたとおりやりましょう。

int n = (int)size(s);
for (int i = 0; i < n; i++) cout << s[i] << (i == n - 1 ? '\n' : ' ');

こんなかんじで。

B - Next

逆順でソートして(当たり前ですがこの時点で先頭が最大値)、二番目から順に先頭の値と比較して違う値になったらそれが答えです。

C - Count xxx

文字ごとに、最大いくつ並んでいるかを数えて、それらを足し合わせたものが答えです。

区別しませんをうっかりして、ランレングスしてから l * (l + 1) / 2 を計算して答えがあわないあわないをして時間をロスしてしまった...。

ていうか C 問題なんだからそれでよかったのでは?!

D - Election Quick Report

map<得票数, set<得票者の番号>> で管理すればよいです。

E - Stamp

なにもわからない。

操作を最後の方から確認するタイプのやつ?

F - Colored Ball

各箱に入っているボールを vector<set<int>> で管理すればよいのですが、そのままやると TLE してしまいます。

なので、うまいことスワップしてボールを移動させる操作について常に小さいほうから大きいほうに移動させるように工夫すれば間に合うようになります。(いわゆるマージテクというやつ?)

テクを使わない回答を投げて 1TLE。(無駄...)

まとめ

C と D の実装でかなりもたついてしまい、最悪緑落ちの可能性もありそうなところから、マージテク(でいいのか?)を思い出したおかげで命拾いしました。