2026-10-16
changed.cpp
struct Event {
unsigned seq;
std::string path;
};
std::optional<std::vector<std::string>> changed(const std::vector<Event>& events) {
}
ファイル変更の通知 Event の列を受け取り、変更されたファイルのパスを返す changed を書いてください。通知元は通知ごとに通し番号 seq を1ずつ増やして付けますが、同じ通知を再送することも、途中の通知を失うこともあります。それまでに受け取った最大の番号以下の番号を持つ通知は再送なので無視します。番号がそれより2以上大きければ途中の通知が失われているので、std::nullopt を返します。そうでなければ、パスを重複なしで、最初に現れた順に並べて返します。最初の通知の番号は何でもよく、events が空なら空の列を返します。
入力例 1
changed({{1, "a.cpp"}, {2, "b.cpp"}, {2, "b.cpp"}, {3, "a.cpp"}, {1, "a.cpp"}})
出力例 1
{"a.cpp", "b.cpp"}
入力例 2
changed({{5, "a.cpp"}, {7, "b.cpp"}})
出力例 2
std::nullopt
入力例 3
changed({})
出力例 3
{}
Reference
std::optional<std::vector<std::string>> changed(const std::vector<Event>& events) {
std::vector<std::string> paths;
std::set<std::string> seen;
std::optional<unsigned> last;
for (const Event& e : events) {
if (last && e.seq <= *last) {
continue;
}
if (last && e.seq != *last + 1) {
return std::nullopt;
}
last = e.seq;
if (seen.insert(e.path).second) {
paths.push_back(e.path);
}
}
return paths;
}
この列には、番号で見分ける重複とパスで見分ける重複の2種類があり、参考実装は別々の道具で扱います。番号の側を受け持つ last は最後に受け取った番号で、最初の通知が来るまでは値が無いので std::optional<unsigned> にしています。番号が last 以下なら再送として読み飛ばし、last + 1 でなければ途中が抜けているので std::nullopt を返します。
2つの判定は、再送の判定が先でなければいけません。入力例 1 の最後の {1, "a.cpp"} は、番号が last + 1 かどうかだけを見ると 3 から 1 への飛びですが、正しくは再送として捨てる通知です。順番を逆にすると、遅れて届いた古い通知のたびに std::nullopt を返し、そのたびに呼び出し側が全体を調べ直すことになります。
パスの重複は std::set で見分けます。insert の戻り値の second は新しく入ったときだけ真なので、初めて現れたパスだけが paths に最初に現れた順で積まれます。番号の飛びを見つけたときは、それまでに集めたパスも返しません。一部だけを返すと、失われた通知に含まれていたファイルが調べ漏れるからです。
掲載したのは参考実装で、唯一の正解ではありません。std::set を使わずに std::ranges::find で paths を探しても同じ結果になり、パスの数が少なければそのほうが速いこともあります。