Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ABC141 反省会

絶望した。頭が悪すぎる。4完で1000ちょいみたいなパフォーマンスを取り続けてもあまり意味がないので、夜遅くに参加して毎回体調崩すくらいなら、しばらくコンテスト休むかも知れない。

A-Dはいつもにも増してイージー

E

ある先頭から長さLのハッシュをロリハで計算して、NxNのテーブルに格納する。

そして、大きいLからテーブルを見ていき、同じハッシュ値のやつがいたら、その先頭をまとめていく。

例えば、{ hash0 => [1,3,6], hash1 => [2,5,9] }のようになる。

あとは、値の方の最大値と最小値の差とLを比較して、重ならないなら見つかったということにする。値の方はソート済みなので、ソートする必要はない。

という方針で実装したが、駄目だった。計算量はO(N2)かと思ったが、WAだけでなく、TLEも出てしまった。ハッシュ値の計算方法を変えるとWAではなくTLEに変わったりもしたので、たぶん、ハッシュが衝突してしまったのだと思う。TLEになる理由は全く不明。

想定はZアルゴリズムで、第一感はZアルゴリズムだったのだが、その時はN=105と勘違いしてて捨ててしまった。N=103と気づいた時にはもうロリハのことしか頭になかったので戻ってこれなかった。絶対にとれた問題だと思う。時間には余裕があったので両方で実装してみればよかった。

ロリハはハッシュ値衝突が怖すぎるので、文字列マッチ系は他の方法からまず検討すべきということを教訓にします。よくよく考えてみれば、ロリハが想定解法であることとか存在しないでしょう。