CodeChef June Challenge 2018: Archi and Tree
CodeChef June Challenge 2018の問題: Archi and Tree (Code: ARCTR)
問題ページ: https://www.codechef.com/JUNE18A/problems/ARCTR
問題概要
各辺がそれぞれの長さを持つ、個の頂点を含む木がある。
番目の辺はとを繋ぐ、長さの辺である。
この木の上に個の流れ星が流れる。
具体的に、番目の流れ星は時間に頂点からスタートし、速度でまっすぐに向かい、頂点に到達したら消える。
各頂点で最初にいずれかの流れ星が観測できる最小の時刻を出力せよ。観測できない頂点については-1を出力せよ。
CodeChef June Challenge 2018: Expected Buildings
CodeChef June Challenge 2018の問題: Expected Buildings (Code: BUILDIT)
問題ページ: https://www.codechef.com/JUNE18A/problems/BUILDIT
問題概要
1つの円があり、円の中心にChefが立っている。
この円を周囲は個の区間に分割され、各区間に1, 2, ..., hと時計回りに番号が付けられている。そこに個の建物が存在し、番目の建物は区間内に含まれている。
また、円の中心に立っているChefの視界範囲はであり、円の周囲の連続した個の区間を一度に見ることができる。
今回、Chefが向く方向をランダムに決定する。
各についてが決められており、視界に(mod )が含まれる確率は()である。
ただし、がでかいため、は最初の個しか与えられず、については係数を用いて以下の式で計算できる。
ランダムな方向を向いた時のChefの視界の範囲に含まれる建物の数の期待値をmodulo 163577857で求めなさい。
CodeChef June Challenge 2018: Ways to Work
CodeChef June Challenge 2018の問題: Ways to Work (Code: WRKWAYS)
問題ページ: https://www.codechef.com/JUNE18A/problems/WRKWAYS
問題概要
人が、他人とかぶらないように1日ずつ選択し、計日働く。
各々には締め切りがあり、番目の人の締め切りはとなっている。つまり、他人とかぶらないようにの中から働く日時を選択しなければならない。
この時、を適切に選ぶことによって、人の日程の組み合わせの通り数をちょうど通りにする必要がある。
となる時、が最小となる時のの各値はいくらになるか?解のうちの1つを出力せよ。
CodeChef May Challenge 2018: Rubber Band
CodeChefのMay Challenge 2018の問題: Rubber Band (Code: RUBBER)
問題: https://www.codechef.com/MAY18A/problems/RUBBER
コンテスト中解けなかった問題。解法メモ。
問題概要
ボード上に個のnailが固定されている。そこに、個の線分で輪っかが構成された1つのrubber bandが存在している。
rubber bandをnailと交差しないように自由に形を変形することで、個のnailとrubber bandを完全に分離(つまり、rubber bandの輪の中にnailが存在しない状態を実現)できるかを判定せよ。
AGC024 - D問題: Isomorphism Freak
問題: D: Isomorphism Freak - AtCoder Grand Contest 024 | AtCoder
1100点だけど、実質700, 800点問題な感じ。
コンテスト中に解けないといけなかった問題。猛省。
問題
木を何色かで彩色したものの内、ある色で彩色された頂点を根とした根付き木は全て同型となるものを良い彩色と呼ぶ。また、木の良い彩色の中の色の種類が最小値をカラフルさと呼ぶ。
この木のある頂点と新たな1つの頂点を繋ぐ操作を何回か繰り返すことで達成できるカラフルさの最小値はいくらか?
そして、カラフルさが最小となる時の木の内、葉の数が最小となる時の葉の数はいくらか?
CodeChef May Challenge 2018: Edges in Spanning Trees
CodeChefのMay Challenge 2018の問題: Edges in Spanning Trees (Code: EDGEST)
問題: https://www.codechef.com/MAY18A/problems/EDGEST
問題
1からNの番号がついた個の頂点を含む2つの木が与えられる。
木に含まれる各辺について、以下の条件を満たす上の辺の数を計算せよ。
- 木から辺を除去しを追加したグラフが木になる
- 木から辺を除去しを追加したグラフが木になる
CodeChef May Challenge 2018: S-T Mincut
CodeChef の May Challenge 2018 の問題: S-T Mincut (Code: STMINCUT)
問題: https://www.codechef.com/MAY18A/problems/STMINCUT
問題
の行列が与えられる。
この行列の各要素の値を増やすことで次の条件を満たす必要がある。
- 個の頂点のグラフの中で、頂点と頂点の間の最小カットのコストがとなるグラフが存在する
この条件を満たすように行列の各要素の値を増加させた時に、その増加させる値の合計を最小いくらにできるかを計算せよ。