解法

最初考えたこと

全く頭が動かない状態で問題を読んでたので、とりあえず”愚直なコードを書いてmを求める”ということをしてました。以下がそのコードです。

	#include <iostream>
	using namespace std;
	int main(int argc, char const *argv[]) {
	int n;
	cin>>n;
	int a[n];
	int max=0;
	for(int i=0;i<n;i++){
	int tmp;
	cin>>tmp;
	a[i]=tmp;
	if(tmp>max) max=tmp;
	}
	cout<<"max="<<max<<endl;
	int ans=0;
	int m=0;
	for(int i=1;i<100000*max;i++){
	int sum=0;
	for(int j=0;j<n;j++){
	sum+=i%a[j];
	}
	if(sum>ans){
	ans=sum;
	m=i;
	}
	}
	printf("m=%d,ans=%d\n",m,ans);
	return 0;
	}

by GitHub

はじめは、与えられる数列の最大値の余りが最大となるときのmのときだろって考えてたので、mを探すループ部分は以下の部分です。

[cpp] for(int i=1;i<100000*max;i++){ int sum=0; for(int j=0;j<n;j++){ sum+=i%a[j]; } if(sum>ans){ ans=sum; m=i; } } [/cpp]

sample2ぐらいならすぐ見つかると思ってたんですが全く答えと一致しなかったので、やけくそでループ回数増やしてます。アホですね。

ただ、やけくそでmを求めたおかげで、欲しいmの値は何でも存在するということに気がつけました。

アホなことをしたお蔭で、欲しいmは必ず存在するということがわかりました。なので、もっとシンプルに考えます。

余りの合計が最大のときはどのような時かといえば、すべての余りが最大のときの合計値です。

例えば2なら余りの最大値は1、3なら2、10なら9・・・のように、その数の余りの最大値はその数自身より1小さい数です。

よって、求める解は、与えられた数列から1引いた数値の合計値となります。ということで、私の書いたコードは次のようになりました。

	#include <iostream>
	using namespace std;
	int main(int argc, char const *argv[]) {
	int n;
	cin>>n;
	int sum=0;
	for(int i=0;i<n;i++){
	int tmp;
	cin>>tmp;
	sum+=tmp-1;
	}
	cout<<sum<<endl;
	return 0;
	}

by GitHub

コンテスト中ならこういうのはさっさと解きたいものですが、そうじゃないのでまあ失敗するのもいいかなあって。

ただ、mを愚直に求めに言ったのは問題慣れしてないというか、なんというか・・・という・・・。精進します。