ABC 401-500/ABC406C - ~ - 競技プログラミング用 知識集積所

---

問題

ABC406C

必要知識

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

• 特になし

考え方

チルダ型の定義がわかりにくいが、これは、

• 最初は増加していく
• 途中から減少していく
• 再び増加になり、そのまま最後まで増加する

ということである。

個数の数え方は、例えば、全体が1つのチルダ型である場合、

{1,2,3,7,6,5,4,8,9,10,11}

のような場合、真ん中の7,6,5,4は採用して、追加で左右を何個採用するか考えて3*4=12個と求められる。

ということは、増えたり減ったりを繰り返す場合でも、同様に数値が減少する地帯の両サイドで増加する列が何個あるかを数え、その積の総和を取ればよい。
それはつまり、連続増加地帯の長さを前から順に数えてvectorに入れ、隣接項の積の総和を求めればよいことになる。

解答例

解答例

注意点

long long型を使う

10^5くらいの数同士の積が出来る場合があるので、int型には収まらないことがある。
long long型を使うこと。

別解