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

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

2018-02-15から1日間の記事一覧

CS Academy 069 DIV2 E - The Wall

とにかく整理に苦労したけど、本番中に通せて嬉しかったん CSA 069 DIV2 E The Wall 図は N = 5 の場合である。 N 段の壁を作りたい。ただし、どのレンガも下にあるレンガが完成してからでないと積み上げられない。 N 段の積み上げる順番の総数はいくらか。1…

CS Academy 069 DIV2 D - Cover the Tree

本番はツリーDPな方向性に走って詰め切れなかったん。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そうなん... ツリーの重心に関する理解が足りてないことがわかったので勉強してまとめたのん。 ツリーの重心分解 (木の重心分解) の図解 - Q…

CS Academy 069 DIV2 C - Build Correct Brackets (最短経路数も一緒に求める最短路!)

まさにこれだったん。 CSA 069 DIV2 C Build Correct Brackets ()()))(())() のようなカッコ列が与えられる。 最小回数flipして正しいカッコ列にせよ。 また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。 ・1 <= 文字列長 <= 2500 まさに最短路…

CS Academy 069 DIV2 B - Reverse Subarray

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