TopCoder: Single Round Match 283

Single Round Match (SRM) Schedule at TopCoder

20日は久しぶりにTopCoderのSingle Round Matchに参加しました。

TopCoderというのは，オンラインでプログラミングコンテストをやっているサイトで，参加者は出題された問題を解くプログラムを素早く仕上げる能力を競います。問題はパズルみたいなのが多いですね。TopCoderは，Google主催のプログラミングコンテスト"Google Code Jam"で使われてるのをみて知りました。


TopCoderでは以下のような独自のJavaアプレットで参加します。



上半分に問題文が出て，下半分にプログラムを入力します。右下のボタンでコンパイルやテストが出来ます。完成したと思ったらSUBMITボタンで送信。問題文を開いてからSUBMITまでの時間でスコアが決まります。

SRMがどんな流れで進むかということに関しては以前SRMに参加したときのエントリを参照してください。


で，結果ですが・・・。
またチャレンジフェーズで落とされました！　うー，落とされる前までは結構上位だったんで期待してたんだけどなぁ。以下に今回出題された問題をメモっときます。


250点問題「DiagonalDisproportion」

• 一桁の数字が正方形の行列に配置されているとき，左上から右下への数字を足したものから，右上から左下への数字を足したものを引き算した値を返すという問題。ただし行の数字は1行の文字列の配列で渡される。例：{"190","828","373"}。

600点問題「PowerSupply」

• 時間が無かったのでパスしました。

1000点問題「FactorialGCD」

• 整数a，bが与えられたとき，a!とbの最大公約数を求めよ。

250点問題はそんなに難しく無かったです。素直に書いて速攻サブミット。

600点問題はパスで，1000点問題。この問題が結構難しくて，試行錯誤をぎりぎりまでやってました。最初は「最大公約数はユークリッドの互除法で求めればOKだし，1000点にしては簡単じゃね？」とか思ってました。つまり次のようなアホアホなプログラムを書いちゃってました。

public int factGCD(int a, int b) {
    int temp = fact(a); // 階乗を計算
    return gcd(x, b); // 最大公約数を計算
}

ですが，実行してみるとすぐに分かりますが，階乗ってのがクセモノで，普通に階乗してから最大公約数を計算してると，fact(a)のところで桁あふれになっちゃいます。

ということで何かトリックを考えなくちゃいけない。ユークリッドの互除法の計算では，最初にa!をbで割った余りを求めます。なので別にa!が分からなくてもbで割った余りが分かれば，最大公約数の計算は実行できます。そこで階乗の計算途中にbで割った余りで置換する，という戦略で行きました（合同式の乗法法則）。
つまり以下のようなロジック。

public int factGCD(int a, int b) {
    int temp = 1;
    for (int i=a; i>0; i--) {
        temp = (i % b) * (temp % b);
    }
    return gcd(b, temp);
}

これで桁あふれはしなくなったんですが，問題文で紹介されている例(a=2097711064, b=2147483646)だと，制限時間2秒以内に終わりません。そこで細かい条件を考えて調整しつつ，制限時間10分前で何とか2秒以内に計算させることが出来ました。結構苦労したので「やった！」と心の中で叫んでました。
で，最終的にサブミットしたのが次のプログラム。

public int factGCD(int a, int b) {
    // aの方が大きかったら階乗にbが含まれるのでbが最大公約数
    if ( a >= b ) return b;
    int temp = 1;
    for (int i=a; i>0; i--) {
        temp = (i % b) * (temp % b);
        // 階乗の途中計算がbの倍数になったらループを抜ける
        if (temp == 0) break;
    }
    // a!がbの倍数になっているので，bが最大公約数
    if (temp == 0) return b;
    return gcd(b, temp);
}

でもチャレンジで落とされたんですよねー(ﾁｷｼｮｳ!)。今，冷静になって考えてみると，階乗の計算式がおかしい気がします。(i%b)*(temp%b)じゃなくて，(i*temp)%bでよかったんじゃないかなぁ。そこで代入されるtempで桁あふれが起こっていたと思います。


ともかく，久しぶりに全力で集中してプログラムを書けたので満足です。最近はEclipseのプラグインを弄ったりフレームワークを使ったり，素直に1からソースコードを書くことが少なかったので，こういうのは息抜きに良いですね。今後もTopCoderのSRMには参加していこうと思います。

一応，TopCoderにはdeltam81の名前で参加してますので，よろしく。


【関連リンク】
4TopCoder
日本人でTopCoderに参加している人のBlog。問題について詳細に解説されているので勉強になります。
TopCoder Events Calendar
TopCoderのイベントスケジュール。

【過去の記事】
サルノオボエガキ: TopCoder
サルノオボエガキ: Single Round Match 255 at TopCoder