TopCoder(delta2323) / Codeforces(delta) / twitter
2011-05-05
■ [実践][SRM] SRM 505 Div1 300 RectangleArea 
前回のSRMのEasyがwriterさんのコードを見てようやく理解できたので，備忘録としてメモを残しておこうと思います．
300 RectangleArea
要約
N*Mの小長方形に分割された長方形があり，小長方形のうちいくつかは面積がわかっている．あといくつ小長方形の面積がわかれば全体の面積が求まるか．個数の最小値を求めよ．N, Mは1以上50以下．
方針
下図のように4つの小長方形がつくる長方形を，便宜的に中長方形呼ぶ事にします．
□□□□□□□□□□ □■□□□■□□□□ □□□□□□□□□□ □■□□□■□□□□ □□□□□□□□□□ （中長方形の例）
中長方形が退化して，4頂点がすべて同じ小長方形を指している場合も中長方形と考えます．
まずサンプルケースを見ると，中長方形を作る小長方形4つのうち，3つの面積が既知ならば残り一つの面積も計算できる事がわかります．そこでまず，初期状態から新たに情報を追加しなくても面積が求まる部分を出来る限り求めてみます．
#include <string> #include <vector> #include <sstream> #include <iostream> using namespace std; vector<string> k; bool check(int i, int ii, int j, int jj){ int cnt = 0; if(k[i][j] == 'Y') cnt++; if(k[ii][j] == 'Y') cnt++; if(k[i][jj] == 'Y') cnt++; if(k[ii][jj] == 'Y') cnt++; if(cnt == 3){ k[i][j] = k[ii][j] = k[i][jj] = k[ii][jj] = 'Y'; return true; }else{ return false; } } class RectangleArea { public: int minimumQueries(vector <string> known) { k = known; int n = known.size(); int m = known[0].size(); bool flag = true; while(flag){ flag = false; for(int i = 0;i<n;i++){ for(int ii = i;ii<n;ii++){ for(int j = 0;j<m;j++){ for(int jj = j;jj<m;jj++){ if(check(i, ii, j, jj)){ flag = true; } } } } } } // COMPLEMENT FINISHED } };
コメントの部分に達すると，長方形内のどの中長方形も「4頂点すべて面積既知」or「すべて面積未知」となります．例えば典型的には下図のような状況です．（■，●は面積既知，□は未知）．
□□□□■□□■□■ □●□●□●□□□□ □□□□■□□■□■ □●□●□●□□□□ □□□□■□□■□■ □□□□□□□□□□ （初期状態から面積がわかるものを全て補完した状態の例）
この場合，面積既知の小長方形を●のグループと■のグループとで分ける事が出来ます．なんとなくそれっぽい感じはするのですが，それをきちんと言葉で表すと，「どの●を取っても，その●から上下左右に小長方形を走査すると●しか見つからず，■は見つからない」という状態です．これは行と列を適当に入れ替えると分かりやすくなります．
■■■□□□□□□□ ■■■□□□□□□□ ■■■□□□□□□□ □□□●●●□□□□ □□□●●●□□□□ □□□□□□□□□□ （直前の図の行同士，列同士を適当に入れ替えた）
ここから適当に小長方形を一つ選べば●のグループと■のグループを「繋げる」ことが出来ます．例えば上から3行目（■のある行）と左から4列目（●のある列）の交点上にある小長方形を選ぶと，面積の分かる部分は下図のように増えます．
■■■■■□□□□□ ■■■■■□□□□□ ■■■■■□□□□□ ■■■■■□□□□□ ■■■■■□□□□□ □□□□□□□□□□ （一つ面積のわかる部分を付け加えてた結果，面積の分かる部分）
つまり，（グループの数）- 1個の小長方形を付け加えればこれらのグループはひとまとまりに出来ます．残りの白部分の面積を全て求めるには（白行の数）+（白列の数）個の小長方形の面積が分かれば十分です．
■■■■■■■■■■ ■■■■■□□□□□ ■■■■■□□□□□ ■■■■■□□□□□ ■■■■■□□□□□ ■□□□□□□□□□ （残りの小長方形の面積を知るためにいくつか■の長方形を追加）
残っている問題は次の2つです．
- 面積既知の小長方形をグループ分けした時のグループの数は？
- グループをひとつにまとめ上げた後に残っている白行，白列の数は？
グループ分け，ということでunion-findが使う方法を使います．ここでは小長方形ではなく行，列のグループ分けするとうまく行きます（グループ分けを行，列に対して行おうという発想が自分にはありませんでした．）．小長方形のグループを上下左右に延ばして「行と列の集合」に変換します．例えば
□□□□■□□■□■ □□□□□□□□□□ □□□□■□□■□■ □□□□□□□□□□ □□□□■□□■□■
なら
■■■■■■■■■■ □□□□■□□■□■ ■■■■■■■■■■ □□□□■□□■□■ ■■■■■■■■■■
に変換します（逆の操作も可能です）．
すると「「要」となる小長方形があるなら，小長方形が属する列と属する行は同じグループに属する」とルール化できます．
以上をまとめて，次のような下のようなコードが出来ました．
コード例
#include <string> #include <vector> #include <sstream> #include <iostream> #include <set> #include "../print.hpp" using namespace std; class UnionFind{ public: UnionFind(int _n):n(_n){ par.resize(n); for(int i = 0;i<n;i++){ par[i] = i; } rank.resize(n, 0); } int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return ; if(rank[x] < rank[y]){ par[x] = y; }else{ par[y] = x; } if(rank[x] == rank[y]) rank[x]++; } bool same(int x, int y){ return find(x) == find(y); } private: int n; vector<int> par; vector<int> rank; }; vector<string> k; bool check(int i, int ii, int j, int jj){ int cnt = 0; if(k[i][j] == 'Y') cnt++; if(k[ii][j] == 'Y') cnt++; if(k[i][jj] == 'Y') cnt++; if(k[ii][jj] == 'Y') cnt++; if(cnt == 3){ k[i][j] = k[ii][j] = k[i][jj] = k[ii][jj] = 'Y'; return true; }else{ return false; } } class RectangleArea { public: int minimumQueries(vector <string> known) { k = known; int n = known.size(); int m = known[0].size(); // In fact, this part is redundant. See also the remark below. bool flag = true; while(flag){ flag = false; for(int i = 0; i < n; i++){ for(int ii = i; ii < n; ii++){ for(int j = 0; j < m; j++){ for(int jj = 0; jj < m; jj++){ if(check(i, ii, j, jj)){ flag = true; } } } } } } /////////////////////////// UnionFind uf(n + m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(k[i][j] == 'Y'){ uf.unite(i, j + n); } } } int ans = 0; for(int i = 0; i < n + m; i++){ if(uf.find(i) == i){ ans ++ ; } } return ans - 1; } };
分析
実は，上の小長方形を補完する部分は余分です．例えば行と列をつなぐ要を
□□□□■□□■□■ □□□□□□□□□□ □□□□■□□■□■ □□□□□□□□□□ □□□□■□□■□■
からいくつか減らして
□□□□■□□■□□ □□□□□□□□□□ □□□□□□□□□■ □□□□□□□□□□ □□□□□□□■□■
としても，同じ行，列のグループを作ります．
■ [実践][Codeforces] Yandex Open 2011 Qualification 1 
問題一覧：Dashboard - Yandex.Algorithm Open 2011: Qualification 1 - Codeforces
結果：Standings - Yandex.Algorithm Open 2011: Qualification 1 - Codeforces
| = | . | A | B | C | D | E |
| - | - | - | 0:29 | - | - | - |
| 0 | +0/-0 | - | -1 | -2 | - | - |
部屋内10位(Room 68)，全体781位
Rating：1531 → 1452 (-79)
Yandexなるロシアのインターネット関連会社が主催するプログラミングコンテストが，Codeforcesをホストとして開催されています（ルールは通常のCodeforcesと同様です）．今回は2回あるQualificationラウンドの1回目で，上位500位までがRound1に進出します．ボーダーは1188点なので，A+Bを高速で解くか，A+Cを少ない誤答で解けばノルマを達成できたようです．
自分については，Codeforcesで0点は初めてかもしれないです．A, B問題について掲載します．C問題までは消化したいと思っています．
A. Plug-in
要約
1行の文字列に対し，同じ文字が隣同士にあったらそれら2つを削除するという操作を考える．文字列が与えられているので，この操作を行える限り行った結果を出力せよ（どのような順番で文字を消しても最終的な答えは同じである．）．つまり，それぞれの文字を「ぷよぷよ」のぷよだと思って，2個消しでできるだけぷよを消す操作を行え．
文字列の長さは1以上2*10^{5}以下．
方針
文字列を走査していき，ぷよで言うところの1連鎖分をシミュレートするような実装の場合，最悪文字列の長さの2乗のアルゴリズムとなってしまい時間内に終わらない．スタックを用いるとスマートに実装できる．今回の場合最後の出力はスタックの先頭から順に取り出すので，デックを用いると便利．
コード(c++)
#include <iostream> #include <vector> #include <string> #include <deque> using namespace std; int main(){ string s; while(cin >> s){ deque<char> ss; for(int i = 0;i<s.size();i++){ if(ss.empty()){ ss.push_back(s[i]); }else{ char t = ss.back(); if(t == s[i]){ ss.pop_back(); }else{ ss.push_back(s[i]); } } } while(!ss.empty()){ cout << ss.front(); ss.pop_front(); } cout << endl; } return 0; }
B. Sequence Formatting
要約
整数（123など複数桁もありうる，長さは任意），コンマ，スペース，三連ドットからなる一列の文字列がある，これをスペースの数を調節する事で，次の条件を満たすように整形せよ．
- コンマの後には1個のスペースがある（コンマが文字列の終端にある場合はスペースを入れない）
- 三連ドットの前には1個スペースがある（三連どっとが文字列の先頭にあるばあいはスペースを入れない）
- 整数と整数の間には1個のスペースがある
- これ以外にはスペースは入らない．
例えば
□□1,2□,3,...,□□□□□10□□11□□
は
1,□2□,3□,□...,□10□11
と整形される（□はスペース1個分を表す）
方針
はじめにスペースを出来る限り取り除き（正規化），その後必要な箇所にスペースを挿入するというアプローチをとる（最終的に残るスペースを一度消してしまうなど二度手間になる可能性がありますが，すっきりしてわかりやすいと思います）．
正規化では整数と整数それぞれの間にスペースを1つだけ残し，残りは全部取り除く，前述の例に当てはめれば
1,2,3,...,10□11
とする．これは，「文字列を走査していってスペースを見つけたら
（数字）□（数字）
となっていない限り取り除く」というアルゴリズムで行える．
つぎに，必要なスペースを挿入していく，整数と整数の間のスペースは既にあるので，コンマと三連ドットに付随するスペースを挿入していく．コンマ，三連ドット個別に考えれば良いだろうと思うし，実際それで問題ないのだが，コンマ，三連ドット両方からスペースを挿入され，スペースが連続してしまう可能性がある．例えば，
,...
の場合，「すべてのコンマの後にスペース」を適用した後「すべての三連ドットの前にスペース」を適用すると
,□□...
となる．そこで，三連ドットについては自分の前がスペースでないかを確認しなければならない．
コード(c++, コンテスト外)
#include <iostream> #include <vector> #include <string> #include <cctype> using namespace std; int main(){ string s; while(getline(cin, s)){ for(int i = s.size() -1;i>= 0;i--){ if(s[i] == ' '){ if( i -1 >= 0 && i + 1 < s.size() && isdigit(s[i-1] ) && isdigit(s[i+1])) continue; s.erase(i, 1); } } for(int i = s.size();i>=0;i--){ if(s[i] == ',' && i!= s.size()-1){ s.insert(s.begin () + i + 1,1, ' '); } } int cnt = 0; for(int i = s.size();i>=0;i--){ if(s[i] == '.'){ cnt ++; if(cnt % 3 == 0 && s[i-1] != ' ' && i != 0){ s.insert(s.begin () + i ,1, ' '); } } } cout << s <<endl; } return 0; }
分析
おそらく常套手段ですが，文字列の挿入，消去を行う場合，後ろから走査すると，処理済み，未処理を明確に区別でき便利です．例えば，「文字列の中にスペースがあったらそれを複製する」という操作duplicate_spaceを考えます．
abc□de□f
なら，
abc□□de□□f
です．これを次のように実装すると無限ループになります．
void duplicate_space(string & s) for(int i = 0;i<s.size();i++){ if(s[i] = ' '){ s.insert(s.begin() + i , 1, ' '); } }
これは新しく挿入したスペースの上も操作する事で，スペースが次々に挿入されてしまうためです．for文を逆順にすれば，スペースはiの操作済の範囲に挿入されるのでこの心配はありません．
void duplicate_space(string & s) for(int i = s.size() -1;i>=0;i--){ // The direction in which variable i runs is reversed. if(s[i] = ' '){ s.insert(s.begin() + i , 1, ' '); } }
補足
正規表現ライブラリが標準で付属している言語ならそれを用いるのが賢明だと思います．_dp_さんの提出解答は上の方針をPythonのreモジュールを用いて実装しています．
Status - Yandex.Algorithm Open 2011: Qualification 1 - Codeforces