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

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

CodeforcesR1700

Codeforces Round 824 (Div. 2) D. Meta-set (R1700)

なんとか通した。結構迷走した。 問題へのリンク 問題概要 0 と 1 と 2 のみからなる の行列が与えられる。これらの行列のある 3 つの行が good であるとは、「どの列についても、それら 3 行の値がすべて等しいか、すべて互いに異なる」という条件を満たす…

Educational Codeforces Round 9 C. The Smallest String Concatenation (R1700)

すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…

Codeforces Round #609 (Div. 1) A. Long Beautiful Integer (R1700)

こういうのは、いかにシンプルにできるか... 問題へのリンク 問題概要 桁の整数 が与えられる (文字列として)。leading zero はない。整数 が与えられる。 以上の整数 であって の 桁目と 桁目の値は等しい という条件を満たす最小値を求めよ。 制約 考えた…

Codeforces Round #479 (Div. 3) F. Consecutive Subsequence (R1700)

教育的で楽しい 問題へのリンク 問題概要 長さ の数列 が与えられる。数列中の部分列 (連続でなくてよい) であって、連続する自然数となっているもののうち、最長のものを求めよ。 また、それを復元せよ (添字を答える)。 ex: (3, 3, 4, 7, 5, 6, 8) -> (3, …

Educational Codeforces Round 73 D. Make The Fence Great Again (R1700)

いかにも Greedy にできなさそうなので DP!!! 問題へのリンク 問題概要 長さ の整数数列 が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。 項目を 1 増加させるのに要するコストは で…

Codeforces Round #584 (Div. 1 + Div. 2) D. Cow and Snacks (R1700)

面白かった! 問題へのリンク 問題概要 組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。 「これまでに登場した整数」を表す集合を とする 各 i について、 がとも…

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) D. Valid BFS? (R1700)

こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …