AtCoder: ABC250 E - Prefix Equality (Swift)
E - Prefix Equality
ハッシュを配列に入れる方法
- コンテスト中は愚直にセットを配列に入れてREとTLEを出していたのが、ハッシュの配列にすればいいという方針
- Kiri8128さんのコードも見ていたが、最初は、SetのhashValueを使ってみてTLE(おしい)
- 計算量はhashValueのドキュメントには記載されていない
- Kiri8128さんのハッシュの算出方法だと随時更新できるし、軽量そうなのでそのまま利用させていただいてAC
- このハッシュを保存していくのは応用できそうだし、覚えておきたい
- 一方で、Kiri8128さんもご自身で触れているがハッシュ衝突のリスクを受け入れるかの判断は必要になりそう
配列を置換する方法
参考:hamamuさんの解説
- 数字を記号として認識して、それをAを基準に昇順に置換する方法
- その際、それまでの種類数と最大値も記録
- Bでも、Aと同じ置換を行い、やはり種類数と最大値を記録
- 今回の問題のように数字が純粋に記号として与えられている場合、それを置換することで最大値などの数字としての特性を活かせるようにするのは面白い
- 応用性がどれだけあるかわからないが、覚えておきたい
- AC
(追記:2022-05-14)
XOR
参考:m_99さんの解説