hitoare https://blog.hatena.ne.jp/hitoare/ hitoare日記 https://hitoare.hatenablog.com/ 競技プログラミング AtCoder ABC 問題リンク atcoder.jp 問題概要 \(H+1 \times W \)マスのグリッドがある。 グリッド上は右か下に移動できる。 ただし、上からk行目からk+1行目に移動する時、左から\(A_k\)マス目から\(B_k\)マス目の区間で下方向に移動するのは禁止されている。 一番上のWマスのうちのいずれかからスタートして、k+1行目に到達するまでの最小移動回数を\(1 \leq k \leq H\)に対して求めよ。到達不可能ならば-1を出力せよ。 解法 縦移動の回数は決まっているので、横方向の最小移動回数を求める。 各行のWマスに対し、「その地点に到達するのに必要な横移動の最小回数」を上か… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhitoare.hatenablog.com%2Fentry%2F2020%2F08%2F29%2F230642" title="F - I hate Shortest Path Problem(AtCoder Beginner Contest 177) - hitoare日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-08-29 23:06:42 rich https://hitoare.hatenablog.com/entry/2020/08/29/230642 1.0 100%