日々drdrする人のメモ

今日もdrdr、明日もdrdr

CodeChef August Challenge 2018: Safe Partition

CodeChef August Challenge 2018の問題: Safe Partition (Code: SAFPAR)
問題ページ: https://www.codechef.com/AUG18A/problems/SAFPAR

問題概要

 {N}個の要素を含む数列 {A}がある。

この数列を、各要素がいずれか1つの列に属するように、連続したいくつかの部分列 {S_1, S_2, ..., S_K}に分割する。
この時、全ての部分列について {\min(S_i) \le |S_i| \le \max(S_i)}を満たすようにしたい。

このような分割の仕方はいくつあるか?MOD  {10^9 + 7}で求めなさい。

続きを読む

CodeChef August Challenge 2018: Chef at the River

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と動物全員を対岸に渡すために必要な最小のボートの容量を求めよ。

続きを読む

CodeChef July Challenge 2018: Subway Ride

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

問題概要

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

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


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

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

続きを読む

CodeChef July Challenge 2018: Tom and Jerry

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  {i (\ge 0)}では、 {X_i}にいる猫達と {v_i}にいる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}はいくらか?

続きを読む

CodeChef July Challenge 2018: Pizza Delivery

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枚注文するための、最小料金はそれぞれいくらか?

続きを読む

Microsoft Q# Coding Contest - Summer 2018 - Warmup

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

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

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

続きを読む