2004Eの解答

ACM/ICPC


2004Eの問題


回答者：ほへい

解法：水を入れて、溢れたら壁の低い区間を調べて判定処理
　　　　１．溢れる先が満杯でなければ、溢れる分を用いて溢れる先に処理を移動。
　　　　２．溢れる先が満杯なら、
　　　　　　Ａ．凹型であれば結合し、溢れた分を用いて同じ場所で処理
　　　　　　Ｂ．下り坂のようになっていたら、溢れた分を用いて溢れる先に処理を移動
　　　　３．水が溢れなくなるまで続ける

所要時間：３時間強、とにかくデバッグがヤバいです。
　　　　　　なまじサンプルが通るコードだったばっかりに…って悲劇。

速度：データセット瞬殺

実行環境：PenM 1.6GHz 512M Win2000

備考：決して難しい問題ではないです。ただ、この分量をすんなり書けるのは化け物かと。。。
　　　　僕の中では捨て問としての地位が揺るぎない感じです。
　　　　双方向リストを使ったプログラムは初でしたが、便利だなぁと思いました。

#include <stdio.h>

FILE *fp_in, *fp_out;
static char *f_source = "2004E_in.txt";
static char *f_answer = "2004E_out.txt";

typedef struct {
   int position;
   int height;
} Wall;

typedef struct __Section {
   int max_water;
   int current_water;
   Wall left_wall;
   Wall right_wall;
   struct __Section *prev, *next;
} Section;

typedef struct {
   int position;
   int ejection_rate;
} Faucet;

typedef struct {
   int position;
   int time;
} Measurement;

Section start_section, end_section;                // 始点・終点を示すダミー
Section sections[10];
Section temp_sections[10];
Faucet faucets[9];
Measurement measurements[9];
int num_boards, num_faucets, num_measurements;

void setValue(void);                                         // 各値をセットする。
void getAnswer(void);                                        // データセットのループ処理をする関数
double measureHeight(Section *section);                      // その区間の水位を返す
void flowWater(int plus_water, Section *section);            // 水を流す再帰関数
Section *searchSection(int position, Section *section);      // pointがどの区間に属するかを返す
void setMaxwater(Section *section);                          // その区間の水量の最大をセットする
void resetSections(void);                                    // 測定毎に区間をリセットする
int lowerHeight(Section *section);                           // その区間の壁の低い方を返す
void connectSections(Section *section, Section *temp);       // 二つの区間を結合する
int isMax(Section *section);                                 // その区間が水で満たされているか

void printSections(Section *section);                // デバッグ用。全区間の情報をコンソールに表示
                                                    // 必要に応じて挿入（削除済み）

int main(void)
{
   int num_dataset;
   fp_in = fopen(f_source, "r");
   fp_out = fopen(f_answer, "w");
   
   fscanf(fp_in, "%d", &num_dataset);  
   for(; num_dataset > 0; num_dataset--) {
       setValue();
       getAnswer();
   }
   fclose(fp_out);
   fclose(fp_in);
   
   return 0;
}

void setValue()
{
   int i;
   fscanf(fp_in, "%d", &num_boards);

   sections[0].left_wall.position = 0;
   sections[0].left_wall.height = 50;

   fscanf(fp_in, "%d%d", &sections[0].right_wall.position, &sections[0].right_wall.height);

   sections[0].prev = &start_section;
   start_section.next = &sections[0];
   sections[0].next = &sections[1];

   for(i = 1;i < num_boards; i++) {
       fscanf(fp_in, "%d", &sections[i].right_wall.position);
       fscanf(fp_in, "%d", &sections[i].right_wall.height);
       sections[i].left_wall.position = sections[i - 1].right_wall.position;
       sections[i].left_wall.height = sections[i - 1].right_wall.height;
       sections[i].prev = &sections[i - 1];
       sections[i].next = &sections[i + 1];

       if(i == num_boards - 1) {
           sections[i + 1].left_wall.position = sections[i].right_wall.position;
           sections[i + 1].left_wall.height = sections[i].right_wall.height;
           sections[i + 1].right_wall.position = 100;
           sections[i + 1].right_wall.height = 50;
           sections[i + 1].prev = &sections[i];
           sections[i + 1].next = &end_section;
           end_section.prev = &sections[i + 1];
       }
   }
   
   fscanf(fp_in, "%d", &num_faucets);
   for(i = 0; i < num_faucets; i++) {
       fscanf(fp_in, "%d%d", &faucets[i].position, &faucets[i].ejection_rate);
   }
   
   fscanf(fp_in, "%d", &num_measurements);
   for(i = 0; i < num_measurements; i++) {
       fscanf(fp_in, "%d%d", &measurements[i].position, &measurements[i].time);
   }
   
   for(i = 0; i < num_boards + 1; i++) {
       sections[i].current_water = 0;
       setMaxwater(&sections[i]);
       temp_sections[i] = sections[i];
   }
}

void setMaxwater(Section *section)
{
   int temp_height, temp_width;
   temp_width = section->right_wall.position - section->left_wall.position;
   if(section->left_wall.height > section->right_wall.height) {
       temp_height = section->right_wall.height;
   }
   else {
       temp_height = section->left_wall.height;
   }
   section->max_water = 30 * temp_height * temp_width;
}

void resetSections()
{
   int i;
   for(i = 0; i < num_boards + 1; i++) {
       sections[i] = temp_sections[i];
   }
   start_section.next = &sections[0];
   end_section.prev= &sections[num_boards];
}

void getAnswer()
{
   int i, j;
   int water;
   double answer;
   
   for(i = 0; i < num_measurements; i++) {
       resetSections();
       for(j = 0; j < num_faucets; j++) {
           water = faucets[j].ejection_rate * measurements[i].time;
           flowWater(water, searchSection(faucets[j].position, start_section.next));
       }
       answer = measureHeight(searchSection(measurements[i].position, start_section.next));
       fprintf(fp_out, "%lf\n", answer);
   }
}

Section *searchSection(int position, Section *section)
{
   if(section != &end_section) {
       if(position < section->right_wall.position) {
           return section;
       }
       else {
           return searchSection(position, section->next);
       }
   }
   return NULL;
}

int isMax(Section *section)
{
   if(section->current_water == section->max_water) {
       return 1;
   }
   return 0;
}

void flowWater(int water, Section *section) 
{
   int temp_water;
   section->current_water += water;
   temp_water = section->current_water - section->max_water;
   if(temp_water > 0) {
       Section *temp_section;
       section->current_water = section->max_water;
       if(section->right_wall.height != section->left_wall.height) {
           if(section->right_wall.height < section->left_wall.height) {
               temp_section = section->next;
           }
           else {
               temp_section = section->prev;
           }
           if(isMax(temp_section)) {
               if(lowerHeight(section) != lowerHeight(temp_section)) {
                   flowWater(temp_water, temp_section);
               }
               else {
                   connectSections(section, temp_section);
                   flowWater(temp_water, section);
               }
           }
           else {
               flowWater(temp_water, temp_section);
           }
       }
   }
}

void connectSections(Section *section, Section *temp) {
   section->current_water += temp->current_water;
   if(section->next == temp) {
       section->right_wall = temp->right_wall;
       (temp->next)->prev = section;
       section->next = temp->next;
   }
   else if(section->prev == temp) {
       section->left_wall = temp->left_wall;
       (temp->prev)->next = section;
       section->prev = temp->prev;
   }
   setMaxwater(section);
}

int lowerHeight(Section *section) {
   if(section->right_wall.height > section->left_wall.height) {
       return section->left_wall.height;
   }
   return section->right_wall.height;
}

double measureHeight(Section *section)
{
   double answer;
   int temp_width = section->right_wall.position - section->left_wall.position;
   answer = (double)section->current_water / (temp_width * 30);
   return answer;
}

void printSections(Section *section)
{
   if(section != &end_section) {
       printf("%d %d\n", section->left_wall.position, section->right_wall.position);
       printf("%d %d\n", section->left_wall.height, section->right_wall.height);
       printSections(section->next);
   }
}