AtCoder Regular Contest 042 - A - 掲示板
https://gyazo.com/d654072df093d35628e3c1377b35115e
なんか最近のAtCoderじゃあまり見ない問題で面白かった.
考えたこと
愚直にやるなら、図に書かれているとおりにvectorを用意して、書き込みされたスレッドをvectorの先頭に移動するんだけど、vectorはこういった処理に適していない(後ろへの追加とかは速いけど)
回答用のvectorを用意して上げて、新しい書き込みのたびに、そこへpush_backしてあげればいいかな?
これだと、入力例2みたいに同じスレッドへ複数回書き込まれた時が対応できない
同じスレッドへの書き込みを1回で考えたい。
順序なので、結局最後の書き込みしか考慮しなくていいのでは?
スレッド1,2,3があって書き込みが 1 -> 2 -> 3 -> 1とされた場合, 最初の1がなくて 2 -> 3 -> 1でも答えは変わらない.
これでいけそう。回答用のvectorと、スレッドがすでに1度書き込みされたかを管理するvectorを用意してあげて、すでに書き込まれてなければ追加で良さそう.
この時、aは逆順にリバースが必要(最後の書き込みが優先されるので)
また、回答用のvectorへ追加した後に、書き込みが行われなかったスレッドの追加も必要だと思う(入力例2のような例や n > mの場合に対応)
提出したコード
code: A.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
int n, m; cin >> n >> m;
vector<int> a(m);
// 最後の書き込みから見ていきたいのでreverseする
reverse(a.begin(), a.end());
// スレッドがすでに1度でも書き込みされたかの状態管理用のvector
vector<bool> used(n, false);
// 回答用のvector
vector<int> ans;
// mを全て見ていき、最後に書き込まれた順にvectorへ追加していく
rep(i, m) if(!used[ai-1]) { }
// 書き込みされていないスレッドがある場合があるので、それを順番に追加する(元の並びが1,2,3...Nなので、シンプルにiを追加してあげればいい)
rep(i, used.size()) {
ans.push_back(i+1);
}
}
rep(i, ans.size()) {
}
return 0;
}