Monsters Battle Royale [AtCoder Beginner Contest 118 C]

atcoder.jp

相手を殴ったとき、自分の体力と同じだけ相手の体力を減らせるという設定のもと、体力 A を初期値として持つ n 体のモンスターたちが殴り合いをしたとき、最後に生き残ったモンスターの体力の最小値として考えられるものを出力せよ、という問題です。

問題文だけ読むと何やら複雑そうですが、解説にある通り、自分の体力と同じだけ相手の体力を減らせるという設定で2匹のモンスターが殴り合いをする様子には、ユークリッドの互除法の手順を見出すことができ、ここから「A1~An の n 個の数字の最大公約数は何か」という問題に帰着できます。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int temp = sc.nextInt();
		for (int i=0; i<n-1; i++) {
			temp = gcd(temp, sc.nextInt());
		}
		System.out.println(temp);
		
	}
	
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	
}

最大公約数を求めるメソッドが超コンパクトですが、自分で考えたものではなく、拾いものです。こういうのを自分で考えないから、この問題もコンテスト中に解けなかったんでしょうね。