Codeforces Beta Round #90 B: Before Exam

Codeforces

問題概要

長さN(<100)の配列Aがある。また、カードがK(<=N)枚ある。各カードにはN/Kだけ配列のインデックスが書いてある。重複は無い。カードの情報が何枚分か与えられるので、カードに書かれているインデックスをキーとした数値の平均値として考えられるもののうち最小の値と最大の値を出力する問題。

考えたこと

  • 答えが浮動小数点数だけど、合計点で考えればよいので実質整数でできる。
  • まだ不定なカードがあるとしたら、残ってるうち小さい方(大きい方)から貪欲に選んでいけばよい。
  • サブミット。wrong answer pretest 1。サンプル通って無いじゃん！
  • グローバル変数とローカル変数で変数名が衝突していた。入力を真っ当に受けとることもできないとか競技プログラミング何年目だよ…。
  • そういえばカードが何枚オープンになってるか調べて無かった。付け加えておこう。
    • 結果的にはこの修正のおかげでBが落ちなかった。
  • サブミット。pretest passed。
  • コンテスト終了直前に、min_element(tot, tot+Q)がQ=0のとき怪しいことに気づいた。Q=0のときは最小値、最大値を適当に初期化してやる。
  • システムテスト無事通ってた。しかし罠をかいくぐっていたもののそれで撃墜できなかったのはちょっと反省。

本番で通ったコード

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

const int MAX_N = 100;
const int MAX_Q = 100;
const int INF = 1<<29;

int N, K, M, Q;
int as[MAX_N];
bool used[MAX_N];
int tot[MAX_Q];

void solve(){
	int maxi = *max_element(tot, tot+Q),
		mini = *min_element(tot, tot+Q);
	if(Q==0){
		maxi = 0;
		mini = INF;
	}

	int res = count(used, used+N, true);
	if(res / M < K){
		vector<int> unused;
		for(int i=0; i<N; i++)if(!used[i]){
			unused.push_back(as[i]);
		}

		sort(unused.begin(), unused.end());
		if((int)unused.size() >= M){
			maxi = max(maxi, accumulate(unused.rbegin(), unused.rbegin() + M, 0));
			mini = min(mini, accumulate(unused.begin(), unused.begin() + M, 0));
		}
	}

	printf("%.8f %.8f\n", (double)mini/M, (double)maxi/M);
}


int main(){
	scanf("%d%d",&N,&K);
	M = N / K;
	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		int x;
		for(int j=0; j<M; j++){
			scanf("%d",&x);
			x--;
			used[x] = true;
			tot[i] += as[x];
		}
	}

	solve();

	return 0;
}