ABC 401-500/ABC439D - Kadomatsu Subsequence - 競技プログラミング用 知識集積所

---

問題

ABC439D

必要知識

B以下レベルの内容は省略

• 二分探索※

考え方

A[i]:A[j]:A[k]=3:5:7 という条件を「あるmに対し、A[i]=3m、かつ、A[j]=5m、かつ、A[k]=7m」と書き換えておく。
すると、Aの中から、値が3mになるもの一覧、値が5mになるもの一覧、値が7mになるもの一覧、を抜き出しておくのが第1段階になる。
しかし、Aの値は10^9通りあるので、mの値を添字とするvectorで実行するとサイズが大きくなりすぎる。
そこで、map※を利用してmの値とその出現位置一覧vectorを記録しておく。

その後、jが(i,j,k)の中で端にあるパターン数を考える。
これは、値が5mである全ての位置jについてそれぞれ、以下を考えればよい。

• 「値が3mであるものが、その5mの位置より左に何個あるか」×「値が7mであるものが、その5mの位置より左に何個あるか」
• 同じく右に何個あるか
• 上記2つの和が、そのjを採用するパターンの総数

これは、出現位置を記録するvectorを昇順で作ってあれば、二分探索※を利用して簡単に求められる。

各jに対して求めた値の総和が答えとなる。

解答例

解答例
上記説明のmのところをk（問題で使っている文字と重複）と書いてしまっている。

注意点

答えにlong long型を使う。

3が数千個、7が数千個、5が数千個という並びだと、答えが容易にint型から溢れる。

別解