# AtCoder: ABC250 E - Prefix Equality (Swift)

## [E - Prefix Equality](https://atcoder.jp/contests/abc250/tasks/abc250_e)

### ハッシュを配列に入れる方法

参考：[Kiri8128さんの解説](https://atcoder.jp/contests/abc250/editorial/3940)

- コンテスト中は愚直に[セットを配列に入れて](https://atcoder.jp/contests/abc250/submissions/31547930)REとTLEを出していたのが、ハッシュの配列にすればいいという方針
- Kiri8128さんのコードも見ていたが、最初は、[SetのhashValueを使ってみてTLE](https://atcoder.jp/contests/abc250/submissions/31594772)（おしい）
- 計算量は[hashValueのドキュメント](https://developer.apple.com/documentation/swift/set/3237061-hashvalue)には記載されていない
- Kiri8128さんのハッシュの算出方法だと随時更新できるし、軽量そうなので[そのまま利用させていただいてAC](https://atcoder.jp/contests/abc250/submissions/31594840)
- このハッシュを保存していくのは応用できそうだし、覚えておきたい
- 一方で、Kiri8128さんもご自身で触れているがハッシュ衝突のリスクを受け入れるかの判断は必要になりそう

### 配列を置換する方法

参考：[hamamuさんの解説](https://atcoder.jp/contests/abc250/editorial/3948)

- 数字を記号として認識して、それをAを基準に昇順に置換する方法
- その際、それまでの種類数と最大値も記録
- Bでも、Aと同じ置換を行い、やはり種類数と最大値を記録
- 今回の問題のように数字が純粋に記号として与えられている場合、それを置換することで最大値などの数字としての特性を活かせるようにするのは面白い
- 応用性がどれだけあるかわからないが、覚えておきたい
- [AC](https://atcoder.jp/contests/abc250/submissions/31595193)

（追記：2022-05-14）
### XOR

参考：[m_99さんの解説](https://atcoder.jp/contests/abc250/editorial/3906)

- 解説をチラ見したあと、自力で似たようなことをやろうとして失敗していた
- 解説にある二つの前計算を一緒にやろうとして、ちゃんと前計算1を最後までやっていなかったのが原因
- ちゃんと分けて書いたら[AC](https://atcoder.jp/contests/abc250/submissions/31643686)
- Setで追加して、増えるかどうか判断できるのは便利
- removeからinsertに書き換えたら[実行速度が改善した](https://atcoder.jp/contests/abc250/submissions/31651340)