11/19 PKU - Algorithmer’s note

それぞれ異なる数値をもつ牛がN頭いる。牛を入れ替えて数値の順に整列させたい。2頭の牛を入れ替える際には、2頭の数値の和だけコストがかかる。任意の2頭を入れ替えられる。コストの和を最小化せよ。

巡回列らしい

文字列と、各文字に対して、その文字を追加するときのコストと削除するときのコストが与えられるので、文字列を回文にするために必要な最小のコストを求めよ。

牛が一列に並んでいて、どの牛がどの牛を見れるっていうリストが与えられるので、各牛の最大の身長を求めよ。

リストを適切にソートして順番に制約を強める

連結な無向グラフが与えられる。グラフに辺をいくつか付け足して、すべての頂点間に、同じ辺を共有しないような2つ以上の経路が存在するようにするとき、最低何本付け足す必要があるか。

二重辺連結成分を求めて、同じ成分のものを同一視して木にしてから、葉の数を求める。葉の数をRとすると、(R+1)/2の整数部分が答えとなる。

牛が何頭かいて、それぞれ掃除する時間と掃除させるために必要なコストが決まっている。時間全部いずれかの牛が掃除しているようにするために必要な最小コストはいくらか。

DP書くの面倒だったからdijkstraで通したけどdijkstraもvector使ったらTLEしたので結局面倒だった

グリッドがあり、各マスは「牛」「騎士」「道」「通れない」「shrubbery」のどれかである。牛は縦横四方向に移動できる。牛がshrubberyを得て騎士のところへ行く時の最小時間を求めよ。shrubberyを持たずに騎士の場所を通過してはならない。

牛の場所と騎士の場所からBFSやるだけ

ビット列がいくつか与えられるので、目標とするビット列に最も近い（異なるビット数が最小）ものを求めよ。

英語読むだけ

整数列A1, A2, …, ANが与えられる。非減少もしくは非増加の整数列B1, B2, …, BNをとるとき、|A1-B1|+…+|AN-BN|の最小値を求めよ。

Biの値はあるAの値に限ってよいことに注意すると、DPで求まる。

「A→B」みたいな関係がたくさん与えられるから、全部つなげたものを出力せよ。

std::string, std::mapの練習問題