[[ACM/ICPC]]&br;
&br;
&br;
[[2004Eの問題:http://www.acm-japan.org/past-icpc/domestic2004/E.jp/E.html]] by [[ほへい]] &br;
[[2004Eの問題:http://www.acm-japan.org/past-icpc/domestic2004/E.jp/E.html]] &br;
&br;
&br;
回答者：[[ほへい]]&br;
&br;
解法：水を入れて、溢れたら壁の低い区間を調べて判定処理&br;
　　　　１．溢れる先が満杯でなければ、溢れる分を用いて溢れる先に処理を移動。&br;
　　　　２．溢れる先が満杯なら、&br;
　　　　　　Ａ．凹型であれば結合し、溢れた分を用いて同じ場所で処理&br;
　　　　　　Ｂ．下り坂のようになっていたら、溢れた分を用いて溢れる先に処理を移動&br;
　　　　３．水が溢れなくなるまで続ける&br;
&br;
所要時間：３時間強、とにかくデバッグがヤバいです。&br;
　　　　　　なまじサンプルが通るコードだったばっかりに…って悲劇。&br;
&br;
速度：データセット瞬殺&br;
&br;
実行環境：PenM 1.6GHz 512M Win2000&br;
&br;
備考：決して難しい問題ではないです。ただ、この分量をすんなり書けるのは化け物かと。。。&br;
　　　　僕の中では捨て問としての地位が揺るぎない感じです。&br;
　　　　双方向リストを使ったプログラムは初でしたが、便利だなぁと思いました。&br;
&br;
 #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);
    }
 }
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS