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

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

数列の構築

AtCoder AGC 053 A - >< again (水色, 400 点)

自明な上界を達成できるパターンだった! 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…

AtCoder ABC 126 F - XOR Matching (青色, 600 点)

600 点問題ともなると、さすがに正解者数も少ない。 色んな人が色んな構築してそうだけど、僕なりの方法をば。 問題へのリンク 問題概要 を 以上の整数とする。 以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、 となるよう…

AtCoder AGC 006 B - Median Pyramid Easy (青色, 400 点)

これの Easy バージョン。すごく楽しくて好き!!!!! Easy:操作の結果が所望になる入力を求める逆問題 Hard:操作に入力を与えた結果を求める問題 という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と …

AtCoder AGC 031 C - Differ by 1 Bit (黄色, 800 点)

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…

AtCoder AGC 008 D - K-th K (黄色, 800 点)

実装は手こずったものの、それなりに自信のある Greedy を提出できて一発 AC できてよかった 問題へのリンク 問題概要 1 〜 の値を 個ずつもつ長さ の数列であって、 各 について、 番目の値が 個目の である という条件を満たすものを 1 つ構築せよ。条件を…

AtCoder ARC 091 E - LISDL (青色, 700 点)

問題へのリンク 問題概要 1, 2, ..., N を並べ替えてできる列であって、以下の条件を満たすものがあるかどうか判定し、あればその例をひとつ構成せよ: 最長増加部分列の長さは A 最長減少部分列の長さは B 制約 1 <= N, A, B <= 3 × 105 解法 LIS and LDS と…