あなたのタスクは洪水災害をシミュレートすることです。
与えられた横断面図に対して、浸水部分の面積を求めてください。
この地域では絶えず雨が降り続けており、地域から溢れ出た水が両側の海に流れ込んでいると仮定します。 例えば、上記の横断面図では、雨水が洪水を引き起こし、その面積はそれぞれ 4、2、1、19、9 となります。
入力
1 行で文字列を与え、"/"、""、および"_" で傾斜と平地を表します。 例えば、上記の例の領域は文字列 “\ \ /// \ _ / \ / \ \ \ \ /_/ \ \ ///_ _ \ \ \ _ \ \ /_ \ /_/” で与えられます。
出力
以下の形式で出力してください：
A
K L1,L2,…,Lk
最初の行には洪水領域の総面積 A を印刷します。
2 行目には洪水領域の数 K と各領域の面積 Li（左から右へ）を印刷します。
制約
1 ≤ 文字列の長さ ≤ 20000
この問題を見たとき、まず思いついたのは、最初から 1 つずつ後ろに進んで、凹み始める場所を見つけ、高さが以前と同じになるまで追跡し続けることです。そして、再び下降し始めるまで進み、以前のプロセスを繰り返します。。
しかし、以前の下降の高さに達しなくなる状況に簡単に遭遇することに気づき、このアプローチを断念し、大規模なシミュレーションを書くことにしました：
横断面図を直接構築し、0 を空気、1 を山、2 を完全な水、3 を下降する半分の水、4 を上昇する半分の水として表します。
まず山の上の部分をすべて水で満たし、その後繰り返し実行します：左右の下方のいずれかの方向が空気である水を捨て、再び捨てられなくなるまで続けます。残ったものが私たちの水たまりです。
最後に DFS を使用して各水たまりを見つけ、面積を計算します。
その後、地図は 2 次元配列であることがわかり、ditu[MAXN][MAXN]と定義すると、すぐにメモリがオーバーフローします。したがって、常に下降または上昇する山はないはずなので、高さにそれほど多くのセルは必要ないと考え、小さな 2 次元を開くことを試みました。
2 つの TLE を取得しました
#include <stdio.h>
#define MAXN 20005
#define INF ((int)0x3f3f3f3f)
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) < (b) ? (b) : (a))
int a[MAXN] = {0};
int ditu[MAXN][1005] = {0};//0:空,1:山,2:水,3:下降する山,4:上昇する山
short vis[MAXN][1005] = {0};
int mmjimf[MAXN] = {0};
int newm = 0;
double dfs(int x, int y)
{
if (vis[x][y])
{
return 0.;
}
vis[x][y] = 1;
double value = 0;
switch (ditu[x][y])
{
case 2:
value = 1;
break;
case 3:
case 4:
value = 0.5;
break;
default:
return 0;
}
if (ditu[x][y] == 2) value += dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
else if (ditu[x][y] == 3)
{
value += dfs(x + 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
if (ditu[x - 1][y] != 4)
{
value += dfs(x - 1, y);
}
} else if (ditu[x][y] == 4)
{
value += dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
if (ditu[x + 1][y] != 3)
{
value += dfs(x + 1, y);
}
}
return value;
}
int main(void)
{
char c = getchar();
int newp = 1;
int zvdi = INF, zvgc = -INF;
while (c == '/' || c == '\\' || c == '_')
{
++newp;
switch (c)
{
case '/':
a[newp] = a[newp - 1] + 1;
break;
case '\\':
a[newp] = a[newp - 1] - 1;
break;
case '_':
a[newp] = a[newp - 1];
break;
}
if (a[newp] < zvdi)
{
zvdi = a[newp];
}
c = getchar();
}
for (int i = 1; i <= newp; ++i)
{
a[i] += (-zvdi + 1);
if (a[i] > zvgc)
{
zvgc = a[i];
}
}
for (int i = 1; i < newp; ++i)
{
int low = min(a[i], a[i + 1]);
int high = max(a[i], a[i + 1]);
for (int j = 1; j <= zvgc; ++j)
{
if (j <= low)
{
ditu[i][j] = 1;
} else if (j >= low && j <= high)
{
if (low != high)
{
if (a[i] > a[i + 1]) ditu[i][j] = 3;
else ditu[i][j] = 4;
} else
{
ditu[i][j] = 2;
}
} else if (j > high)
{
ditu[i][j] = 2;
}
}
}
int vcdc = 0;
do
{
vcdc = 0;
for (int j = zvgc; j >= 1; --j)
{
for (int i = 1; i < newp; ++i)
{
if (ditu[i][j] == 2 || ditu[i][j] == 3 || ditu[i][j] == 4)
{
if (!((ditu[i - 1][j] || ditu[i][j] == 3) && (ditu[i + 1][j] || ditu[i][j] == 4) && ditu[i][j - 1]))
{
++vcdc;
ditu[i][j] = 0;
}
}
}
}
} while (vcdc);
double mmji = 0;
for (int j = zvgc; j >= 1; --j)
{
for (int i = 1; i < newp; ++i)
{
switch (ditu[i][j])
{
case 2:
mmji += 1;
break;
case 3:
case 4:
mmji += 0.5;
break;
}
}
}
printf("%.0lf\n", mmji);
for (int i = 1; i < newp; ++i)
{
for (int j = zvgc; j >= 1; --j)
{
if (!vis[i][j])
{
double ans = dfs(i, j);
if (ans) mmjimf[++newm] = ans;
}
}
}
printf("%d ", newm);
for (int i = 1; i <= newm; ++i)
{
printf("%d ", mmjimf[i]);
}
return 0;
}
深刻なタイムリミット超過（TLE）に直面し、私は非常に悲痛な気持ちになりました。Bing を開き、全ネットを検索し、問題の解決策を見つけました。この解決策は私たちに教えてくれました
浸水区域から「\」と「/」のペアを考えることができます。
この問題は、どのようにして完全に水に浸された区間を構成するかが特に重要です。答えは、すべてのペアの区間の中で相互に含まれる区間をマージすることです。
どのようにマージするか？大きな区間に含まれる小さな区間は必ず大きな区間より先にスタックに入るため、これに基づいてマージできます。
横断面積をどのように計算するか？すべてのペアの「\」と「/」の間に形成される横断面は台形または三角形であり、問題を複数の小さな問題に分解して解決します。
私はこの考えに大いに触発され、この思考に基づいて書くことに決めました。少し書いた後、これはスタックを使う必要がないことに気づき、単に加算と減算を行うだけで済むようです。
その時、最初のアプローチをより暴力的に変え、各起点から出発し、以前の下降の高さに再び達しなくなったら、その起点を捨てて次の起点に切り替えることに気づきました。この方法は、あまり多くのメモリを浪費せず、また大規模なシミュレーションよりもはるかに速く、無事に AC を取得しました。
#include <stdio.h>
#define MAXN 20005
char sgn[MAXN] = {0};
double ans[MAXN] = {0};
double tot = 0;
int news = 0;
int newa = 0;
int main()
{
int h = 0;
char t = getchar();
while (t == '/' || t == '\\' || t == '_')
{
sgn[++news] = t;
t = getchar();
}
int i = 1;
while (i <= news)
{
double sum = .5, hi = 1;
if (sgn[i] != '\\')
{
++i;
continue;
}
int st = 1;
int j;
for (j = i + 1; j <= news && st > 0; ++j)
{
if (sgn[j] == '\\')
{
++st;
++hi;
sum += (hi - .5);
} else if (sgn[j] == '/')
{
--st;
--hi;
sum += (hi + .5);
} else
{
sum += hi;
}
}
if (st == 0)
{
i = j;
ans[++newa] = sum;
tot += sum;
} else
{
++i;
}
}
printf("%.0lf\n%d ", tot, newa);
for (int i = 1; i <= newa; ++i)
{
printf("%.0lf ", ans[i]);
}
return 0;
}
リハビリの道は続いています～～