1/22 PKU - Algorithmer’s note

2752 Seek the Name, Seek the Fame

与えられた文字列のprefixにもsuffixにもなっているような文字列の長さをすべて求めよ。

まずKMPテーブルを作成する。すると、なぜか次のアルゴリズムが正解を返す。
1. p = L とする。
2. p > 0 である限り、p を解として記録し、p = fail[p] とする。

[補足] 「なぜか」などと書いたが、fail[p]の意味は「文字列の[0, fail[p])の部分と[p-fail[p], p)が一致する」ということであり、これの「fail[p]」を「fail[fail[p] ]」などと読み替えても成立するので、当然といえば当然である。さらにKMPのfailを辿っていって、そのような位置をすべて記録しきれていないなら、検索アルゴリズムとして使えない。

3013 Big Christmas Tree

グラフからいくつかの辺を選んで木を作る。各辺、各頂点には重みがついており、木のコストは各辺に対しての(辺の重み)*(すべての子ノードの重みの和)で計算される。木の根は常に頂点1である。コストを最小化せよ。

式を組み替えると、コストはすべての頂点に対しての(頂点の重み)*(根までの経路上の辺の重みの和)とできる。頂点の重みは固定なので、根までの距離を最小化すればよい。実際、Dijkstraをすると、すべての頂点に対して最短経路を達成するために必要な辺の数はV-1であり、ちょうど木になる。

3249 Test for Job

街と街のつながりを示した図と、各街で得られる利益が与えられる。source-city（その街に入る道がないような街）からtarget-city（その街から出る道がないような街）までで得られる利益の最大値を求めよ。

やるだけ

3265 Problem Solving

いくつかの問題を解決したいが、難しすぎるのでコンサルタントに頼むことにした。コンサルタントは、どの問題も１ヶ月で解決できる。報酬は、依頼する月の初めと解決し終わった月の初めに払う。牛は毎月、金をM稼ぐが、次の月に報酬として払う以外の金はcow candyに使ってしまうので、前の月に稼いだ金額を使うことしかできない。i

3797 Tiling a Grid With Dominoes

4*nのグリッドを1*2の長方形で埋め尽くす方法は何通りか。

漸化式立てるだけ

3276 Face The Right Way

牛がN頭1列に、それぞれ前後どちらかを向いて並んでいる。Farmer Johnは自動牛回転機を導入しようとしている。これは、K頭の連続した牛の向きを反対にできるというものである。K-1頭以下の牛に対しては使えない。牛の並び方が与えられた時、回転の回数を最小化するKと、その回数を求めよ。

すべてのKに対して回数を求める。回数は、前の牛から順に回転/非回転を決定していくと求められる。最後のほうは回転しようとすると牛がK頭もいなくなるので回転できないことに注意。

2303 Russian Dolls

これマトリョーシカかな。2N個の人形があり、それぞれ幅d、高さh、厚さwを持っている。(d, h, w)の人形の中に入る人形(d', h', w')は、d'<=d-2w, h'<=h-2wを満たさないといけない。N個組を2つ作り、どちらも入れ子で1つの人形になっているようにせよ。

DP。入れ子の外側になるにつれて幅は単調増加なので、幅についてソートした後、dp[i][j][k] を「左側最後がi、右側最後がj、左側にはk個使った」として計算するとよい。ダミーの人形(0, 0, 0)を入れておくと楽。

3043 Walk the Talk

文字入りのグリッドが与えられる。辞書にある文字列を、次のようにして作る。
1. 適当なマスを選び、そのマスにある文字を書く。
2. そのマスより右上にあるマス（上や右も含む）に移動し、同じ事を繰り返す。

文字列はいくつ作れるか。

Trie + DP

2803 Defining Moment

単語を、語幹に接頭辞や接尾辞をくっつける方法で拡張するらしい。そのようにして得られる単語の意味を答えよ。

やるだけ