drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ JOI JOI予選・二次予選 AtCoder AOJ 最適化の考察：最適解の形を考える 二分探索 最適化の考察：変形しても悪化しない Greedy：先に進むほど新たな選択肢が挿入される Greedy 数直線上のN点の問題 単純化：操作の流れを単純化して考える 最大値の最小化 順序の工夫：後ろから見る NoviSteps2D 最適化問題 最小コスト 最短路問題 JOI難易度8 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場がある。各工場は座標 () にあって、作業量が となっている。 人の作業員がいる。時刻 0 にはすべての人が座標 0 で待機している。各人は 1 秒で 1 の作業ができる (どの工場においても) 1 秒で 1 だけ移動できる すべての工場のすべての作業が完了するのに要する時間の最小値を求めよ。 制約 考えたこと：二分探索っぽい それぞれの作業員の行動過程はかなり複雑なもの… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F12%2F29%2F030000" title="JOI 二次予選 2021 D - 安全点検 (AOJ 0694) (2D, 難易度 8) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2020-12-29 03:00:00 rich https://drken1215.hatenablog.com/entry/2020/12/29/030000 1.0 100%