トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
ABC-118-C Monsters Battle Royale
■■■問題■■■
N体のモンスターが居て、それぞれ 1 , 2 , ・・・ , Nと番号付けられています。
はじめ、モンスターiの体力は、Aiです。
以降、体力が1以上のモンスターを生きているモンスターと呼びます。
生きているモンスターが 1体になるまで以下を繰り返します。
●ランダムに 1体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。
●その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。
最後に生き残ったモンスターの最終的な体力の最小値を求めてください。
■■■入力■■■
N
A1 A2 ・・・ AN
●入力は全て整数である
●2 <= N <= 10万
●1 <= Ai <= 10億
■■■出力■■■
最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。
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("4");
WillReturn.Add("2 10 8 40");
//2
//1番目のモンスターだけが攻撃し続けた場合、
//最後に生き残ったモンスターの体力は2となり、
//このときが最小です。
}
else if (InputPattern == "Input2") {
WillReturn.Add("4");
WillReturn.Add("5 13 8 1000000000");
//1
}
else if (InputPattern == "Input3") {
WillReturn.Add("3");
WillReturn.Add("1000000000 1000000000 1000000000");
//1000000000
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
int GCD = wkArr[0];
for (int I = 1; I <= wkArr.GetUpperBound(0); I++) {
GCD = DeriveGCD(GCD, wkArr[I]);
}
Console.WriteLine(GCD);
}
//ユークリッドの互除法で2数の最大公約数を求める
static private int DeriveGCD(int pVal1, int pVal2)
{
pVal1 = Math.Abs(pVal1);
pVal2 = Math.Abs(pVal2);
int WarareruKazu = Math.Max(pVal1, pVal2);
int WaruKazu = Math.Min(pVal1, pVal2);
while (true) {
int Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
}
解説
考察を繰り返したら、
ユークリッドの互除法と同じ動きとなりますので、
最大公約数が解となります。