問題 頂点のグラフのいくつかの頂点に、以下のような制約を満たすように色を塗る。 タイプ1：ある頂点に色を塗るとき、既に頂点に色が塗られてなければならない タイプ2：ある頂点に色を塗るとき、既に頂点に色が塗られていてはいけない 全ての制約を満たす…

問題 有効グラフをたどって訪れることができるノードの最大数を求める。 この操作は2回行えるが、重複したノードは一度しか数えない。 考察 強連結成分分解を行い、相互に行き来可能なノードの塊を一つのノードとみなしたDAGを考える。 DAGの各ノードのスコ…

問題 0、1でできた文字列を連結してできる長さの文字列のパターン数を求める。 同じ文字列を何度使ってもよい。 atcoder.jp 考察 NFAを用いた問題の変換 文字列の長さの最大値をとし、次のような非決定性有限オートマトンを考える。 状態 {末尾文字を示す状…

問題 aを個、bを個 、zを個使ってできる文字列のうち、同じ文字が隣合わないものの個数を求める。 atcoder.jp 考察 ここでは、同じ文字列が隣り合うことを衝突と呼ぶ。 文字目までのアルファベットを使ってできる文字列で、衝突が回発生するもののパターンを…

問題 頂点の木を書く。 木を書いている途中で、すでに書いている全ての辺が連結になるような書き方の数を求める。 atcoder.jp 考察 根付き木の根からの生やし方の数を考える。 根付き木のノード数が1のとき1通り。 根の個の子を根とする部分木のノードの数が…

問題 建物のH階部屋1から1階部屋1に移動するパターンを求める。 同じフロアでは部屋はなら隣接していて、同じ部屋は2回通れない。 フロア間は同じ番号の部屋へ一方方向に降りるだけ。 atcoder.jp 考察 フロア内の移動 任意の部屋からスタートし、同じ部屋を…

問題 円の集合のうち、を満たすような円の列の最大の長さKを求める。 ここで、とは円がstrictlyに円の内部にあることを意味する。 atcoder.jp 考察 円の左右の端の座標をとすると、条件を満たす円の列は、 を満たす。 すなわち、になるよう円の列をソートす…

問題 直線上に並んだターゲット全てにボールを当てるまでの回数の期待値を求める。 ボールを狙った座標とその両隣それぞれに1/3の確率でボールが飛んでいく。 atcoder.jp 考察 なので、dp[s] = (sが1の座標にターゲットが残っているときの期待値)とする。 に…

問題 iとwからなる文字列から、連続するiwiを抜き取れる回数の最大値を求める問題。 文字列の途中から抜き出すと、その左右の文字列が連結され、操作を続けられる。 atcoder.jp 考察 文字列の区間の部分文字列をと表記する。からiwiを取り出せる回数の最大値…

問題 与えられた文字列の空文字列を除く部分文字列のうち、辞書順でK番目のものを求める。 ただし、出現場所の異なる部分文字列でも、文字列として同一なら区別しない。 atcoder.jp 考察 辞書順に並べたK番目を求めるので、先頭から文字を決定したい。 先頭…