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

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

グラフや盤面の数え上げ問題

diverta 2019 F - Edge Ordering (1200 点)

こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …

AtCoder AGC E - Go around a Circle (1500 点)

本番これを間に合わせられなかったのが悔しい 問題へのリンク 問題概要 円周を 等分して、それぞれの弧を赤か青に塗る方法のうち、 'R' と 'B' のみからなる長さ の文字列 が与えられて 円周上のどの端点から出発しても弧を順番に左右どちらかに 回たどって…

AtCoder ABC 113 D - Number of Amidakuji (400 点)

あみだくじ 問題へのリンク 問題概要 縦棒の個数が 、横棒が縦方向に 刻みのあみだくじであって、 番目からスタートすると 番目に到着するようなものを数え上げよ。 制約 考えたこと いかにも DP という感じではあるね。 dp[ i ][ j ] := 縦棒を上から i 刻…

AtCoder ABC 122 D - We Like AGC (400 点)

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

Educational Codeforces 62 E - Palindrome-less Arrays

楽しかった 問題へのリンク 問題概要 未完成の数列 が与えられる。未完成部分には が書かれている。完成部分には 以上 以下の整数が書かれている。 のところを 以上 以下の整数を埋める方法であって、整数列が奇数長の回文を含まないものは何通りあるか? 制…

AOJ 2935 赤黒そーるじぇむ (RUPC 2019 day3-F)

楽しい!!!好き!!! 問題へのリンク 問題概要 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 通りの方法のうち、以下の条件を満たすような方法が何通りあるか で割ったあまりを求めよ。 どの赤い頂点も、なんらかの黒い頂点とつながって…

MUJIN 2018 H - タイル張り (1000 点)

コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だったのん... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか? (99824…

SoundHound 2018 本戦 C - Not Too Close (800 点)

好き系。本番解きに行ったけど、もっとサクッと通せればよかった。 問題へのリンク 問題概要 頂点の無向グラフ (頂点の番号は 1 〜 ) であって、以下の条件をすべて満たすものの個数を 1000000007 で割ったあまりを求めよ。 頂点 1 と 2 との間の最短距離が …