2018-05-16

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}$ が木になる

2018-05-14

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

2018-05-04

ARC085 - E問題: MUL

AtCoder ProCon

昔いろいろ考えたけど、書き忘れた問題
問題: E - MUL

2018-05-03

ARC087 - E問題: Prefix-free Game

AtCoder ProCon

解いたので解法メモ
URL: E - Prefix-free Game

2018-04-29

AGC023 - C問題: Painting Machines

AtCoder ProCon

問題: C - Painting Machines

横一列に並んだN個のマスを、N-1台のマシンで塗っていく。i番目のマシンはi番目とi+1番目のマスを黒く塗る。
ある順列Pを与え、その番号の順番でマシンを動かしていき、N個のマスが初めて黒く濡れた時点のPのindex(1-indexed)がスコアとなる。
全ての順列についてこのスコアを求め、その総和を計算する問題。

解けなかった。解法メモ。