トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

第1回 CodeIQプロコン 4問目 鬼

■■■問題■■■

4つのブロックを立方体と考えます。
一辺の長さをそれぞれa, b, c, dとして、

X = aの3乗 + bの3乗
Y = cの3乗 + dの3乗

とするとき、X = Yを満たすX(=Y)の最大値を求めてください。
(a,b,c,dにはそれぞれ別の数字が入るとします)

たとえば、1辺の長さが1〜20までのときは
(1) 1の3乗 + 12の3乗 = 9の3乗 + 10の3乗
(2) 2の3乗 + 16の3乗 = 9の3乗 + 15の3乗

のような場合が考えられますが、
(1)を計算すると1729、(2)を計算すると4104となりますので、4104が条件を満たす最大値となります。

■■■入力■■■

標準入力から、一辺の長さの最大値として整数値(20〜1000)が与えられます。

■■■出力■■■

標準出力に、解となる整数値のみ出力してください。
出力後の改行の有無は問いません。


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input3";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("20");
            //4104
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("50");
            //110808
        }
        else if (InputPattern == "Input3") { //最悪計算量
            WillReturn.Add("1000");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        int[] SanjyouArr = new int[N + 1];
        for (int I = 1; I <= SanjyouArr.GetUpperBound(0); I++) {
            SanjyouArr[I] = I * I * I;
        }

        var SumSet = new HashSet<int>();
        var Answer = 0;

        for (int I = SanjyouArr.GetUpperBound(0); 1 <= I; I--) {
            for (int J = I - 1; 1 <= J; J--) {
                int wkSum = SanjyouArr[I] + SanjyouArr[J];
                if (Answer > wkSum) break;

                if (SumSet.Add(wkSum) == false) {
                    if (Answer < wkSum)
                        Answer = wkSum;
                }
            }
        }
        Console.WriteLine(Answer);
    }
}


解説

3乗数の2数の和を、
なるべく降順になるように求め、
Break文を使用できるようにしてます。

『第1回CodeIQ プログラミングコンテスト』問題解説 --- CodeIQ MAGAZINE