Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

C1. Skyscrapers (easy version) (Codeforces Round #622 Div. 2)

C1の方です。(C2まだ通せてなかった・・・。)

問題

https://codeforces.com/contest/1313/problem/C1

問題概要

長さnの数列が与えられる。各項は正数を保つ限り任意に減少させることができる。またi番目の項a_iについてj \lt i \lt kかつa_j \gt a_i \lt a_kとなるjおよびkがあってはならない。

以上の条件をすべて満たす長さnの数列で、すべての項の合計が最大になるものを示せ。

考察

制約がn \lt= 1000で、TLが1秒なので、二重ループが回せます。よって、ある項を中心として貪欲に(できるだけ大きい数字を保ったまま条件を満たせるように)左右の数字を削っていく、をすべての項で試す、が間に合います。もちろん、その結果最も和が大きくなった場合が答えになります。

所感

Cの1000点にしれっとただの全探索が紛れ込んでいるあたりが、こどふぉの怖いところでありまた面白いところです。