Codeforces #215 B in D

クイズの問題作ってたら飽きたので問題解いてた。一大学クイ研の会長として色々とダメな気がする。アレです。気分転換です。気分転換のほうが時間かかったけど。

問題はここ。まずある大きさの int 配列を受け取って、後で指定されたインデックスから終端までのスライスの unique を取った時のサイズを返す。

自分の正解答案は以下。

注目すべきは 8 行目以降。ていうかぶっちゃけこの部分は他の人の答案パクりました。最後の言い逃れとして一応 D 言語以外の答案を見るようにしました。というかフィルタかけたら僕以外に D 言語の答案無かったし。だいたいみんな C++ で解いてた。でも僕の上のプログラムでも 78ms だし十分匹敵する速度は出せてた。

閑話休題。ソートされてない配列のユニークを取りたければ連想配列を作る。で何も考えずに端っこから順番に連想配列に突っ込んでいく。んで ans[i] には後ろから i 個分のスライスをユニークにした配列のサイズを入れておく。これで、この問題で求められうる全ての場合の解答が O(n) で用意できる。よく分かんないから値はブーリアンにしました。でもメモリはめっちゃ（7300KB）使ってた。まあ範囲内だし気にしない。

最初 std.algorithm.uniq を使ったら全然意図しない配列が返ってきた（Ruby 脳なので Array#uniq 的な動作を期待してた）。よく考えてみたらどうも隣り合う要素が一致してるかどうかしか判定してないみたいで、こういう実装の仕方は C++ でも同じらしい。何でこういう風にするかというと O(n) で終わるので速いから。で、これを使うとき配列はソートされてなければいけないので、arr.sort.uniq みたいにして使いなさいよと。std.algorithm.sort は O(nlog(n)) で終わるので、Ruby Array#uniq みたいに O(n^2) かかるよりはさっきみたいにしたほうが速いということか。でも知らないと分からないよね……情弱辛い。

ちなみに僕は最初はインデックスを求められる度に後ろから l 個のスライスのユニークを求めてたので、大きさ 10^5 の配列のユニークを 10^5 回調べたら 10^10 だからそりゃあ TLE で死ぬのも当然だわなあと。また 1 個勉強になりました。

L5-6 で front と back を使ってるけどこれは L4 の最後に array を付けてなかった時の名残です。どうせ UFCS で繋げないなら先行評価しちゃった方がいいよなと思って array を外しました。適宜使い分けていこう。

明日は 1 限なのでもう寝ます（寝ない）。