問題 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番目を求めるので、先頭から文字を決定したい。 先頭…

2019年2月17日に東京ドームホテルで行われた全国統一プログラミング王決定戦の本戦イベントに参加してきました。 主催、共催は日本経済新聞社とAtCoder。 僕は201~500位での参加なのでトークセッション、表彰式、エキシビション、懇親会に参加した。 はじま…

2018.10.13 21:00~のAtCoder AGC028に参加 結果はABの2完。 A - Two Abbreviations与えられた2つの文字列を元に、条件を満たす文字列の最小の長さを出力する問題。 条件は 答えの文字列の長さはそれぞれの文字列の長さの整数倍 答えの文字列を個に区切った個…

2018.10.06 21:00~のAtCoder ABC112に参加しました。 結果はDを1WAで全完でした。47分かかってしまったのでもっと早くしたいです。 A - Programming Education 1つ目の入力が1か2かで分岐。出題形式がちょっと珍しい気がしました。 B - Time Limit Exceeded …