Hatena::Grouptopcoder

shnyaの参戦記録

2011-01-26【勉強会】TopCoderの問題を解いてみる SRM 186 Div2

SRM 186 Div2 Medium WordWrap 18:40  [http://www.topcoder.com/stat?c=problem_statement&pm=2413&rd=4750:title=SRM 186 Div2 Medium WordWrap] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=2413&rd=4750:title=SRM 186 Div2 Medium WordWrap] - shnyaの参戦記録

問題概要

エディタなどでは適当なカラムで自動的にテキストを折り返す機能があります。

これを「justify」といういうのですが、入力として現在エディタに入力されているテキスト(1行ごとにベクトルとなっている)と折り返してほしいサイズが与えられますので、「justify」を実装してください。


入力例と出力例

0)	
    	
{"now is the time for all good men",
 "to come to the aid of their country"}
20
Returns: 
{ "now is the time for",
 "all good men to come",
 "to the aid of their",
 "country" }

1)	
    	
{"now",
 "is the time for",
 "all",
 "good",
 "men",
 "to",
 "come to the aid",
 "of",
 "their",
 "country"}
20
Returns: 
{ "now is the time for",
 "all good men to come",
 "to the aid of their",
 "country" }
Each line is made as long as possible without exceeding the column width.
2)	
    	
{"four score and seven years ago", 
 "our fathers brought forth",
 "upon this continent",
 "a new nation",
 "conceived in liberty", 
 "and dedicated to the proposition", 
 "that all men are created",
 "equal"}
50
Returns: 
{ "four score and seven years ago our fathers brought",
 "forth upon this continent a new nation conceived",
 "in liberty and dedicated to the proposition that",
 "all men are created equal" }
3)	
    	
{"th e ow l an d th e pu ss yc at",
 "we nt to se a",
 "on a be au ti fu l pe a gr ee n bo at"}
4
Returns: 
{ "th e",
 "ow l",
 "an d",
 "th e",
 "pu",
 "ss",
 "yc",
 "at",
 "we",
 "nt",
 "to",
 "se a",
 "on a",
 "be",
 "au",
 "ti",
 "fu l",
 "pe a",
 "gr",
 "ee n",
 "bo",
 "at" }

解き方

とりあえず入力となるベクトルを扱いやすいように連結する。

その後は、各単語ごとに処理、をしているんだけど境界条件のチェックとかでいろいろ間違えて時間を食ってしまった。あまりいいやり方じゃなかったかも。

 class WordWrap
 { 
 public: 
   vector <string> justify(vector <string> lines, int columnWidth) 
   { 
     string str;
     for(size_t i = 0; i < lines.size(); i++){
       str += lines[i];
       str += ' ';
     }
     string sub = str.substr(0, str.size() - 1);

     vector<string> result;
     while(1){
       size_t pos = 0;
       for(int i = 0; i <= columnWidth; i++){
         if(i >= sub.size()){
           pos = 100000;
           break;
         }
         if(sub[i] == ' '){
           pos = i;
         }
       }
       if(pos == 100000 || pos == 0) break;
       result.push_back(sub.substr(0, pos));
       sub = sub.substr(pos + 1);
     }
     result.push_back(sub);

     return result;
   } 
};