2004Eの解答
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[ACM/ICPC]]&br;
&br;
&br;
[[2004Eの問題:http://www.acm-japan.org/past-icpc/domestic2004/E.jp/E.html]] &br;
&br;
&br;
回答者:[[ほへい]]&br;
&br;
解法:水を入れて、溢れたら壁の低い区間を調べて判定処理&br;
1.溢れる先が満杯でなければ、溢れる分を用いて溢れる先に処理を移動。&br;
2.溢れる先が満杯なら、&br;
A.凹型であれば結合し、溢れた分を用いて同じ場所で処理&br;
B.下り坂のようになっていたら、溢れた分を用いて溢れる先に処理を移動&br;
3.水が溢れなくなるまで続ける&br;
&br;
所要時間:3時間強、とにかくデバッグがヤバいです。&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", §ions[0].right_wall.position, §ions[0].right_wall.height);
sections[0].prev = &start_section;
start_section.next = §ions[0];
sections[0].next = §ions[1];
for(i = 1;i < num_boards; i++) {
fscanf(fp_in, "%d", §ions[i].right_wall.position);
fscanf(fp_in, "%d", §ions[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 = §ions[i - 1];
sections[i].next = §ions[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 = §ions[i];
sections[i + 1].next = &end_section;
end_section.prev = §ions[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(§ions[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 = §ions[0];
end_section.prev= §ions[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);
}
}
終了行:
[[ACM/ICPC]]&br;
&br;
&br;
[[2004Eの問題:http://www.acm-japan.org/past-icpc/domestic2004/E.jp/E.html]] &br;
&br;
&br;
回答者:[[ほへい]]&br;
&br;
解法:水を入れて、溢れたら壁の低い区間を調べて判定処理&br;
1.溢れる先が満杯でなければ、溢れる分を用いて溢れる先に処理を移動。&br;
2.溢れる先が満杯なら、&br;
A.凹型であれば結合し、溢れた分を用いて同じ場所で処理&br;
B.下り坂のようになっていたら、溢れた分を用いて溢れる先に処理を移動&br;
3.水が溢れなくなるまで続ける&br;
&br;
所要時間:3時間強、とにかくデバッグがヤバいです。&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", §ions[0].right_wall.position, §ions[0].right_wall.height);
sections[0].prev = &start_section;
start_section.next = §ions[0];
sections[0].next = §ions[1];
for(i = 1;i < num_boards; i++) {
fscanf(fp_in, "%d", §ions[i].right_wall.position);
fscanf(fp_in, "%d", §ions[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 = §ions[i - 1];
sections[i].next = §ions[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 = §ions[i];
sections[i + 1].next = &end_section;
end_section.prev = §ions[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(§ions[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 = §ions[0];
end_section.prev= §ions[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);
}
}
ページ名: