ABC 250 E: Prefix Equality
方針
解説にも書いてあるが、集合の大きさが等しいのはサイズが等しいときのみ。各接頭辞に対する要素の集合は前から順番にSetに突っ込んでいけば簡単に求められる。
集合が等しくなる瞬間のサイズは、次のようにして求められる。（尺取的な気持ち）
各数列に対して、ポインタ、先頭からポインタまでの要素の集合、異なる方の数列の集合に含まれていて自分には含まれていない要素の集合を用意する。 集合が小さい方のポインタが指している方を集合に追加する。新しく追加された要素が、自分に含まれない集合に存在した場合、それを消す。また、相手の集合に含まれていなければ、相手側に含まれていない要素の集合に追加する。その後、ポインタを進める。２つの集合の大きさがおなじになったとき、両方の含まれていない要素の集合が両方空でなければ、そのサイズでの２つの集合は等しい。
反省
3億年ぶりに、それなりの難易度の競技プログラミングの問題を解いたので、コードにバグを仕込みまくった。（バグだらけのコード）以下はミスの一覧。
- 参照している配列が違う(35行目)
- ループの条件が違う(16行目)。この条件だとサンプルで失敗する。
&&を||に変えると、(1,1,1), (1,2,3)のようなケースで無限ループする。更新がなくなるまで続けるのが正解。 - 集合の同値性判定の場所がおかしい（18,32行目）。これだと、(1,2),(2,1)のようなケースで、最後の更新で等しくなった場合が考慮されない。内側のループの最後でやるか、外側のループが終わったあとにもう一度同じ判定を追加する必要がある。
教訓
- それなりに複雑な処理はコードをコピペして編集するより、関数にしたほうが良い。（今はIDEでコーディングしているので）正直、引数に副作用を与えるコードを書きたくない気持ちがかなり強いが、競技プログラミングはメンテナンスするコードを書く競技ではないため。
- 尺取的なコードを書くのが苦手すぎるのでもっと練習するように。
はじめに通過させたコードはこれ。
