日々drdrする人のメモ

今日も明日もdrdr

CodeChef June Challenge 2018: Archi and Tree

CodeChef June Challenge 2018の問題: Archi and Tree (Code: ARCTR)
問題ページ: https://www.codechef.com/JUNE18A/problems/ARCTR

問題概要

各辺がそれぞれの長さを持つ、 {N}個の頂点を含む木がある。
 {i}番目の辺は {a_i} {b_i}を繋ぐ、長さ {w_i}の辺である。

この木の上に {M}個の流れ星が流れる。
具体的に、 {i}番目の流れ星は時間 {t_i}に頂点 {u_i}からスタートし、速度 {s_i}でまっすぐ {v_i}に向かい、頂点 {v_i}に到達したら消える。

各頂点で最初にいずれかの流れ星が観測できる最小の時刻を出力せよ。観測できない頂点については-1を出力せよ。

続きを読む

CodeChef June Challenge 2018: Expected Buildings

CodeChef June Challenge 2018の問題: Expected Buildings (Code: BUILDIT)
問題ページ: https://www.codechef.com/JUNE18A/problems/BUILDIT

問題概要

1つの円があり、円の中心にChefが立っている。
この円を周囲は {h}個の区間に分割され、各区間に1, 2, ..., hと時計回りに番号が付けられている。そこに {N}個の建物が存在し、 {i}番目の建物は区間 {p_i}内に含まれている。
また、円の中心に立っているChefの視界範囲は {x}であり、円の周囲の連続した {x}個の区間を一度に見ることができる。

今回、Chefが向く方向をランダムに決定する。
 {i = 1, 2, ..., h}について {a_i}が決められており、視界に {i, i+1, ..., i+x}(mod  {h})が含まれる確率は {\frac{a_i}{s}}( {s = \sum_{i=1}^h a_i})である。

ただし、 {h}がでかいため、 {a_i}は最初の {K}個しか与えられず、 {i = K+1, ..., h}については係数 {c_i}を用いて以下の式で計算できる。
 {\displaystyle a_i = \sum_{j=1}^K c_j a_{i-j}}

ランダムな方向を向いた時のChefの視界の範囲 {x}に含まれる建物の数の期待値を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

問題概要

 {N}人が、他人とかぶらないように1日ずつ選択し、計 {N}日働く。
各々には締め切りがあり、 {i}番目の人の締め切りは {d_i}となっている。つまり、他人とかぶらないように {1, ..., d_i}の中から働く日時を選択しなければならない。


この時、 {d_1, d_2, ..., d_N}を適切に選ぶことによって、 {N}人の日程の組み合わせの通り数をちょうど {C}通りにする必要がある。
 {d_1 \le d_2 \le ... \le d_N}となる時、 {d_N}が最小となる時の {d_1, d_2, ..., d_N}の各値はいくらになるか?解のうちの1つを出力せよ。

続きを読む

CodeChef May Challenge 2018: Rubber Band

CodeChefのMay Challenge 2018の問題: Rubber Band (Code: RUBBER)
問題: https://www.codechef.com/MAY18A/problems/RUBBER

コンテスト中解けなかった問題。解法メモ。

問題概要

ボード上に {N}個のnailが固定されている。そこに、 {M}個の線分で輪っかが構成された1つのrubber bandが存在している。
rubber bandをnailと交差しないように自由に形を変形することで、 {N}個のnailとrubber bandを完全に分離(つまり、rubber bandの輪の中にnailが存在しない状態を実現)できるかを判定せよ。

続きを読む

AGC024 - D問題: Isomorphism Freak

問題: D: Isomorphism Freak - AtCoder Grand Contest 024 | AtCoder

1100点だけど、実質700, 800点問題な感じ。
コンテスト中に解けないといけなかった問題。猛省。

問題

 {G}を何色かで彩色したものの内、ある色で彩色された頂点 {v}を根とした根付き木は全て同型となるものを良い彩色と呼ぶ。また、木 {G}良い彩色の中の色の種類が最小値をカラフルさと呼ぶ。

この木 {G}のある頂点と新たな1つの頂点を繋ぐ操作を何回か繰り返すことで達成できるカラフルさの最小値はいくらか?
そして、カラフルさが最小となる時の木 {T}の内、葉の数が最小となる時の葉の数はいくらか?

続きを読む

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の番号がついた {N}個の頂点を含む2つの木 {T_1, T_2}が与えられる。

 {T_1}に含まれる各辺 {e_1}について、以下の条件を満たす {T_2}上の辺 {e_2}の数を計算せよ。

  •  {T_1}から辺 {e_1}を除去し {e_2}を追加したグラフ {T_1 - e_1 + e_2}が木になる
  •  {T_2}から辺 {e_2}を除去し {e_1}を追加したグラフ {T_2 - e_2 + e_1}が木になる
続きを読む

CodeChef May Challenge 2018: S-T Mincut

CodeChef の May Challenge 2018 の問題: S-T Mincut (Code: STMINCUT)
問題: https://www.codechef.com/MAY18A/problems/STMINCUT

問題

 {N \times N}の行列 {A}が与えられる。
この行列の各要素 {A_{ij}}の値を増やすことで次の条件を満たす必要がある。

  •  {N}個の頂点のグラフの中で、頂点 {i}と頂点 {j}の間の最小カットのコストが {A_{ij}}となるグラフ {G}が存在する

この条件を満たすように行列 {A}の各要素の値を増加させた時に、その増加させる値の合計を最小いくらにできるかを計算せよ。

続きを読む