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

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

辞書順

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…

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 1399 Sixth Sense (ICPC アジア 2018 K)

「辞書順最大」という条件さえなければ典型的な Greedy マッチングではあるね。「辞書順最大」になっても頑張れば基本に忠実にできる。ややこしいけど頑張ればできる感じかな。。。 問題へのリンク 問題概要 人対 人の対戦割当を決めたい。敵が 1 回戦、2 回…

AtCoder AGC 029 C - Lexicographic constraints (700 点)

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

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

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

AtCoder AGC 026 E - Synchronized Subsequence (1600 点)

こういうのちゃんと解き切れるようになりたい... なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう... 問題へのリンク 問題概要 (AGC 026 E) …

AtCoder ARC 097 C - K-th Substring (300 点)

本番出てなかったけどこれは... ARC 097 C K-th Substring 問題概要 文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。 制約 1 <= |s| <= 5000 1 <= K <= 5 解法 K が小さいのが怪しい。 冷静に考えると、辞書順 K …

CS Academy 079 DIV2 C K - Inversions

CSA 079 DIV2 C K Inversions 問題概要 1 ~ N の順列で転倒数が K となるもののうち、辞書順最小のものを求めよ。 2 <= N <= 105 0 <= K <= NC2 やったこと 辞書順最小ということで、とにかく今見ている部分を極力小さくする Greedy を行う。 具体的には、…

CS Academy 069 DIV2 B - Reverse Subarray

B なのに難しかったのん。 CSA 069 DIV2 B Reverse Subarray N 要素からなる数列が与えられる。 ここから連続する区間を reverse することで元の数列全体が単調非減少となるようにしたい。 そのような区間の選び方は何通りあるか? またそのような区間のうち…