ABC-056-C Go Home

■■■問題■■■

無限に左右に伸びている数直線上の 0 の地点に時刻 0 にカンガルーがいます。
カンガルーは時刻 i-1 から i にかけて、
なにもしないか、もしくは長さがちょうど i のジャンプを、左右どちらかの方向を選んで行えます。
つまり、時刻 i-1 に座標 x にいたとすると、時刻 i には x-i, x, x+i のどれかに存在することが出来ます。

カンガルーの家は座標 X にあります。
カンガルーはできるだけ早く座標 X まで移動しようとしています。
カンガルーが座標 X に到着する時刻の最小値を求めてください。

■■■入力■■■

X

●Xは整数
●1 <= X <= 10億

■■■出力■■■

カンガルーが座標Xに到着する時刻の最小値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            //3
            //3回右にジャンプすると時刻3に家にたどり着けて、これが最小です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            //2
            //時刻0にはなにもせず、
            //時刻1に右にジャンプすることで時刻2に家にたどり着けます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int SumVal = 0;
        for (int I = 1; I <= int.MaxValue; I++) {
            SumVal += I;
            if (X <= SumVal) {
                Console.WriteLine(I);
                break;
            }
        }
    }
}

解説

マイナス方向のジャンプを行わないとして、

0秒で到達可能な座標は0
1秒で到達可能な座標は0 1
2秒で到達可能な座標は0 1 2 3
3秒で到達可能な座標は0 1 2 3 4 5 6
4秒で到達可能な座標は0 1 2 3 4 5 6 7 8 9 10
5秒で到達可能な座標は0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
6秒で到達可能な座標は0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

といった形で等差数列の和までの座標に到達可能だと分かります。
また、マイナス方向のジャンプが意味をなさないことも分かります。

以上をふまえて、等差数列の和を順に求めて解いてます。