せっかくやってるので記録を残していくことに
本番のコードまま貼っていきます
パフォーマンスはぎり水色ぐらい。Dがもっと早く解けてればねー
ただ文章を出力するだけなので難しいところはないでしょう
2で何回割り切れるか聞かれてるのでそのままコードにしました
5進法で表して、1234を2468に置換すればいいだけだとわかったので、なんかそのまんま解く。n進法に直すコピペ部分はchatgpt産
置換するところは関数とか探す方が面倒だったので地道に置換
chatgptの生のコメントが残ったままコピペしていたりと、いろいろ生々しいACコードです
今回はここまでしか解けず。もっと勉強せんとね。
手の付け方から迷ったんだけど、
- 減らすことはできる
- 削除もできる
ということから、自身を起点に左右へどれぐらい伸ばすことが出来るかが問われていると理解。なので、n箇所について、自信を中心にしたときにサイズはいくつが最大かをそれぞれ求めて、その答えを答えにすることに。
例えば
1 2 3 1 2
だと、真ん中の3は左に1 2 3となるので、左へ3
右には3 1 で終わるので右へ2
となる
もし、1 2 3 4 2 だと、真ん中の3は1 2 3,3 2 1の両方が出来るのでサイズ3が答えになる。
で、問題の左右のサイズだけど、ここは両端累積和を使う。例えば、1 2 3 2 1 なら、
1 2 3 の3の時点で左にいくつまで伸びるかは、 1 2の時点の連続数を確認して、次が3以上だったら1 2 3と左に連続。次が2で1 2 2 だったら連続数は2。1だったら連続数は1 2 1 の1。
ということで、直前の累積数より大きければ +1。そうでなかったら自分自身を当てはめるという累積和を左右両方からやって、左側への連続数と右側への連続数を求める。それで、その2つのうち小さい方がその数を中心としたときの連続数の最大値。
それを全部の位置で求めて最大値を求めましょう
最小値の最大値とかだから二分探索を使うのかとか少し迷走してしまって、時間をとってしまった。