AOJ-ICPC 1285 - 備忘録

今日はこの問題。

グラフを書くときに使うインクの量を計算しましょう、という問題。
問題文が英語でややこしくて、理解するのに１時間ぐらいかかりました。
以下、簡単に説明。

入力として、まずnとwの値が与えられます。その後n個の値v_1, v_2, ... v_nが与えられます。
wとは幅のことであり、例えばv_k(kはn以下の自然数)が0以上w未満である場合はグラフのうち一番左の部分の値が1大きくなります。w以上2w未満の場合は左から2番目の部分の値が…というふうになります。
例えば問題文のサンプルとしてでてくるグラフでは、n = 10, w = 10となっており、0以上10未満を満たす値が5個、10以上20未満を満たす値が3個、…というように入力で与えられているのです。
そして色の塗り方。一番左が最も濃く、一番右がもっとも薄くなるようにします。色の濃さは(その部分の値 / もっとも値が大きい部分の値) * (白以外の部分で、左から何番めか / 白以外の部分がいくつあるか)で求まります。
言葉で表現するのは難しい…。

答えはこんな感じ。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <iomanip>
  
using namespace std;

int main()
{
	int  n, w;
	while(1){
		cin >> n >> w;
		if(n == 0 && w == 0) break;
		double height[100] = {0};
		int howmanyranges = 0;
		for(int i = 0; i < n; i++){
			int v;
			cin >> v;
			int j = 0;
			while(1){
				if(v >= j * w && v < (j + 1) * w){
					height[j]++;
					break;
				}
				else j++;
			}
			howmanyranges = max(howmanyranges, (v / w + 1));
		}
		double maxheight = 0;
		for(int i = 0; i < 100; i++){
			maxheight = max(maxheight, height[i]);
		}
		double ans = 0;
		if(howmanyranges == 1) ans = 0;
		else {
			for(int i = 0; i < 100; i++){
				ans += ((howmanyranges - 1 - i) * height[i]) / ((howmanyranges - 1) * maxheight);			
			}
		}
		ans += 0.01;
		cout << setprecision( 6 ) << ans << endl;
	}
}

heightはその名の通り高さを表します。k番目はk * w以上(k + 1) * w未満の値がいくつあるかを表します。maxheightはそのうちもっとも高いものを表します。
howmanyrangesはいくつ領域があるかを表します。一番大きなvの値を幅wで割って1を足せば求められます。
howmanyrangesが1のときはインクを使わないので答えは0(この後0.1を足す)になります。
そうでない場合は一つ一つの部分について計算して足し合わせていきます。
最後に0.1を足して、一応6桁まで表示して終わり。

英語の問題を読むのが大変でした。英語勉強します。