2018-08-15

CodeChef August Challenge 2018: Chef at the River

ProCon CodeChef

Code Chef August Challenge 2018の問題: Chef at the River (Code: RIVER)
問題ページ: https://www.codechef.com/AUG18A/problems/RIVER/

問題概要

Chefと ${N}$ の動物が川の左岸におり、ボートを使って何回か往復することで全員右岸に渡りたい。
ボートは必ずChefが同行しなければならない。

${N}$ 匹の動物の中には、相性が悪いペアがおり、Chefと一緒にいない時に彼らが一緒にいてはいけない。
この悪いペアの関係は ${N}$ 頂点のグラフで表現され、 ${u}$ と ${v}$ が辺で繋がっている時、 ${u}$ , ${v}$ は相性が悪いことを表す。

最初は頂点1のみの根付き木になっており、 ${2, 3, ..., N}$ の頂点がこの根付き木に繋がっていく。
2の頂点が繋がった時から、 ${N}$ の頂点が繋がった時までの各 ${N-1}$ の状態について、制約を満たしながらChefと動物全員を対岸に渡すために必要な最小のボートの容量を求めよ。

2018-07-20

CodeChef July Challenge 2018: Subway Ride

ProCon CodeChef

CodeChef July Challenge 2018の問題: Subway Ride (Code: SUBWAY)
問題ページ: https://www.codechef.com/JULY18A/problems/SUBWAY

問題概要

頂点 ${N}$ 、辺 ${M}$ の無向グラフが与えられる。
このグラフは自己ループと単純閉路が存在せず、多重辺を持つ。(つまり、同じ頂点同士を繋ぐ多重辺を全て１つの辺に置き換えると木になる)
そして、各辺には色が塗られている。

${i}$ 番目の辺は頂点 ${u_i}$ と頂点 ${v_i}$ を繋ぎ、 ${w_i}$ の色で塗られている。

このグラフの2点間の単純パスを考え、この時通る辺の色を通った順に並べ、コストを計算する。
このコストは、単純パスで通った辺の内、隣接している辺の色が異なる数、で計算する。

今回、 ${Q}$ クエリが与えられる。
各クエリで頂点 ${u}$ と頂点 ${v}$ が与えられるので、その2点間の単純パスで考えられる最大コストを計算せよ。

2018-07-19

CodeChef July Challenge 2018: Tom and Jerry

ProCon CodeChef

CodeChef July Challenge 2018の問題: Tom and Jerry (Code: JELLYTOM)
問題ページ: https://www.codechef.com/JULY18A/problems/JERRYTOM

問題概要

Jerryを捕まえるためにTomは ${K}$ 匹の猫を雇う。
そして、 ${N}$ つの頂点と ${M}$ 本の辺を持つグラフ ${G = (V, E)}$ 上で ${K}$ 匹の猫達がJerryを捕まえようとする。

このグラフ ${G}$ は以下の特徴を持つ

4つ以上の頂点からなる単純閉路について、この中に含まれる頂点同士を結ぶ、閉路に含まれない辺が存在する

このグラフ ${G}$ 上では、各roundで以下の手順を行う

最初のround 0では、猫達は最初にとどまる頂点集合 ${X_0 \subseteq V, |X_0| \le K}$ となる ${X_0}$ を選択し、Jerryはとどまる頂点 ${v_0 \in V \setminus X_0}$ を選択する
各round では、にいる猫達とにいるJerryが以下のように移動する
- 猫達が次にとどまる頂点集合 ${X_{i+1} \subseteq V, |X_{i+1}| \le K}$ を選択し移動する
- その後にJerryは、 ${X_i \cap X_{i+1}}$ に含まれる頂点を通らないパスで到達できる頂点 ${v_{i+1} \in V \setminus X_{i+1}}$ に移動し、そのような頂点 ${v_{i+1}}$ が存在しない場合はJerryは捕まる