なんか無駄なことをしている気がする……と思ったんだけど

べつにバグではないんだけど、競技中にあんまり調べていられなかったのと、「リングバッファ」というの名前が思い出せなくて、結局vecの要素のシフトをこう書いてしまった。ABC314のC - Rotate Colored Subsequenceである。

どことなくアホっぽいけど、これでも時間制限には引っかからないんですよね。reverse()ってO(M)くらいかと思うけど、意外と他の方法とかわらない。

    for clr in 1..=m {
        let tmp = map[clr].pop().unwrap();
        map[clr].reverse();
        map[clr].push(tmp);
    }

ちなみに、これ、なんでひっくり返しているかというと、取り出すときに都合がよかったのですよね。もちろんVecDequeueで書けばひっくり返す必要は無い(思いださなかった)。が、push_front()の回数が少ないせいか、意外なことにちょっと遅くなる。

    for i in 0..n {
        let j = map[c[i]].pop().unwrap();
        print!("{}", s[j]);
    }

pop()のかわりにイテレータで記憶しておくこともできる。添字でもいい。が、配列にする必要がある。コードは省略するが、これも速くはない。

そもそも、このようにvecの使い回しをしないで、公式の解説のように2つのvecを用意して、右から左に入れコピーした方が速くなる。が、桁が違うというほどではなかった。

Rushのコンパイラーが頭がいいせいかもしれないけど、AtCoderの問題の範囲では多分これはわりとどうでもよいトピックなんだと思う。

プログラマーになりたい。