日々ｄｒｄｒする人のメモ

今日も明日もｄｒｄｒ

CodeChef June Challenge 2018: Ways to Work

ProCon CodeChef

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

ProCon CodeChef Algorithm

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

ProCon AtCoder

問題: 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

ProCon CodeChef

CodeChefのMay Challenge 2018の問題: Edges in Spanning Trees (Code: EDGEST)
問題: https://www.codechef.com/MAY18A/problems/EDGEST

問題

1からNの番号がついた {N}個の頂点を含む２つの木 {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

ProCon CodeChef

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}の各要素の値を増加させた時に、その増加させる値の合計を最小いくらにできるかを計算せよ。

続きを読む