まさに遅延評価セグメント木の練習問題！！！ 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…

勉強になった！！！！！ 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

文字列を値にもつ DP、ご無沙汰！！！ 問題へのリンク 問題概要 本のマッチ棒を使ってできるだけ大きな数値を作りたい。 マッチ棒で 1, 2, 3, 4, 5, 6, 7, 8, 9 を作るのにそれぞれ 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒が必要である。 ただし各桁に用い…

詰め切るの大変だった！ 問題へのリンク editorials 問題概要 '0'〜'9' からなる長さ の文字列 が与えられる。 これらの文字列をいくつかの連続する部分文字列に分ける。次の条件を満たす必要がある。 各部分文字列を数値とみなしたとき、strictly に単調増…