AtCoder Beginner Contest 260

4完4WA。

各問題

A - A Unique Letter

どうやるのが正解なのかよくわからず...。

自分は vector<int>(26) で各文字の出現数を数えて、1つのものを出力するようにしました。

B - Better Students Are Needed!

どうやるのが正解なのかよくわからず2...。あと誤読していて不要な実装をしてひどいことになりました。

結局の所、数学の点数、英語の点数、合計点数と、番号をペアにして配列に持ってソートして、上から所定の合格人数を拾ってくればよいです。

教科ごとに同じ人を拾わないようにチェックと、回答の出力をソートすることを忘れないように注意です。

C - Changing Jewels

まずレベルnの赤を処理します。レベルn-1の赤とレベルnの青になります。レベルn-1の赤を処理してもレベルnの青に影響しませんが、レベルnの青を処理するとレベルn-1の赤に影響するため、先にレベルnの青を処理します。するとレベルn-1の赤とレベルn-1の青が残りますが、レベルn-1の赤を処理するとレベルn-1の青に影響するのでそちらを先に処理します。

と行った具合で、n赤 -> n青 -> n-1赤 -> n-1青 -> ... の順で処理すればよいです。

A, B より楽だったんですが！？

D - Draw Your Cards

map<int, vector<int>> で管理して愚直に処理すればよいです。

上に重ねる操作のときに、下になったものをmapから消して上に来る方に移す必要があるのですが、vectorをコピーしてしまうとTLEしてしまうので、swapなどで計算量を削減する必要があります。

// あかんやつ
// 実装は抜粋です
auto itr = m.lower_bound(p);
m[p] = itr->second;
m.emplace_back(p);
m.erase(itr);

// ええやつ
// 実装は抜粋です
auto itr = m.lower_bound(p);
swap(m[p], itr->second);
m.emplace_back(p);
m.erase(itr);

まとめ

考察問題ないのに実装でパフォ1色分落とすとか自分的に一番やっちゃいけないやつ...。