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

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

文字列問題

AtCoder ABC 130 E - Common Subsequence (500 点)

共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…

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

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

AtCoder AGC 001 D - Arrays and Palindrome (1000 点)

楽しかった。 回文系の問題。「〜な条件だと結局全部一緒になる」という問題の雰囲気がどことなく数オリっぽい。 必要条件を頑張って列挙したら実は十分な感じもまた、数オリっぽさと AGC っぽさの両方がある感じ。 問題へのリンク 問題概要 総和が 、長さが…

diverta 2019 C - AB Substrings (400 点)

ペアリングを場合分けしてルールベースで頑張る系の問題、過去に何度もやらかしていて苦手意識が強い 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを任意の順序で連結してできる 通りの文字列のうち、その中に "AB" を連続部分列として含んで…

Codeforces 558 DIV2 D. Mysterious Code (R2200)

部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…

第3回 ドワンゴからの挑戦状 予選 B - ニコニコ文字列 (300 点)

300 点!??? 問題へのリンク 問題概要 '0' 〜 '9' および '?' からなる文字列 S が与えられる。 文字列のニコニコレベルとは、連続部分列であって "2525... 25" となっているものの最長の長さとして定義される。 S の '?' に '0' 〜 '9' を当てはめる方法…

AtCoder AGC 021 D - Reversed LCS (900 点)

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …

AtCoder ABC 122 D - We Like AGC (400 点)

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

AtCoder ABC 124 C - Coloring Colorfully (300 点)

一見複雑だけど、実質 2 通りしかないというやつ 問題へのリンク 問題概要 長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、 0 と 1 が交互に並んでいる状態 にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の…

GCJ 2019 Round 1A C - Alien Rhyme

いい感じの Greedy 問題 問題へのリンク 問題概要 個の文字列 が与えられる。2 つの文字列 について、 の最後 i 文字と、 の最後 i 文字が共通 の後ろから i 文字目も、 の後ろから i 文字目も c である という条件を満たすとき、ラベル (i, c) をつけながら…

AtCoder ABC 122 C - GeT AC (300 点)

これも累積和!!! ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com

AtCoder AGC 006 A - Prefix and Suffix (200 点)

なのでいくらでも何でもできるという感覚 問題へのリンク 問題概要 すぬけ君は次の条件を満たす文字列に興味があります。 長さ 以上である。 先頭 文字が文字列 に一致する。 末尾 文字が文字列 に一致する。 条件を満たす文字列のうち、最も短いものの長さ…

AOJ 2444 Substring (AOJ-ICPC 450 点)

ロリハそのものな問題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…

早稲田大学プログラミングコンテスト WUPC 2019 E - Artist

回文な問題リストに!!! 問題へのリンク 問題概要 × のグリッドが与えられ、各セルには 0 か 1 の値が書かれている。 今、縦方向と横方向に切れ目を入れて、4 つの長方形に分けて、それぞれの長方形を 180 度回転させる操作を行う。 このときに、各行各列…

AtCoder AGC 031 A - Colorful Subsequence (200 点)

高校数学を思い出させてくれる感じの数え上げ問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の部分列であって、すべて異なる文字からなるものの数を 1000000007 で割った余りを答えてください。文字列として同一でも、異なる位置から取り出さ…

AOJ 2934 往復文字列 (RUPC 2019 day3-E)

ロリハの練習!!! 問題へのリンク 問題概要 長さ の文字列 T が与えられる。以下の条件を満たす最長の長さの文字列 S (反転したものを S' とする) を求めよ: S + S'.substr(1) + S.substr(1) + S'.substr(1) + S.substr(1) + ... の最初の 文字が と一致す…

全国統一プログラミング王決定戦 エキシビジョン G - 回文スコア (400 点)

比較的普通の問題っぽい 問題へのリンク 問題概要 文字列 が与えられる。 に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。文字は自由な順序で使用することができ、 に複数回現れる文字は合計でその回数だけ使用します。 長さ の…

CS Academy FII Code #1 B - Sugarel and Substrings

しゃくとり法のいい感じの練習問題 問題へのリンク 問題概要 英小文字のみから成る文字列 が与えられる。 の連続する部分文字列のうち「同じアルファベットが2度以上使われることのない」ものが何個あるかを数えよ (空文字列は 1 個とみなす) 制約 考えたこ…

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 本のマッチ棒が必要である。 ただし各桁に用い…

AOJ 0660 たのしいたのしいたのしい家庭菜園 (JOI 2019 本選 C)

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない」ようにしたい。それが可能となる操…

AtCoder ARC 064 D - An Ordinary Game (500 点)

気づき系。。。 こういうのを一瞬で思いつける人になりたい。 問題へのリンク 問題概要 長さ の文字列 が与えられる。先手と後手とで交互に 文字列中の文字を一文字選んで消していく、ただし 両端は消せない その文字を消すことで「同じ文字が隣り合っている…

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C)

こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…

AOJ 1392 Shortest Common Non-Subsequence (ICPC アジア 2018 D)

ARC 081 E - Don't Be a Subsequence の文字列が 2 個になったバージョン! 問題へのリンク 問題概要 2 つの '0' と '1' で構成された文字列 S, T が与えられる。 S の部分文字列でも T の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複…

AtCoder AGC 029 C - Lexicographic constraints (700 点)

弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…

AtCoder AGC 028 A - Two Abbreviations (300 点)

そろそろまた競プロやっていくぞー!!! 問題へのリンク 問題概要 長さ n の文字列 S と長さ m の文字列 T が与えられる。以下の条件を満たす文字列 X があるかどうか判定し、あるならば X の長さ L として考えられる最小値を求めよ。 (以下において、n' = …

AOJ 2895 回文部分列 (AUPC 2018 day3 G)

すごく大好きな問題! 部分列を走査する考え方をちゃんとわかっていれば自然に解くことができる。 問題へのリンク 問題概要 文字列 が与えられる。 の部分文字列のうち回文となっているものが何通りあるか、1000000007 で割ったあまりで求めよ。 制約 は英小…

AtCoder ABC 110 C - String Transformation (300 点)

ごめんなさい!!!!! コンテスト中に僕が AC した解法は嘘解法でした (てんぷらさんたちに教えてもらいました)!!! 嘘解法 :https://beta.atcoder.jp/contests/abc110/submissions/3251109 S と T の各文字の個数をカウントして、それぞれ個数ベクトル…

AtCoder ARC 081 E - Don't Be a Subsequence (600 点)

部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 (ARC 081 E) 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制…

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

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

AtCoder AGC 027 E - ABBreviate (1300 点)

2 日目:AGC 027 E - ABBreviate (1300 点)https://t.co/mvWcvtxfRz3 で割った余りについて不変量であることは既出。重複を除くために「文字列の部分文字列の数え上げ」的な考え方をするのも恐らく典型。自力で詰め切るのはまだ辛いけど「赤くならないうちは…