Problems 302. Count on Cantor

概要

出展

https://www.spoj.pl/problems/CANTON/

簡単な解説

（1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4...）と続く数列があるとする。
この時、n番目は何なのかを求める。

（主観的な）ジャンル

数学的なアルゴリズム

（主観的な）難易度　５段階

☆☆（標準）

所感

問題文の表がヒントです。ここからどうやってn番目を導き出すかがポイントです。
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1

ごり押しでも解けそうな気がするのですが、スマートな方法を探してみることにしました。

考察

n番目がどの辺り位置するのかの検討をつける必要があります。
1引いて、2引いて、3引いて...で負の数になるまで計算してもいいのですが、時間かかりそうなので、個人的にNGです。

まず、「分母+分子」が同じ値のものをグループにします。
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1
今回の数列はこのグループを、左下に進む⇒左上に進む⇒左下に進む...を繰り返していることが分かります。
グループに属する分数の数は、１つ、２つ、３つ...と増えて行きますので、台形の公式を使うとm番目のグループまでに存在する分数の個数を求めることができます。

（上底+下底）*高さ/2＝台形の面積
（1+m）*m/2=分数の個数
(m*m)+m=分数の個数*2 ...(1)

(1)で、分数の個数をsとすると、

m^2 + m - 2s = 0

と展開できます。これは2次方程式なので、解の公式が使用可能です。

m = (-1 + √(1 + 8s)) / 2

となります。グループ番号mは正の値なので、-√の方はあり得ないので却下です。
sは、今回の入力値nと同値ですので、これによって求まった値を小数点以下切り上げればmが確定できます。

グループ番号mが求まれば、nがそのグループで何番目にいるのかを求めることが可能となります。
グループ内の分数は、「分母+分子=m+1」ということが分かっているので、これによりn番目の分数を特定することが可能です。

解答例

//////////////////////////////////////////////////
//
//  Sphere Online Judge
//      302. Count on Cantor
//      Problem code:   CANTON
//
//      Author  : Hau-kun
//      Date    : 2010/12/27
//
//////////////////////////////////////////////////
//  accepted
//      TIME    0.00
//      MEM     1.6M
//      LANG    C
//////////////////////////////////////////////////

#include 
#include 

#define FORMAT_OUTPUT "TERM %d IS %d/%d\n"

//  プロトタイプ宣言
void AnalyzeContor(void);

//////////////////////////////////////////////////
//  メイン関数
////////////////////////////////////////////////////
int main(void)
{
    int i = 0;
    int nLoopMax = 0;       //  問題数

    //  問題数読み取り
    scanf("%d", &nLoopMax);
    
    //  問題数分、処理を繰り返す
    for(i = 1; i <= nLoopMax; i++)
    {
        AnalyzeContor();
    }

    return 0;
}

//////////////////////////////////////////////////
//  データ出力関数
//////////////////////////////////////////////////
void AnalyzeContor(void)
{
    int nInput = 0;
    int nGroup = 0;
    int nOrder = 0;

    //  データの入力
    scanf("%d", &nInput);

    //  データがどのグループにいるかを求める。
    nGroup = ceil((-1 + sqrt((double)1 + 8 * nInput)) / 2); //  cf.解の公式

    //  データが、グループ内の何番目にいるのか求める。
    nOrder = ((nGroup * nGroup + nGroup) - (nInput * 2)) / 2;

    //  データが、分母の減少グループか、分子の減少グループかを求め、結果を出力する
    if(nGroup % 2 == 0)
    {
        //  分母の減少グループ
        printf(FORMAT_OUTPUT, nInput, nGroup - nOrder, nOrder + 1);
    }
    else
    {
        //  分子の減少グループ
        printf(FORMAT_OUTPUT, nInput, nOrder + 1, nGroup - nOrder);
    }
}

Sphere Online Judgeに関する最新記事

• [2011/01/25] Sphere Online Judgeへの参戦方法 (2)
• [2010/12/27] Problems 302. Count on Cantor (0)
• [2010/10/02] Problems 2524. Conversions (1)
• [2010/03/29] Problems 2. Prime Generator (1)
• [2010/03/14] Problems 1. Life, the Universe, and Everything (1)

Sphere Online Judgeへの参戦方法はこちら