問題 次の条件を満たす整数行列が構築可能なら1つ求める。 行のbitwise-or/bitwise-andが 列のbitwise-or/bitwise-andが atcoder.jp 考察 bitwise-or/bitwise-andなので、桁ごとに独立して考えてよい。 桁毎に分けると、は のいずれか。 そのように考えると…

問題 段階の照明の明るさを2種類のボタンで切り替える 明るさを1つあげる。現在の明るさがなら次の明るさはになる 前もって決めた明るさにする。 最善のを決めたときに、明るさをと順に切り替えるときのボタンを押す回数の最小値を求める。 atcoder.jp 考察 …

問題 直線上を座標に並んだ体のロボットは、それぞれ次の操作が可能である。 今いる座標から、座標の空いている好きな方に移動する 座標が0以下でゴールになる。体のロボットの順位としてありえるパターンを求める。 考察 でがよりも先にゴールするとき、座…

問題 整数列が与えられ、を、 を満たすようにとる。に対し、整数列の「 の最大値」の最小値を求める。 考察 ある区間で、「[tex: C{i+1} - C_i] の最大値」の最小値を考える。また、[tex: C{i+1} - C_i]はグラフの変化率と考えることができる。 はなるべく小…

問題 十分多い金貨と枚の銀貨を持って都市1にいる。 本の線路はそれぞれ、都市間を走り、運賃は銀貨枚、時間は分かかる。 各都市の料金所で分かけて金貨1枚と銀貨枚を交換してくれる。 各都市に移動するのにかかる最小時間を求める。 atcoder.jp 考察 都市の…

問題 座標にイチゴの乗った長さのケーキに対して、回目の操作後のケーキの美しさを求める。 操作は、 * 座標にイチゴがないなら、座標にイチゴを乗せる * 座標にイチゴがあるなら、座標のイチゴを取り除く ケーキの美しさは、次の値の最大値として定義する。…

問題 頂点の有効グラフの頂点の からへ向かう辺が存在するか からへのパスが存在するか がわかっている。この条件を満たすからへ向かう辺の集合があれば求める。 atcoder.jp 考察 これらの条件を満たさないのは、 からへのパスがないが、からへの辺があり、…

問題 個の重さの異なるシャリと個の重さの異なるネタからそれぞれ2つずつ選び、重さの同じ寿司を2つ作ることができるか判定する。 atcoder.jp 考察 問題の制約から、完成する寿司の重さが高々[tex: 2\times 106]であることがわかる。重さの寿司ができるかを…

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

問題 頂点のグラフのいくつかの頂点に、以下のような制約を満たすように色を塗る。 タイプ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番目を求めるので、先頭から文字を決定したい。 先頭…