SRM 528 Div1

年内最後のするめ。

250:Cut
うなぎを切る問題。うなぎかわいそうです。誰もそれに対して訴えないのが異常。
Fox Ciel黒すぎ…
じゃなくて適当にGreedyするだけ

public class Cut{
	public int getMaximum(int[]a,int b){
		int ret=0;
		for(int i=0;i<a.length;i++)if(a[i]==10){
			ret++;
			a[i]=-1;
		}
		for(int j=20;j<=1000;j+=10){
			for(int i=0;i<a.length;i++){
				if(b>j/10-2&&a[i]==j){
					ret+=j/10;
					a[i]=-1;
					b-=j/10-1;
				}
			}
		}
		for(int i=0;i<a.length;i++){
			while(b>0&&a[i]>10){
				b--;
				ret++;
				a[i]-=10;
			}
			System.out.println(ret+" "+b);
		}
		return ret;
	}
}

500:SPartition
SPartitionってなんですか？
とりあえず見た瞬間に半分全列挙を書く。vectorだと間に合わないことをtest中に発見して配列に書き直してたらあらたいへんもうこんな時間。vector不快すぎ…

#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
	struct wolf{
		int size;//Plus:X Minus:Y
		bool bit[20];
		wolf(int a,int b[20]){
			size=a;
			for(int i=0;i<20;i++)bit[i]=b[i];
		}
		wolf(){

		}
	};
	int Abs(int a){return a<0?-a:a;}
	inline bool operator<(const wolf &a,const wolf &b){
		if(a.size!=b.size)return a.size<b.size;
		for(int i=0;i<Abs(a.size);i++){
			if(a.bit[i]!=b.bit[i])return a.bit[i]<b.bit[i];
		}
		return false;
	}
class SPartition{
	public:


	wolf dat[1<<20];
	long long getCount(string a){
		int now=0;
		for(int i=0;i<(1<<(a.size()/2));i++){
			bool ok=true;
			int X=0;
			int Y=0;
			int x[20];
			int y[20];
			for(int j=0;j<a.size()/2;j++){
				if(i&(1<<j))x[X++]=(a[j]=='o'?1:0);
				else y[Y++]=(a[j]=='o'?1:0);
			}
			for(int j=0;j<min(X,Y);j++){
				if(x[j]!=y[j])ok=false;
			}
			if(!ok)continue;
			int S[20];
			int ind=0;
			if(X<Y)for(int j=X;j<Y;j++)S[ind++]=y[j];
			else for(int j=Y;j<X;j++)S[ind++]=x[j];
		//	for(int j=0;j<20;j++)printf("%d",S[j]);
			//printf(":%d\n",X-Y);
			dat[now++]=wolf(X-Y,S);
		}
		std::sort(dat,dat+now);
//printf("---------\n");

	//	printf("%d\n",now);
		long long ret=0;
		for(int i=0;i<(1<<(a.size()/2));i++){
			bool ok=true;
			int X=0;
			int Y=0;
			int x[20];
			int y[20];
			for(int j=0;j<a.size()/2;j++){
				if(i&(1<<j))x[X++]=(a[a.size()/2+j]=='o'?1:0);
				else y[Y++]=(a[a.size()/2+j]=='o'?1:0);
			}
			int t=min(X,Y);
			for(int j=0;j<t;j++){
				if(x[X-1-j]!=y[Y-1-j])ok=false;
			}
			if(!ok)continue;
			//printf("CALL\n");
			int S[20];
			int ind=0;
			if(X<Y)for(int j=0;j<Y-X;j++)S[ind++]=y[j];
			else for(int j=0;j<X-Y;j++)S[ind++]=x[j];
		//	for(int j=0;j<S.size();j++)printf("%d",S[j]);
		//	printf(":%d\n",y.size()-x.size());
			ret+=upper_bound(dat,dat+now,wolf(Y-X,S))-lower_bound(dat,dat+now,wolf(Y-X,S));
		//	printf("%lld\n",ret);
		}
		return ret;
	}
};

1000:wolf
狼です

Challenge Phase:
if(L[i]%10)がif(L[i]%10==0)と同値だと勘違いして-25

System Test:
両方とおる

Result:
230.19 + 237.14 + 0 - 25 = 442.43(128th)
Rating:
1659 -> 1753 (+96)

年末最後がこれで嬉しいですね。
しかしPKUずっとやってることにより早解き力がなくなってしまったのでEasyもぱっとしないしMediumもゴミなので、レッドコーダーに憧れたらTopCoderの過去問で練習(廃人プレイの意)します。