AtCoder: ABC250 E - Prefix Equality (Swift)

E - Prefix Equality

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

参考：Kiri8128さんの解説

• コンテスト中は愚直にセットを配列に入れてREとTLEを出していたのが、ハッシュの配列にすればいいという方針
• Kiri8128さんのコードも見ていたが、最初は、SetのhashValueを使ってみてTLE（おしい）
• 計算量はhashValueのドキュメントには記載されていない
• Kiri8128さんのハッシュの算出方法だと随時更新できるし、軽量そうなのでそのまま利用させていただいてAC
• このハッシュを保存していくのは応用できそうだし、覚えておきたい
• 一方で、Kiri8128さんもご自身で触れているがハッシュ衝突のリスクを受け入れるかの判断は必要になりそう

配列を置換する方法

参考：hamamuさんの解説

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

（追記：2022-05-14）

XOR

参考：m_99さんの解説

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