drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder300点 AGC-A Greedy 区間 考察：区間ごとに分割して考える 数列 Greedy:後によいものを残す・今が良いほど未来も良い 茶色diff ジグザグ >< 左右からそれぞれ走査する 個人的には超苦手系。。。 でもちゃんと Greedy 思考を整理すればできる。こういうのは Greedy 思考の「型」を理解することが大事そう。 問題へのリンク 問題概要 長さ の数列 が与えられる。 を何箇所かで切って、 の連続した部分であるようないくつかの数列に分ける。 このとき、各区間については「単調非減少」または「単調非増加」になっている必要がある。 最小で何個の区間に分ければ良いかを求めよ。 制約 考えたこと 基本的には下図のようなことがしたい！！！ でも頭が混乱するケースとして、以下のようなケースがある！！！ 30, 40, 50, 60, 55, 65, 75, 85 これは正解… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F03%2F28%2F014100" title="AtCoder AGC 013 A - Sorted Arrays (茶色, 300 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20190326/20190326205537.png Hatena Blog https://hatena.blog 2019-03-28 01:41:00 rich https://drken1215.hatenablog.com/entry/2019/03/28/014100 1.0 100%