betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング F - Sugoroku 解法 個の連続するゲームオーバーマスがある場合はゴール不可能なので、そうでないことを仮定します。「最小ターン数」と「辞書順最小」、それぞれに注目します。 ゴールするための最小ターン数はDP等で求めることができます（後で具体的に説明します）。そのターン数が であると求められたとします。このとき、 ターンでゴールできる辞書順最小の移動パターンはどうやって求めれば良いでしょうか。 辞書順最小の基本は「前から貪欲」です。ここでの「貪欲」とは、条件を満たす（ ターンでゴールする）ことが可能な範囲で、今考えているターンの移動をなるべく小さくする…ということを前から順番に繰り返して… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F11%2F25%2F225556" title="AtCoder Beginner Contest 146 F - Sugoroku - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20M Hatena Blog https://hatena.blog 2019-11-25 22:55:56 rich https://betrue12.hateblo.jp/entry/2019/11/25/225556 1.0 100%