問題 ある食堂では日目、日目、日目に料理が提供される。 社員それぞれについて、以下の条件で食堂に通うとき、回目に利用するまでに料理を食べる回数を求める。 初めて食堂を利用する日は日目である。 初めて食堂を利用して以降、料理が提供される日は必ず…

問題 王国に個の街がある。 魔王が番目の街にモンスターを匹送ると、王国にのダメージを与える。 魔王は個の拠点があり、合計のモンスターを番目の街に好きな配分で送り込める。 王国に与えられダメージの最大値を求める。 atcoder.jp 考察 次のようなdpを考…

問題 偏りのない個の6面サイコロがあり、番目のサイコロの番目の面には[A_{i,j}]が書かれている。 はじめ、好きなサイコロを1つ選んで出た目をとする。以降、次の操作を可能な限り繰り返す。 好きなサイコロを1つ選んで出た目をとする。ならとし、そうでない…

問題 人の社員をいくつかのグループに分けるときのスコアの最大値を求める。スコアはで与えられる。 atcoder.jp 考察 要素数の集合の部分集合の部分集合の列挙はでできる。 集合だけで問題を解いたときの解とする。のとき、。のとき、 で求められる。 の全て…

問題 有効グラフをたどって訪れることができるノードの最大数を求める。 この操作は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番目を求めるので、先頭から文字を決定したい。 先頭…