この記事は、"IQ1 Advent Calendar 2018"の13日目の記事です。
adventar.org
今回は、自分用の競プロライブラリのWebページを最近AsciiDocで作ったので、この話を書きます。競プロよりもAsciiDocメインの記事です。
tjkendev.github.io
Link-Cut Treeの実装メモ
Link-Cut Tree(Link-Cut 木)を実装したのでそのメモみたいなもの
続きを読むCodeChef August Challenge 2018: Safe Partition
CodeChef August Challenge 2018の問題: Safe Partition (Code: SAFPAR)
問題ページ: https://www.codechef.com/AUG18A/problems/SAFPAR
問題概要
個の要素を含む数列
がある。
この数列を、各要素がいずれか1つの列に属するように、連続したいくつかの部分列に分割する。
この時、全ての部分列についてを満たすようにしたい。
このような分割の仕方はいくつあるか？MOD で求めなさい。
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との動物が川の左岸におり、ボートを使って何回か往復することで全員右岸に渡りたい。
ボートは必ずChefが同行しなければならない。
匹の動物の中には、相性が悪いペアがおり、Chefと一緒にいない時に彼らが一緒にいてはいけない。
この悪いペアの関係は頂点のグラフで表現され、
と
が辺で繋がっている時、
,
は相性が悪いことを表す。
最初は頂点1のみの根付き木になっており、の頂点がこの根付き木に繋がっていく。
2の頂点が繋がった時から、の頂点が繋がった時までの各
の状態について、制約を満たしながらChefと動物全員を対岸に渡すために必要な最小のボートの容量を求めよ。
CodeChef July Challenge 2018: Subway Ride
CodeChef July Challenge 2018の問題: Subway Ride (Code: SUBWAY)
問題ページ: https://www.codechef.com/JULY18A/problems/SUBWAY
問題概要
頂点、辺
の無向グラフが与えられる。
このグラフは自己ループと単純閉路が存在せず、多重辺を持つ。(つまり、同じ頂点同士を繋ぐ多重辺を全て１つの辺に置き換えると木になる)
そして、各辺には色が塗られている。
番目の辺は頂点
と頂点
を繋ぎ、
の色で塗られている。
このグラフの2点間の単純パスを考え、この時通る辺の色を通った順に並べ、コストを計算する。
このコストは、単純パスで通った辺の内、隣接している辺の色が異なる数、で計算する。
今回、クエリが与えられる。
各クエリで頂点と頂点
が与えられるので、その2点間の単純パスで考えられる最大コストを計算せよ。
