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

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

部分列

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 の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複…

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

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

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

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

AtCoder AGC 027 E - ABBreviate (1300 点)

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

Codeforces 502 C - The Phone Number

LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …

AOJ 2727 M and A (200)

これ、問題文を一目見て簡単な問題だと気づけるようになるには、それ自体のトレーニングが必要そうなん 問題へのリンク 問題概要 文字列 S, T が与えられる。 S のうち偶数番目だけを抜き出してできる文字列を S1 S のうち奇数番目だけを抜き出してできる文…

CS Academy 079 DIV2 E - Smallest Subsets

CS Academy 079 DIV2 E Smallest Subsets 問題概要 N 個の整数 S[0], S[1], ..., S[N-1] が与えられる。これらの部分和 (2N 通り) を小さい順に K 個出力せよ。 1 <= N <= 105 1 <= K <= min(2N, 105) -109 <= S[i] <= 109 解法 S[i] として負の値もあるのが…