AtCoderのPAST
次のPASTの問題へ
前のPASTの問題へ
第10回PAST G 方程式
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("32 2 -246");
//1.500000000000000000
}
else if (InputPattern == "Input2") {
WillReturn.Add("12 3 -45");
//1.279562760087743278
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static double mA;
static double mB;
static double mC;
static void Main()
{
List<string> InputList = GetInputList();
double[] wkArr = InputList[0].Split(' ').Select(pX => double.Parse(pX)).ToArray();
mA = wkArr[0];
mB = wkArr[1];
mC = wkArr[2];
double Result = ExecSanbuntansaku();
Console.WriteLine(Result);
}
// 三分探索で極小値を求める
static double ExecSanbuntansaku()
{
double L = 1;
double R = 2;
var PairHashSet = new HashSet<string>();
while (L + double.Epsilon < R) {
double C1 = (L * 2 + R) / 3;
double C2 = (L + R * 2) / 3;
double C1Val = CalcFunc(C1);
double C2Val = CalcFunc(C2);
if (C1Val < C2Val) {
R = C2;
}
else {
L = C1;
}
string Hash = string.Format("{0},{1}", L, R);
if (PairHashSet.Add(Hash) == false) {
break;
}
}
return L;
}
// Xの値を引数として、コストのSumを返す
static double CalcFunc(double pX)
{
return Math.Abs(mA * pX * pX * pX * pX * pX + mB * pX + mC);
}
}
解説
0との差に着目すれば、三分探索が使えます。