けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2020-03-10から1日間の記事一覧

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D)

このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい!!! 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…

Educational Codeforces Round 83 E. Array Shrinking

区間 DP な問題って、あまり見なくなったなと。貴重なので記録。 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、…

Educational Codeforces Round 83 G. Autocompletion

頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…