kmjp's blog

競技プログラミング参加記です

AtCoder ARC #043 : A - 点数変換、B - 難易度

ARC

Cに手こずったけど、周りもCに手こずったので結果的にそこそこの順位でした。
http://arc043.contest.atcoder.jp/tasks/arc043_a
http://arc043.contest.atcoder.jp/tasks/arc043_b

A - 点数変換

N人のテスト得点はS[i]である。
このテスト得点を定数P,Qを用いて T_i = P \times S_i + Qで線形変換したとき、Tの平均値がA、最大値と最小値の差がBとなるP,Qを求めよ。

まずSをソートする。
T_{N-1} - T_0 = P \times (S_{N-1} - S_0) = Bより P = \frac{B}{S_{N-1} - S_0}。
また sum(T) = P \times sum(S) + N \times Q = A * Nより Q = A - \frac{P \times sum(S)}{N}。

int N;
ll A,B;
double P,Q;
ll sum;
ll S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	FOR(i,N) cin>>S[i], sum+=S[i];
	sort(S,S+N);
	
	if(S[N-1]==S[0]) return _P("-1\n");
	P=B*1.0/(S[N-1]-S[0]);
	double ave=sum*1.0/N;
	Q=A-P*ave;
	
	_P("%.12lf %.12lf\n",P,Q);
}

B - 難易度

N個の問題があり、それぞれの難易度はD[i]である。
これらから4問を選んだ時、2問目は1問目の２倍以上の難易度、3問目は2問目の２倍以上の難易度、4問目は3問目の２倍以上の難易度となるような選び方の総数を求めよ。

まずDを昇順ソートする。
i番目の問題が4問中j問目に来る組み合わせ数は、D[x]がD[i]が半分以下になるようなxに対し、それらが(j-1)問目になる組み合わせ数の和である。
xの上限は二分探索で求め、後は累積和を用いれば全体でO(N*logN)で解ける。
同じ難易度が複数個ある場合、lower_boundの使い方に注意。(自分はこれで1WAした)

int N;
ll D[101010];
ll dp[101010][4];
ll sum[101010][4];

ll mo=1000000007;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>D[i];
	D[N]=0;
	N++;
	sort(D,D+N);
	
	for(i=1;i<N;i++) {
		x=lower_bound(D,D+i+1,D[i]/2+1)-D;
		while(D[x]*2>D[i]) x--;
		dp[i][0]=1;
		dp[i][1]=sum[x][0];
		dp[i][2]=sum[x][1];
		dp[i][3]=sum[x][2];
		FOR(j,3) sum[i][j]=(sum[i-1][j]+dp[i][j])%mo;
		ret += dp[i][3];
	}
	
	cout<<ret%mo<<endl;
	
}

まとめ

今回のARCは難しいという意見もあるけど、自分はCが難しめなもののABDはいつも通りという感触だった。