tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM463 Div1Mediumとその他

463Med(500pts)
解法:変な制約から、a<=b<=c<=d<=e<=f...とおくと、最大となるのは(a+f)(b+e)(c+d)ghijkl...見たいな形になることが分かるので、それらを全部試す。
解法が分かったら実装は一瞬でした。制約の1.5以上を1.125以上にすると急に難しくなるらしいです(なぜだろう?)

import java.util.*;
public class Nisoku{
	public double theMax(double[]a){
		double ret=0;
		Arrays.sort(a);
		int n=a.length;
		for(int i=0;i<=n/2;i++){
			double t=1;
			for(int j=0;j<i;j++){
				t*=(a[j]+a[2*i-1-j]);
			}
			for(int j=2*i;j<n;j++)t*=a[j];
			ret=Math.max(ret,t);
		}
		return ret;
	}
}

CF#176 Div1A
解法:4つの塊を作ってそれぞれ別々にサイクルを作る
本当にこの解法で言いのか不安になる系の問題。特に成立しないときとか。

#include<stdio.h>
int ans[100000];
int main(){
	int a;scanf("%d",&a);
	if(a%4==2||a%4==3){
		printf("-1\n");
		return 0;
	}
	if(a%4==0){
		for(int i=0;i<a/4;i++){
			ans[i*2]=i*2+2;
			ans[i*2+1]=a-i*2;
			ans[a-1-i*2]=a-1-i*2;
			ans[a-2-i*2]=i*2+1;
		}
	}else{
		for(int i=0;i<a/4;i++){
			ans[i*2]=i*2+2;
			ans[i*2+1]=a-i*2;
			ans[a-1-i*2]=a-1-i*2;
			ans[a-2-i*2]=i*2+1;
		}
		ans[a/2]=a/2+1;
	}
	for(int i=0;i<a;i++)printf("%d ",ans[i]);
}

CF#176 Div1B
解法:1/1+1/2+1/3+...+1/N=O(log N)となることを使って、シフトして戻るところだけを更新するだけで済むようにずらしていく
右端が実装不安になる

#include<stdio.h>
int b[2000000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)b[i]=i+1;
	int t=0;
	for(int i=2;i<=a;i++){
		for(int j=(a-1)/i*i;j>=0;j-=i){
			if(j==(a-1)/i*i){
				b[t+a]=b[t+j];
			}else b[t+j+i]=b[t+j];
		}
		t++;
	}
	for(int i=0;i<a;i++)printf("%d ",b[t+i]);
}

ぜんぜん実装重いのといてないのですがそれは

追記
Nisokuはa,b,c>1.5なので、(a+b+c)<=a(b+c)が示せます。あと均すのは相加相乗平均みたいな考えかたでいけます。