Code Festival Team Relay 2018 : I - 一円を笑う者は一円に泣く

確信をもって提出するの難しそう。
https://beta.atcoder.jp/contests/cf18-relay-open/tasks/relay2018_i

問題

N個の商品の値段が与えられる。
各商品を購入する際、いくつかを組にして複数回に分けて会計することができる。
その際、支払金額は最寄りの5の倍数に丸められる。

最適な会計の分け方をしたとき、支払総額を最小化せよ。
また、同じ総額の組み合わせが多数ある場合、支払回数の最小値を答えよ。

解法

組み合わせに関して、商品を金額 mod 5の値で分類するのが良いのはわかる。
後は支払い方だが、合計金額mod5が2,1,0,4,3の順で支払うのが良い。
よって、以下の順で商品を組にしていこう。
以下金額はmod 5の値を示す。

• 金額3と金額4の商品をまとめ、総額 mod 5が2の商品として扱う。
• 金額4の商品を3つまとめ、総額 mod 5が2の商品として扱う。
• 金額4の商品を2つまとめ、総額 mod 5が3の商品として扱う。これは支払金額は減らないが、支払回数を減らす効果がある。
• 金額3の商品を2つまとめ、総額 mod 5が1の商品として扱う。
• 金額2と金額3の商品をまとめ、総額 mod 5が0の商品として扱う。これは支払金額は減らないが、支払回数を減らす効果がある。
• 金額2と金額4の商品をまとめ、総額 mod 5が1の商品として扱う。これは支払金額は減らないが、支払回数を減らす効果がある。
• 金額1と金額3の商品をまとめ、総額 mod 5が4の商品として扱う。これは支払金額は減らないが、支払回数を減らす効果がある。
• 金額1と金額4の商品をまとめ、総額 mod 5が0の商品として扱う。これは支払金額は減らないが、支払回数を減らす効果がある。
• 金額1の商品を2つまとめ、総額 mod 5が2の商品として扱う。これは支払金額は減らないが、支払回数を減らす効果がある。

あとはこれ以上支払金額や支払回数を減らす手順は無いので、最適な結果となる。

int N;
int C[5];
ll sum=0;

void hogemin(int a,int b) {
	int mi=min(C[a],C[b]);
	sum+=(a+b)/5*5*mi;
	C[a]-=mi;
	C[b]-=mi;
	C[(a+b)%5]+=mi;
}

void hogemul(int a,int v) {
	int mi=C[a]/v;
	sum+=(a*v)/5*5*mi;
	C[a]-=mi*v;
	C[(a*v)%5]+=mi;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int num=0;
	FOR(i,N) {
		cin>>x;
		sum+=x/5*5;
		C[x%5]++;
	}
	
	hogemin(3,4);
	hogemul(4,3);
	hogemul(4,2);
	hogemul(3,2);
	hogemin(2,3);
	hogemin(2,4);
	hogemin(1,3);
	hogemin(1,4);
	hogemul(1,2);
	
	num=C[1]+C[2]+C[3]+C[4];
	sum+=5*(C[3]+C[4]);
	
	
	cout<<sum<<" "<<max(1,num)<<endl;
}

まとめ

リレー向きな問題という気はする。