7月17日のPKU

今日：3問
今日までの合計：3問

PKU 2421 Constructing Roads

問題

PKU 2421

いくつかの村があって、その村のうち二つが道で結ばれているものがある。

村どうしの距離が与えられるので、道を付け足して全部の村を通行可能にするとき、付け足す道の最小の長さを求める問題。

村の数は100以下で村どうしの距離は1以上1000以下。

解法

まず既に結ばれている村たちを幅優先探索なりで連結成分ごとに分解。その後、連結成分ひとつを頂点として最小全域木を求める。

PKU 2590 Steps

問題

PKU 2590

整数x, y(0 <= x <= y < 2³¹)が与えられる。xから整数を渡り歩いてyに到達したい。

ただし、1ステップに進める長さは、直前に進んだ長さのままか、±1の範囲のみとする。

また、最初にxから出発するときは1だけ進むことができ、最後にyへ到達するときには必ず長さ1の進行で到達しなければならない。

このとき、xからyへ行くのに必要な最小の移動回数を求める問題。

解法

xからyに行くまで、1ずつ進行距離をのばしていって、yのところでちょうど1になるように進行距離を落として行く。

このとき、進行距離が最長になるときの進行距離の長さは floor(sqrt(y-x)) で求めることができる。これは、進行距離を「1 → 2 → 3 → ... → n-1 → n → n-1 → ... → 3 → 2 → 1」のように変えながら進んだとき、合計で n² だけ進めることから分かる。

floor(sqrt(y-x)) を f とする。上にあげた進み方をすれば f² だけ進むことができて、残りは (y-x)-f² であり、この残りを d とする。

dが0の場合は既にyに到達しているから、答は 2f-1 ステップになる。

dがf以下の場合は上の進み方に1ステップ追加して、「1 → 2 → 3 → ... → d → d → d+1 → ... → n → ...　→ 3 → 2 → 1」という風にする。そうするとf²+dだけ進むことができる。よってdがf以下の場合は答は 2f ステップになる。

dがf以上の場合は、dをf以下の二つの数の和で表現して、dがf以下の場合と同じように考えれば答は 2f+1 ステップになる。ここではdが必ず2f以下であることを利用している。

PKU 3665 iCow

問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=3665:PKU 3665

音楽プレイヤにN曲の曲が入っており、1からNまで番号がつけられている。曲ごとの評価が決まっており、評価がもっとも高い曲が次に演奏される。

演奏された曲の評価は他の曲に平等に分配され、演奏された曲の評価は0になる。

評価の分配過程で余りが出た場合(演奏された曲の評価がN-1で割り切れなかった場合)は、その余りを曲の番号が若い順に1ずつ分配していく。

初期のレーティングが与えられるので、最初からT番目まで、演奏される曲の番号を順番に求める問題。

ただし 1 <= N, T <= 1000。初期のレーティングは全て1以上10000以下。

解法

やるだけ。