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

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

数値を表す文字列同士の比較

ACL Beginner Contest E - Replace Digits (青色, 500 点)

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

Codeforces Round #584 (Div. 1 + Div. 2) F. Koala and Notebook (R2600)

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

AtCoder ABC 118 D - Match Matching (青色, 400 点)

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

TopCoder SRM 402 DIV1 Hard - IncreasingSequence (本番 2 人)

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