数値を表す文字列同士の比較
まさに遅延評価セグメント木の練習問題!!! 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…
Codeforces
探索問題
応用的な探索
解に確実に含まれる要素を列挙する
最短路問題
BFS
グラフ問題
DFS
DP
DP値:文字列
グラフの辺を分割する
辞書順
辞書順最小なグラフ探索
数値を表す文字列同士の比較
各kに対して
整数値のconcatを考える問題
CodeforcesCombined
CodeforcesR2600
DFS木やBFS木を考察する
勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…
文字列を値にもつ DP、ご無沙汰!!! 問題へのリンク 問題概要 本のマッチ棒を使ってできるだけ大きな数値を作りたい。 マッチ棒で 1, 2, 3, 4, 5, 6, 7, 8, 9 を作るのにそれぞれ 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒が必要である。 ただし各桁に用い…