ABC_362_E "Count Arithmetic Subsequences"をrubyで解く
いつになったら水安定するんだ。
今回の問題はこちら
DP解法
解説
緑以下でDPが得意という人はいないと思います。
私自身コツがあるならこっちが知りてーよと毎週思っていますが、今回は特に何が一緒であれば合流させてOKなのか丁寧にリストアップする事が重要でした。
今回は「現在見ている数列のインデックス」「現在の等差数列の長さ」「等差数列の末尾の値」「等差数列の交差」が同一だった場合のみ同じ場合として合流させる事ができます。まさかの4次元DPです。
1行前しか見ないタイプのDPの時には、oldとnewの2行だけ見てそれ以前の行は捨てる事ができます。コードがやや複雑になる代わりに、dp配列がコンパクトになり高速化できます。また等差数列の長さが1の場合を考えると、交差を保存するより「等差数列の末尾から一個前」の値を保存する方がバグを抑えられます。
以上から、「現在の等差数列の長さ」「等差数列の末尾の値」「等差数列の末尾から一個前」をキーに、取り出す位置の組み合わせを値にした連想配列をoldとnewの二つ用意してループします。rubyではhashのキーに配列を入れる事ができるので、3次元配列をサボって長さ3の配列をキーにしてしまいます。こういう事するとしょっちゅうバグります。おそらく内部的にhashが衝突しているので、良い子のみんなはちゃんと3次元配列を書きましょう。
ACコード
ほぼ同じ事をやっているこのコードでなぜWAなのか、正直納得いきません。誰か教えてください。
算術的解法
こっちの解法をメモするためだけにこの記事を書きました。
解説
- 予め「配列Aにおいて、どの値がどこのインデックスにあるか」をキャッシュしておきます。
- 長さ1の等差数列は明らかにN通りあります。
- 長さ2の等差数列は、明らかにN*(N-1)/2通りあります。
- Aから値が2つ(以上)選ばれて等差数列が形成されると、等差数列に次に追加される値は「等差数列の末尾の値」と「交差」から算出できます。
- 値が決まれば、その値がAのどこにあるかは1で探索済みです。ただし「等差数列の末尾のインデックス」より左の値は使えないので切り捨て、右側の値のみを考えます。
- 等差数列の長さを一つ伸ばしたパターン数に、5で見つけた「右側の値のインデックス」の個数分を追加します。
- 5で見つけた「右側の値のインデックス」をループして、「新しい等差数列末尾の値のインデックス」「新しい等差数列末尾の値」「交差」「新しい等差数列の長さ」を使って4に再帰します。
- 4から7までの流れを、A_1からA_Nまでの中から2つを選ぶ全組み合わせに対して行います。交差0の場合は無限ループに入ってしまうので一旦無視し、後で合計します。
- 交差0、つまり値が等しいパターンを追加します。等差数列の長さが2以下の場合は2と3で追加済みである事に注意します。
ACコード
「この方法はdpより遅い」と一度言い切ってしまったのですが、dpのコードだけ剰余を%ではなく引き算で計算していた事が原因でした。剰余の計算方法をそろえた場合、dpよりも再帰の方が早いです。
dpが遅いのはまだ許せます。ruby競プロで1番辛いのはheapがない事。
Discussion