結果

問題 No.385 カップ麺生活
コンテスト
ユーザー 37zigen
提出日時 2016-07-01 23:30:18
言語 Java
(openjdk 23)
結果
AC  
実行時間 153 ms / 2,000 ms
コード長 3,737 bytes
コンパイル時間 2,365 ms
コンパイル使用メモリ 84,720 KB
実行使用メモリ 55,428 KB
最終ジャッジ日時 2024-10-04 22:29:15
合計ジャッジ時間 7,598 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class  Main{
	public static void main(String[] args){
		new Main().solver();
	}
	void solver(){
		Scanner sc=new Scanner(System.in);
		int M=sc.nextInt();
		int N=sc.nextInt();
		int[] C=new int[N];
		for(int i=0;i<N;i++){
			C[i]=sc.nextInt();
		}

		// size is 1229
		ArrayList<Integer> primeList=primeList(10010);

		Arrays.sort(C);

		int[] possible_num=new int[10010];



		for(int j=M;j>=0;j--){
			for(int i=0;i<N;i++){
				if(j+C[i]<=M){
					if(possible_num[j+C[i]]>0||j+C[i]==M)
						possible_num[j]=Math.max(possible_num[j+C[i]]+1,possible_num[j]);
				}
			}
		}
		long ans=0;
		long max=0;
		for(int i=1;i<M;i++){
			if(primeList.contains(i)){
				ans+=possible_num[i];
//				System.out.println(i+" "+possible_num[i]);
			}
		}
		for(int i=0;i<M;i++){
			max=Math.max(max, possible_num[i]);
		}
		ans+=max;
		System.out.println(ans);

	}
	boolean[] isPrimeArray(int max){
		boolean[] isPrime=new boolean[max+1];
		Arrays.fill(isPrime, true);
		isPrime[0]=isPrime[1]=false;
		for(int i=2;i*i<=max;i++){
			if(isPrime[i]){
				for(int j=2;j*i<=max;j++){
					isPrime[j*i]=false;
				}
			}
		}
		return isPrime;
	}
	/*
	 * max以下の素数のリストを返す
	 */
	ArrayList<Integer> primeList(int max){
		boolean[] isPrime=isPrimeArray(max);
		ArrayList<Integer> primeList=new ArrayList<Integer>();
		for(int i=2;i<=max;i++){
			if(isPrime[i]){
				primeList.add(i);
			}
		}
		return primeList;
	}
	/*
	 * numをprimeListの素数をもとに素因数分解し、因数を
	 * ArrayList<Factor>の形で返す。1は含まれない。
	 * primeListにはnumの平方根以下の素数が含まれていなければならない。
	 *
	 */
	ArrayList<Factor> primeFactorF(ArrayList<Integer> primeList,long num){
		ArrayList<Factor> ret=new ArrayList<Factor>();
		for(int p:primeList){
			int exp=0;
			while(num%p==0){
				num/=p;
				exp++;
			}
			if(exp>0)ret.add(new Factor(p,exp));
		}
		if(num>1)ret.add(new Factor(num,1));
		return ret;
	}
	class Factor{
		long base,exp;
		Factor(long base,long exp){
			this.base=base;
			this.exp=exp;
		}
	}
	/*
	 * 戻り値：約数の和
	 * verified:yukicoder No.278
	 */
	long sum_d(ArrayList<Factor> fs){
		long sum=1;
		for(Factor f:fs){
			sum*=Long.parseLong((BigInteger.ONE.subtract(pow_big(f.base,f.exp+1))).divide(BigInteger.ONE.subtract(BigInteger.valueOf(f.base))).toString());
		}
		return sum;
	}
	BigInteger pow_big(long a,long n){
		BigInteger A=new BigInteger(String.valueOf(a));
		BigInteger ans=BigInteger.ONE;
		while(n>=1){
			if(n%2==0){
				A=A.multiply(A);
				n/=2;
			}else if(n%2==1){
				ans=ans.multiply(A);
				n--;
			}
		}
		return ans;
	}

	/*Verified:yukicoder377
	 * Eulerのφ関数(Euler's totient function) 1からnまでの自然数のうちnと互いに素なものの個数を数える。
	 * φ(mn)=φ(m)φ(n) (gcd(m,n)=1) なぜならば、chinese reminder theoremより、 a mod mnと
	 * (a mod n)と(b mod m)は全単射。 φ(p^k)=p^k-p^(k-1)=p^k(1-1/p)
	 * よってφ(p^k*q^k)=n(1-1/p)(1-1/q)という風にできる。
	 */

	long totient_function(ArrayList<Factor> f, long n) {
		long ret = n;
		for (int i = 0; i < f.size(); i++) {
			ret = ret - ret / f.get(i).base;
		}
		return ret;
	}
	// nの約数を列挙。1とnを含む。
	ArrayList<Long> enum_div(ArrayList<Factor> f) {
		ArrayList<Long> ret = new ArrayList<Long>();
		ret.add(1L);
		for (int i = 0; i < f.size(); i++) {
			long a = 1;
			int n = ret.size();
			for (int j = 0; j < f.get(i).exp; j++) {
				a *= f.get(i).base;
				for (int k = 0; k < n; k++) {
					ret.add(ret.get(k) * a);
				}
			}
		}
		return ret;
	}
}
0