AOJ1502 War

問題リンク War

• 解法

原点からの距離がkとなるマスは4*k個あります。体力がk以上の兵士は距離kのマスに到達することができ、k以上の体力を持つ兵士が4*k人以上いると、4*k+1番目以降の兵士はどう頑張ってもすでに他の兵士が到達したマスを通らざるを得なくなります。なので、距離がkのマスを占領できる兵士は最大で4*k人です。
また、体力が多い兵士は、原点から近いマスを埋めるような動きをするより、他の兵士が到達できないより遠くのマスへ行った方が得になると考えられます。
以上から次のような計算方法で答えが導き出せます。
兵士の体力の総和をresとする。
原点からの距離がk(1 <= k < 125)であるマスは、前述の議論から占領できる兵士の上限が決まっているので、resからカウントの超過分を引く（距離が125以上のマスについては、全ての兵士が重複することなく到達できるので超過分が無い）。
結果が答え。
本番中は半信半疑でこの解法を提出していました。

• ソース

import java.util.Scanner;

//War
public class AOJ1502 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] h = new int[n];
		long res = 0;
		for(int i=0;i<n;i++)res+=h[i]=sc.nextInt();
		for(int d=1;d<125;d++){
			int c = 0;
			for(int x:h)c+=x>=d?1:0;
			res-=Math.max(0, c-d*4);
		}
		System.out.println(res+1);
	}
	
	public static void main(String[] args) {
		new AOJ1502().run();
	}
}