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

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

制約:複数系列の長さの合計が10^5以下

AOJ 4003 演算装置の接続 (PCK 2022 本選 4)

次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…

AtCoder ABC 324 C - Error Correction (茶色, 300 点)

C 問題としてはかなりハードな問題であった。 問題へのリンク 問題概要 個の文字列 のうち、文字列 との編集距離が 1 以下であるものの個数を求めよ。 なお、文字列 と文字列 の編集距離が 1 以下であるとは、以下のいずれかが成り立つことを指す。 である …

AtCoder ABC 324 E - Joint Two Strings (緑色, 500 点)

問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題! 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…

TTPC 2023 H - 404 Chotto Found

Suffix Array 上をひたすら頑張って探索する感じ 問題へのリンク 問題概要 個の文字列 が与えられる (これらの文字列はすべて英小文字のみからなる)。 以下の条件を満たす文字列 の個数を求めよ。 英小文字のみからなる のうち、ちょうど 1 個の部分文字列で…

AtCoder ABC 302 F - Merge Set (水色, 500 点)

下手を打つと密なグラフになって TLE してしまう!! スーパーノードを作ることでグラフを sparse にするテク! 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…

AtCoder ABC 280 Ex - Substring Sort (5D, 銅色, 600 点)

Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった! 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…

AOJ 2644 Longest Match (JAG 夏合宿 2014 day4-F) (700 点)

Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…

AOJ 2863 Separate String (JAG 模擬地区 2017 H) (500 点)

めちゃくちゃ面白かったし勉強になった! 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…

AtCoder ARC 105 D - Let's Play Nim (青色, 600 点)

これ結構好き! 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき):コインが入…

Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400)

むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…

AOJ 3196 Increasing Sequence (AUPC 2020 day1-D)

in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…

AtCoder ABC 175 F - Making Palindrome (橙色, 600 点)

こういう重たい実装を確実にこなせるように...なりたい! 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…

Codeforces Round #626 (Div. 1) C. Instant Noodles (R2300)

割と TLE に関して危険な橋をわたっていたのかもしれない。でも、ロリハとかしなくても大丈夫だった。 問題へのリンク 問題概要 左頂点数と右頂点数がともに であるような二部グラフが与えられる。二部グラフの辺数は である。 右頂点 には値 がある。今、左…

Codeforces Round #615 (Div. 3) E. Obtain a Permutation (R1900)

こういうのをちゃんと解けるようになったのは成長! 問題へのリンク 問題概要 (意訳) 以下の 個のクエリに答えよ。 番目のクエリでは、数列 が与えられる。この数列に以下のいずれかの操作をほどこして、 となるようにしたい。その最小回数を求めよ。 を任意…

Codeforces #613 (Div. 2) E. Delete a Segment (R2300)

嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…

Xmas Contest 2019 J - Sub-Post Correspondence Problem

信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…

みんなのプロコン 2017 C - 検索 (400 点)

頑張った 問題概要 個の文字列が与えられて そのうちの指定された 個についてについては、その prefix となっている 指定されていない 個については prefix にはなっていない ような最短の文字列を求めよ。存在しない場合は -1 とせよ。 制約 個の文字列の長…

AOJ 2892 しりとり圧縮 (AUPC 2018 day3 D)

迷走しないようにしたい問題。 問題へのリンク 問題概要 banana at tomb but tos sound does some のようなしりとりが与えられる。同じ文字で始まるところは 1 つにつぶすことができる。上の例で言えば (banana at tomb but) (tos) (sound does some) という…