GCJ 2009 Round 1A

予想に反して難しい順にソートされていて、しかも点数が逆転してたりする。

A

ある整数をN進数に変換し、各桁の二乗和を求める。この操作を繰り返し行ったときに1になるものを求めたい。Nに当てはまる数字群が与えられるとき、最小の整数を答えよ、という問題。

愚直な実装をやって下から探索すると、小さい入力のケースでは求まる。大きい入力のケースでは、うまく枝を狩る必要があるんだと思う。2進数とかでうまくいくケースが多過ぎるので、後でチェックにしか使わない、とか？

B

現在地から目的地まで移動するのにかかる最短時間を答えよ、という問題。信号がある。

ダイクストラなんだけれど、次の状態に遷移する枝が動的に(ってほどでもないけど)変化するのでうまく計算する。問題サイズの変更による問題は起こらなさそう。

C

N種類のカードを少なくとも1枚ずつ回収することを考える。C種類のカードを毎回渡されるとき、何回でN種類揃うか、期待値を答えよ、という問題。

現在持っている種類数から、C種類もらうとN種類増えるのは何通りか、というのを組み合わせで求める。増える場合の期待値は分かるので、自分の期待値を未知数にして方程式を立てればいい。小さいケースは全探索でも求まる。