AtCoder Beginner Contest 162 [ D - RGB Triplets ]をPythonで解く（400点、🟫茶diff）

問題

atcoder.jp

解法

1 <= N <= 4000
なのでO(N³)だと、4³ * 10⁹ でTLEのはず。
なので、R, Gの二つの要素を固定。
すると O(16 * 10⁶) くらい？
あとは、計算でBの要素から何個採用できるかを出す。
この方針でTLEは出ないはず。

R, Gのある場所のインデックスは総当たり。
R, Gのある場所のインデックスの大きい方と小さい方の変数をbig, smallとする。

I < j < k であるから、このbig, smallは
1. small = i, big = j
2. small = i, big = k
3. small = j, big = k
の3通りが想定できる。
j-i != k-j である必要があるので、採用しない要素があるかをBのインデックスから確認する。

採用しない要素の数が出たら
Bの数 - 採用しない要素の数
を足し込んでいく。

実装

実行結果

PyPy3(7.3.0) AC 315ms
Python3.8.2 AC 1967ms お、ギリやな

参考

uchidama.hatenablog.com

この問題が似てた。