drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder200点 AGC-A 二次元グリッド 最適化の考察：最適解の形を考える 競技数学色強め 茶色diff 駒(コマ)や石やコインを扱う問題 高校の頃とかに「グリッドの左上から右下まで行く最短路が何通りあるか」みたいな問題に親しんでいれば、自然に思えるかもしれない 問題へのリンク 問題概要 のグリッドがあって、最初は駒は左上隅に置かれていた。 駒が上下左右に動きながら右下隅まで移動した。駒は同じマスを何度も通った可能性もある。 駒が一度でも通った場所が黒く塗られている。黒く塗られた盤面が与えられて、駒が「右」と「下」にしか動いていないかどうかを判定せよ。 制約 与えられた黒塗り盤面を実現するような駒の動きが存在することは保証される。 考えたこと 以下のことが同値であることはよく知られている 駒は左上から右下へと最短経路を移動した 駒… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F03%2F26%2F203100" title="AtCoder AGC 007 A - Shik and Stone (茶色, 200 点) - けんちょんの競プロ精進記録" 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/20190326202413.png Hatena Blog https://hatena.blog 2019-03-26 20:31:00 rich https://drken1215.hatenablog.com/entry/2019/03/26/203100 1.0 100%