ZOJ-1331* a3=b3+c3+d3

1331:aが200以内でaを満たすキューブがb,c,dキューブ和に等しいすべての解を求める.a昇順でリストします.
同じaに対して、一致する複数の組合せがある可能性があり、昇順でリストすることが要求される.
構想は多重ループ遍歴解である.
最初に書かれたコードは次のとおりです.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<memory.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

struct Cube
{
	int a;
	int b;
	int c;
	int d;
};

bool myorder(const Cube& s1,const Cube& s2)
  {
   if(s1.a != s2.a)
    return s1.a < s2.a;
   else if(s1.b != s2.b)
    return s1.b < s2.b;
   else
    return s1.c < s2.c;
  }


int a[201];
int b[201];
int c[201];
int d[201];
int cube[201];
vector<Cube> vcube;


int main()
{
	double res;
	int index;
	int sum;
	int vceil;
	int vfloor;
	//    
	for(int i=0;i<=200;i++)
		cube[i]=i*i*i;

	for(int bb=2;bb<=200;bb++)
		for(int cc=bb;cc<=200;cc++)
			for(int dd=cc;dd<=200;dd++)
			{
				sum=cube[bb]+cube[cc]+cube[dd];
				res=pow(sum,1.0/3);

				vceil = ceil(res);
				vfloor = floor(res);

				if(cube[vceil]==sum)
					index=vceil;
				else if(cube[vfloor]==sum)
					index=vfloor;
				else
					index=-1;

				if(index!=-1)
				{
					Cube c;
					c.a=index;
					c.b=bb;
					c.c=cc;
					c.d=dd;
					vcube.push_back(c);
					sort(vcube.begin(),vcube.end(),myorder);
				}
			}

			for(int i=0;i<vcube.size();i++)
			{
				printf("Cube = %d, Triple = (%d,%d,%d)
",vcube[i].a,vcube[i].b,vcube[i].c,vcube[i].d);
			}
			

}

b,c,dを先に得てaを求める方法を採用したため,開方問題と並べ替え問題に遭遇した.開方については精度の問題により,本来の式が等しくない場合もある.floorとceilで調整してみます.ループ後にソート方法をカスタマイズしてソートします.コードは比較的肥大化しており、実行効率が低い.
良い書き方を見ました.

#include <stdio.h>

int BinarySearch(int s[], int high, int low, int key)
{
    int mid;

    while (low <= high) {
        mid = (high + low) / 2;
        if (s[mid] == key) return mid;
        else if (s[mid] < key) low = mid + 1;
        else high = mid - 1;
    }

    return 0;
}

int main(int argc, char *argv)
{
    int a, b, c, d, i, cube[201];
    
    for (i = 1; i < 201; i ++) cube[i] = i * i * i;
    for (a = 6; a <= 200; a ++) 
        for (b = 2; b < a; b ++) {
            i = cube[a] - cube[b];
            for (c = b + 1; c < a; c ++) {
                d = BinarySearch(cube, a - 1, c + 1, i - cube[c]);
                if (d) printf("Cube = %d, Triple = (%d,%d,%d)
", a, b, c, d);
            }
        }

    return 0;
}

コードは比較的簡素です.両方のコードは配列を用いて200以内のすべての数の立方値を予め計算し,複数回使用する必要があるため,繰返し計算を回避した.
主な違いはサイクルの順序と等式を検証する方法に現れる.既知のa,b,cを用いてdを求める方式.このような利点は,a,b,cをサイクル条件に置いて昇順を維持することである.検証が等しい場合は開方を採用せず,二分探索を用いて浮動小数点数処理を回避した.
境界の処理にも効率が現れている.ループの上下境界、検索の上下境界のように、これらは効率を向上させます.