GCJ 2011 Round 2

C>=A>D>>Bなセットだった。個人的には。

A

動く歩道がいくつかあって、目的地までの距離が与えられる。全部でT秒だけ走ることができるとして、最短到達時刻を求めよ、という問題。

動く歩道の助けをできるだけ長く享受したい。なので動く歩道がないところは走る、次に一番遅い動く歩道の上を走る...、とやるだけ。

B

NxMの板が与えられて、1x1領域ごとの重さが与えられる。KxKの板を切り取り、4隅の1x1を切り落としたとき、重心が中央にくるようにしたい。このような最大のKを求めよ、という問題。

縦方向と横方向は独立に考えられる。Kが奇数ならある点を中心として、Kが偶数ならある2点の間を中心として、長さKの領域の重み付き和を求める。これは上下・左右に伸ばすときに前の値を再利用して計算できる。つまりこの処理はO(NxMxK)でできる。後は、改めて、横K列の合計が0になることを確かめて、縦K列の合計が0になることを確かめれば良い。

C

1からNまでの数について、任意の順番に集合に加えていく。加えるときに、ある数Kをその集合のすべての数で割り切れる正の数に更新する。このような更新が起こる回数の最大値と最小値の差分を求めよ、という問題。

最終的にKはN以下の数の最小公倍数になる。更新が起きるのは各素因数について、出現回数が変化するとき。ある素数でA回割り切れるとすると、一度にAだけ盛り込むか、1ずつA回盛り込むか、が差分になるので、A-1だけ差分が生まれる。Aが2以上になる可能性のある素数についてだけ計算すれば良い。

D

グラフが与えられるので、始点から終点までの最短パスのうち、そのパスと隣接するノード数が最大のものの隣接ノード数を答えよ、という問題。

始点からの距離をすべての点について計算する。距離の差分が1以内の点にのみ移動できるので、二つ前までの点を覚えておいて、3つ揃ったときに二つ前のより遠く一つ前と同じで、今の点よりも近い点がいくつあるか、というのを足しこんでいけば隣接点は計算できる。