問題 atcoder.jp 考察 その他のある色についての解を、として計算する。 を通らないパスとは、色がでないノードの単純パスのうち、上に色がのノードが存在しないようなものである。 このようなノードのペアの数は色を含まない部分木のうち、色を含まないよう…

問題 人のうち、高橋くんとその他人の時刻の差（日付は気にしない）は時間である。人のうちの任意の2人の時差の最小値をの最大値を求める。 atcoder.jp 考察 より、ならばそれぞれ、その他においてである。 時差が人が2人以上（ただしのときの1人は高橋くん…

問題 長さの数列[A_1, \cdots, A__N]から個の要素を選んで部分数列を作る。 要素を選ぶときは、要素ごとに以上開ける必要がある。 辞書順で最小の数列を求める。 考察 のとき、部分列を作ることはできない。 以下、を仮定する。 同じ数字が複数あり、どちら…

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

問題 個の敷地（番目の敷地の範囲は、コストは）がある。 座標にあるビルのコストは、その座標を含む敷地のコストの和。 軒のビルのコストを求める。 atcoder.jp 考察 考える平面が広いので、座標圧縮を行う。 以降、圧縮後の座標で考える。 あるビルのコス…

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

問題 人の参加者が、個の卓でそれぞれ2人ずつ対戦する。 卓では番号と の人が対戦する。 はじめ、人の参加者は1からの番号が順番についていて、対戦が終わると番号が1増える（は1になる）。 ラウンド実施し、同じ2人が対戦するカードが存在しないような卓の…

問題 与えられた頂点の木の頂点1から頂点に、次の条件を満たすように1からの順列の番号をつける。 任意の頂点の組で、頂点と頂点の距離が3なら、かが3の倍数になる。 atcoder.jp 考察 を表す。 なら、積が3の倍数になる。なら、和が3の倍数になる。それ以外…

問題 体の所持モンスターから4匹以上、体のお助けモンスターから0匹以上選んでモンスターを合成する。 合成されたモンスターの強さは、(使用したモンスターの魔力の和)/(使用したモンスターの質量の和)で定義される。 合成できるモンスターの最大の強さを求…

問題 頂点辺の重みつき単純連結無向グラフが与えられる。 辺は頂点とを結び、重みはである。 辺からそれぞれについて、その辺を含む最小の重みの全域木を求める。 atcoder.jp 考察 与えられた連結グラフの最小の重みの全域木とその重みを求める。 この全域木…

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

問題 グリッド上の池に葉がいくつか浮かんでいる。カエルは、同じ行/列にある葉を好きに行き来できる。葉を行き来できなくするよう、以外の除く時の最小枚数を求める。 atcoder.jp 考察 葉からたどり着ける葉の集合と、葉からたどり着ける葉の集合が互いに共…

問題 個の宝石があり、個目の宝石の価値は（負の可能性もある）である。以下の操作を0回以上したとき、残っている宝石の価値の総和の最大値を求める。 正整数を選び、の倍数の宝石を全て割る atcoder.jp 考察 各宝石を割らないグループと割るグループに分類…

問題 個のタイヤと本の木の完全マッチングの個数パターン数の偶奇を求める。 atcoder.jp 考察 完全マッチングの数え上げは、01行列のpermanent値に一致し、これはNP困難であることが知られている。行列のpermanent値は ここで、のdeterminant値を見てみると…

問題 人がいて、番目の身長はである。 「2人の番号の差の絶対値と、身長の和が等しい」ようなペアは何通りあるか。 atcoder.jp 考察 2人の番号をとする。 すると、ペアの制約は、になる。 番号を分離すると、となる。 よって各番号について、なるの数を数え…

問題 初項、公差、項数の数列がある。 十進法でを順に結合してできる数を整数で割ったあまりを求める。 atcoder.jp 考察 全ての要素が桁の整数である公差、長さの等比数列については、 とすると、 。 また、より、 で求められ、。行列の塁上は繰り返し2乗法…

問題 行列が与えられる。次の操作を行ってをに変換するとき、その途中経過であるを1つ求める。 の行ごとに好きに並び替えてにする の列ごとに好きに並び替えてにする の行ごとに好きに並び替えてにする atcoder.jp 考察 の満たすべき条件を考える。 まず、の…

問題 とがある。以下の操作を回以下行って、にできるか判定する。 を選択し、との値を入れ替える atcoder.jp 考察 が昇順であると仮定する。を昇順にソートして比較するとき、を満たさないが存在すれば、実現不可能である。以下、これは満たされていると仮定…