競技プログラミング風 C++問題集【第4回】

TsudaNobuhide

２次元世界の水たまり（難易度：★★★☆☆）

問題

2次元世界での地面の高さ（1～9）が、’1’～’9′ の文字列で与えられる時、上空から雨が充分降ったときにその部分に貯まる水の面積を返す関数 int areaOfThePods(const string& str) を実装しなさい。

なお、高さが指定された部分の左右の地面高はマイナス無限大であるものとし、左右の端から水が溢れるものとする。また、引数文字列中に ‘1’～’9′ 以外の文字が含まれていた場合は -1 を返すものとする。

例えば、引数に “3141592653” が与えられた場合の地形は下図のようになる。

競技プログラミング風C＋＋問題集【第4回】_01

ここに上空から充分な雨が降ると、下図の “○” 部分に水が貯まるので、貯まる水の面積は9となる。

競技プログラミング風C＋＋問題集【第4回】_02
[java] #include <iostream> // 標準入出力ライブラリ
#include <string>
#include <vector>
#include <deque>
#include <unordered_set>
using namespace std; // std 名前空間使用
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
int areaOfThePods(const string& str) {
// ToDo: ここに str で指定された地形に貯まる水の面積を返すコードを記述
return 0;
}
int main() {
DO_TEST( areaOfThePods("1234565432") == 0 );
DO_TEST( areaOfThePods("5432123456") == 16 );
DO_TEST( areaOfThePods("5432123456") == 16 );
DO_TEST( areaOfThePods("3141592653") == 9 );
DO_TEST( areaOfThePods("3121592653") == 9 );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・ある地点にどれだけの水が貯まるかは、左右の壁の高さとその場所の高さで決まるぞ。
・左右の壁の高さが異なる場合、低い方の壁の高さまで水が貯まるぞ。
・その地点の高さが、左右の壁の低い方以上の場合は、水は貯まらないぞ。

解答例

[java] int areaOfThePods(const string& str) {
#if 1
// 各地点からみた左右の壁の高さを予め計算しておく版：
for(auto ch: str) {
if( ch < ‘1’ || ch > ‘9’ ) return -1; // 範囲外の文字を含んでいた場合
}
const int WD = str.size();
vector<int> lt(WD); // 各地点の左方向壁最大高さ
int mxlt = 0; // 左方向壁最大高さ
for (int i = 0; i != WD – 1; ++i) { // 左から順にスキャン
lt[i] = mxlt;
mxlt = max(mxlt, str[i] – ‘0’);
}
vector<int> rt(str.size()); // 各地点の右方向壁最大高さ
int mxrt = 0; // 右方向壁最大高さ
for(int i = WD; –i >= 0; ) { // 右から順にスキャン
rt[i] = mxrt;
mxrt = max(mxrt, str[i] – ‘0’);
}
int sum = 0;
for (int i = 0; i != WD – 1; ++i) {
int ht = min(lt[i], rt[i]); // 左右壁の低い方の高さまで水が貯まる
if( str[i] – ‘0’ < ht ) // その地点の高さが左右壁の低い方の高さ以上であれば、
sum += ht – (str[i] – ‘0’);
}
#else
// 流れ落ちる水を順次計算していく版：
string map = "-" + str + "-";
cout << map << "\n";
string ht(map.size(), ‘?’); // 水面高さ：’0’～’9’、不明：’?’ (0x3f)、マイナス無限大：’-‘ (0x2d)
ht.front() = ht.back() = ‘-‘;
deque<int> dq; // 水面を決めることができる場所のキュー
dq.push_back(1); // 左端
dq.push_back(map.size() – 2); // 右端
while( !dq.empty() ) {
cout << ht << "\n";
int ix = dq.front(); dq.pop_front(); // ix：水面高さを更新できる位置
int h = min(ht[ix-1], ht[ix+1]);
ht[ix] = max(map[ix], min(ht[ix-1], ht[ix+1])); // ix 位置の水面高さを設定
if( ht[ix-1] > ht[ix] && ht[ix-1] > map[ix-1] ) // 水があり、ix よりも水面が高い
dq.push_back(ix-1); // 左側の水面高さを更新可能
if( ht[ix+1] > ht[ix] && ht[ix + 1] > map[ix + 1]) // 水があり、ix よりも水面が高い
dq.push_back(ix+1); // 右側の水面高さを更新可能
}
cout << ht << "\n";
int sum = 0; // 面積合計
for(int i = 1; i != ht.size() – 1; ++i)
sum += ht[i] – map[i]; // 「水面高さ – 地面高さ」で水たまりの面積を求める
#endif
return sum;
}
[/java]

解説

ある地点に貯まることができる水面の高さは、低い方から水が流れていってしまうので、左右の最も高い壁の低い方で決まる。例えば、下図のように左側の壁の高さが3で右側が5であれば、min(3,5) = 3 までの高さが水面高となる。

さらにその地点の地面の高さが水面以下であれば、その差の分だけ水が貯まり、水面より高ければ水が貯まることはない（下図参照）。

問題は左右の壁の高さをどう求めるかだが、左から順にスキャンしていけば各地点の左側壁高さを求めることができるので、計算結果を vector<int> lt(WD) に保存する。
コードは回答例の通りで、最初に mxlt を0に設定し、左から順にスキャンしながら、各地点の左側壁高さを保存し、各地点との最大値で更新していく。
同様に右から順にスキャンし、各地点の右側壁高さを求め、結果を lt に保存する。
これで各地点の左右の壁の高さが、動的配列 lt, rt に設定できたので、あとは各地点を順にスキャンし、貯まる水の面積を求めそれの総和を求めるだけだ。
このアルゴリズムでは各地点のスキャンを3回行うだけなので、処理時間は O(N) となる。

回答例にて #if でコメントアウトしている部分は上記とは別のアルゴリズムを使った版だ。

水面の高さを決めることができる場所を、FIFO（First In First Out）のキュー dq に積んでおき、それを順次取り出し各位置の水面を決め、ht に格納していく。さらにそのとなりにその地点より水面が高い箇所があれば、そこをキューに積む。これをキューが空になるまで繰り返せば、全部の場所の水面高さが決まる、という寸法だ。なお、最初は左右端位置をキューに入れておく。