[解法] 結論から言えば、拡張ダイクストラというものをする。なにを拡張するのかというと、ノードの数である。 そもそもダイクストラをただ単に移動する最短距離や最小コストを得るものとして捉えるのではなく、 最初の状態から最後の状態 になるための最小…

[問題] 問題文は以上の通り。 画像は E8さんのTwitterから拝借。 問題の概要は、「K+1個にバラす時、全てがx以上となる最大のxを見つける」というもの。言い換えれば、最小値の最大値(限界、境界)を見つけるものだ。 なぜ最小の最大 or 最大の最小 は二分探…

DFSの実装で手間取ったのでメモ。 未だに、再帰はイマイチ苦手。 大事なところ 今までdfsを実装する時、"上から下に"行く処理しか書いていなかった。 今回は下から上に上がる(戻る)時にも処理をする必要がある。 木構造の絵を書いてみるとわかる。 具体的に…

CODE FESTIVAL 2014 決勝のE問題、常ならずグラフを解いた。 過去に問題を見て、解説をみて理解できなかったが、今回は解説を見てすんなり理解したので成長を感じた。 解法 結論からいうとDP dp[i][0または１]:= R[i]まで見て現在(上昇中 0 or下降中 1)の時…