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

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

ランダムな方向を向いた時のChefの視界の範囲 ${x}$ に含まれる建物の数の期待値をmodulo 163577857で求めなさい。

2018-06-12

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

2018-05-27

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が存在しない状態を実現)できるかを判定せよ。