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は捕まる

グラフ ${G}$ 上でJerryを捕まえるために必要な最小の猫の数 ${K}$ はいくらか？

2018-07-17

CodeChef July Challenge 2018: Pizza Delivery

ProCon CodeChef

CodeChef July Challenge 2018の問題: Pizza Delivery (Code: PDELIV)
問題ページ: https://www.codechef.com/JULY18A/problems/PDELIV

問題概要

一直線上に ${n}$ 個のピザ屋と ${m}$ 人のお客がいて、 ${i}$ 番目のピザ屋は ${s_i}$ 、 ${i}$ 番目のお客は ${c_i}$ にいる。

${i}$ 番目のピザ屋で1枚注文する場合、ベースの値段 ${p_i}$ に加えて、ピザ屋の位置 ${x_1}$ からお客の位置 ${x_2}$ まで配達するのに追加料金 ${(x_1 - x_2)^2}$ がかかる。

また、各お客 ${i}$ には注文したくないピザ屋が ${k_i}$ 個存在する。
この状況で、 ${m}$ 人のお客がピザ1枚注文するための、最小料金はそれぞれいくらか？

2018-07-03

Microsoft Q# Coding Contest - Summer 2018 - Warmup

ProCon Codeforces

Codeforcesで行われたコンテスト
codeforces.com

Microsoftによって作られた量子プログラミング言語Q#を使ったコンテスト

面白そうなので解いた。
Warmupなので練習コンテスト。本番は今週の土曜日1:00から3日間らしい(気が向いたら出よう)。

2018-06-16

Li Chao Treeのメモ

ProCon Algorithm

Li Chao (Segment) Treeについて理解をまとめた

2018-06-15

CodeChef June Challenge 2018: Archi and Tree

ProCon CodeChef

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を出力せよ。

2018-06-13

CodeChef June Challenge 2018: Expected Buildings

ProCon CodeChef

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}$ )である。