AOJ本の読書メモ
AOJ
次のAOJの問題へ
前のAOJの問題へ
AOJ 0211 みんなでジョギング
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("2");
WillReturn.Add("4 3");
WillReturn.Add("5 4");
WillReturn.Add("5");
WillReturn.Add("789 289");
WillReturn.Add("166 46");
WillReturn.Add("9 4");
WillReturn.Add("617 252");
WillReturn.Add("972 303");
WillReturn.Add("2");
WillReturn.Add("8 5");
WillReturn.Add("32 20");
WillReturn.Add("0");
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int CurrInd = 0;
while (true) {
int N = int.Parse(InputList[CurrInd]);
if (N == 0) break;
string[] InputArr = InputList.Skip(CurrInd + 1).Take(N).ToArray();
Solve(InputArr);
CurrInd += N + 1;
}
}
struct DataInfoDef
{
internal long Distance;
internal long Speed;
}
static List<DataInfoDef> mDataInfoList = new List<DataInfoDef>();
static void Solve(string[] pInputArr)
{
mDataInfoList.Clear();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
for (long I = 0; I <= pInputArr.GetUpperBound(0); I++) {
SplitAct(pInputArr[I]);
DataInfoDef WillAdd;
WillAdd.Distance = wkArr[0];
WillAdd.Speed = wkArr[1];
mDataInfoList.Add(WillAdd);
}
long ACycle = 1; // LCMの単位元は1
long FirstDistance = mDataInfoList[0].Distance;
long FirstSpeed = mDataInfoList[0].Speed;
foreach (DataInfoDef EachDataInfo in mDataInfoList.Skip(1)) {
long Sahen = FirstDistance * EachDataInfo.Speed;
long Uhen = FirstSpeed * EachDataInfo.Distance;
long CurrLCM = DeriveLCM2(Sahen, Uhen);
long CurrACycle = CurrLCM / Sahen;
ACycle = DeriveLCM2(ACycle, CurrACycle);
}
//Console.WriteLine("ACycle={0}", ACycle);
long TotalTime = ACycle * FirstDistance / FirstSpeed;
//Console.WriteLine("TotalTime={0}", TotalTime);
foreach (DataInfoDef EachDataInfo in mDataInfoList) {
Console.WriteLine(ACycle * FirstDistance * EachDataInfo.Speed
/ FirstSpeed / EachDataInfo.Distance);
}
}
// 2つの数のLCMを求める
static long DeriveLCM2(long p1, long p2)
{
long GCD = DeriveGCD(p1, p2);
return (p1 / GCD) * p2;
}
// ユークリッドの互除法で2数の最大公約数を求める
static long DeriveGCD(long pVal1, long pVal2)
{
long WarareruKazu = pVal2;
long WaruKazu = pVal1;
while (true) {
long Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
}
解説
まずは、2人だけで考えます。
2人が一致することは必要条件であります。
距離をD1 , 速度をS1
距離をD2 , 速度をS2
とします。
1人目の周回数をA,2人目の周回数をBとします。
すると
D1 / S1 * A = D2 / S2 * B
変形して
D1 * S2 * A = D2 * S1 * B
左辺と右辺 は、LCM(D1 * S2 ,D2 * S1) の倍数ですが
なるべく小さいほうが良いので
A = LCM / D1 / S2
になります。
同様に1人目と3人目で一致することを考えた時の
Aの周回数を考えると
LCM(1人目と2人目でのAの最小周回数 ,
1人目と3人目でのAの最小周回数 ,
1人目と4人目でのAの最小周回数 ,
1人目と5人目でのAの最小周回数)
となるので、
これから全員の周回数を求めることができます。
実装で
除算での切り捨てが発生しないように注意する必要があります。