CodeChef August Challenge 2018の問題: Safe Partition (Code: SAFPAR)
問題ページ: https://www.codechef.com/AUG18A/problems/SAFPAR
問題概要
個の要素を含む数列がある。
この数列を、各要素がいずれか1つの列に属するように、連続したいくつかの部分列に分割する。
この時、全ての部分列についてを満たすようにしたい。
このような分割の仕方はいくつあるか?MOD で求めなさい。
CodeChef August Challenge 2018の問題: Safe Partition (Code: SAFPAR)
問題ページ: https://www.codechef.com/AUG18A/problems/SAFPAR
個の要素を含む数列がある。
この数列を、各要素がいずれか1つの列に属するように、連続したいくつかの部分列に分割する。
この時、全ての部分列についてを満たすようにしたい。
このような分割の仕方はいくつあるか?MOD で求めなさい。
Code Chef August Challenge 2018の問題: Chef at the River (Code: RIVER)
問題ページ: https://www.codechef.com/AUG18A/problems/RIVER/
Chefとの動物が川の左岸におり、ボートを使って何回か往復することで全員右岸に渡りたい。
ボートは必ずChefが同行しなければならない。
匹の動物の中には、相性が悪いペアがおり、Chefと一緒にいない時に彼らが一緒にいてはいけない。
この悪いペアの関係は頂点のグラフで表現され、とが辺で繋がっている時、, は相性が悪いことを表す。
最初は頂点1のみの根付き木になっており、の頂点がこの根付き木に繋がっていく。
2の頂点が繋がった時から、の頂点が繋がった時までの各の状態について、制約を満たしながらChefと動物全員を対岸に渡すために必要な最小のボートの容量を求めよ。
CodeChef July Challenge 2018の問題: Subway Ride (Code: SUBWAY)
問題ページ: https://www.codechef.com/JULY18A/problems/SUBWAY
頂点、辺の無向グラフが与えられる。
このグラフは自己ループと単純閉路が存在せず、多重辺を持つ。(つまり、同じ頂点同士を繋ぐ多重辺を全て1つの辺に置き換えると木になる)
そして、各辺には色が塗られている。
番目の辺は頂点と頂点を繋ぎ、の色で塗られている。
このグラフの2点間の単純パスを考え、この時通る辺の色を通った順に並べ、コストを計算する。
このコストは、単純パスで通った辺の内、隣接している辺の色が異なる数、で計算する。
今回、クエリが与えられる。
各クエリで頂点と頂点が与えられるので、その2点間の単純パスで考えられる最大コストを計算せよ。
CodeChef July Challenge 2018の問題: Tom and Jerry (Code: JELLYTOM)
問題ページ: https://www.codechef.com/JULY18A/problems/JERRYTOM
Jerryを捕まえるためにTomは匹の猫を雇う。
そして、つの頂点と本の辺を持つグラフ上で匹の猫達がJerryを捕まえようとする。
このグラフは以下の特徴を持つ
このグラフ上では、各roundで以下の手順を行う
グラフ上でJerryを捕まえるために必要な最小の猫の数はいくらか?
CodeChef July Challenge 2018の問題: Pizza Delivery (Code: PDELIV)
問題ページ: https://www.codechef.com/JULY18A/problems/PDELIV
一直線上に個のピザ屋と人のお客がいて、番目のピザ屋は、番目のお客はにいる。
番目のピザ屋で1枚注文する場合、ベースの値段に加えて、ピザ屋の位置からお客の位置まで配達するのに追加料金がかかる。
また、各お客には注文したくないピザ屋が個存在する。
この状況で、人のお客がピザ1枚注文するための、最小料金はそれぞれいくらか?
Codeforcesで行われたコンテスト
codeforces.com
Microsoftによって作られた量子プログラミング言語Q#を使ったコンテスト
面白そうなので解いた。
Warmupなので練習コンテスト。本番は今週の土曜日1:00から3日間らしい(気が向いたら出よう)。
Li Chao (Segment) Treeについて理解をまとめた
続きを読む