TopCoder Open Round #1 - にゃあさんの戯言日記

懇親会が終わって家に帰ってきた後、しばらくだらーっとして時間を潰した。そして26:00から、TopCoder OpenのRound #1。このラウンドで400/700に絞られる。
とりあえずRegistrationだけすればTCOのTシャツがもらえるのでそれだけでちょっと満足。
しかしやっぱ、一日のうちに二回コンテストをやって、しかも二回目が午前2時からっていうのはきついなぁ...

今回の問題は3問。途中で配点ミスが見つかって、1問目と2問目の難易度が入れ替わったり、時間が30分くらい伸びたり、なんか色々とアクシデントがあった模様。とりあえず問題を紹介してみる。

問題1 (350pt.)

無向グラフの隣接行列が与えられるので、最大マッチングを求めよ。以上。
ただし、ノード数は最大18。

問題2 (500pt.)

最上位の桁の数を最下位の桁にくっつけることを、数を''rotate''することと定義する。つまり、下のような操作がrotate。

12345 -> 51234
102564 -> 025641

分数p/qが与えられるので、rotate操作をしたときに数がp/q倍になるような最小の自然数を求める問題。たとえば、例の2番目はp=1, q=4の時の解。ただし、rotate前の数の最上位桁は0であってはならない。rotate後の最上位桁が0であっても構わない。2000000000(2*10^9)未満にそのような数が無ければ-1を返す。 $1 \le p,q \le 100$ 。

問題3 (900pt.)

n個の要素をもつ集合 $S_n = \left{1, 2, ..., n\right}$ に対して、全単射 $S_n \to S_n$ を''permutation''と呼ぶことにする。たとえば、 $A = \left{1 \to 2, 2 \to 1, 3 \to 3\right}$ はpermutationのひとつ。また、''identity permutation''とは全ての要素を同じ要素に射影するpermutationのこと。つまり、 $I_n = \left{1 \to 1, 2 \to 2, 3 \to 3, ..., n \to n\right}$ 。
ここで、 $S_n$ に対する permutation $P_n$ の''order''を、 $(P_n)^k = I_n$ を満たす最小のkと定義する。たとえば、Aのorderは2。

整数n ( $1 \le n \le 1000$ )が与えられるので、 $S_n$ に対する異なるorderのpermutationがいくつ存在するかを返す。たとえば、 $S_3$ に対するpermutationにはorderが1,2,3のものが存在するので、n=3に対する解答は3。

さて、ぼくはどうだったかというと。

問題2

最初はこれが一番点数の低い問題と表示されていたのでこの問題から始めた。

rotate前の数を $10^n k + x$ (ただし $0 \le x \lt 10^n$ )とすると、rotate後の数は $10x + k$ なので、それが $\frac{p}{q}$ 倍になるとき、 $x = \frac{k(10^n p - q)}{10q - p}$ 。n, kの小さい順にxを計算して、そのような整数xが存在するかチェックしてやればいい。