Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2011-11-29SRM 525 Div2

1年ぶりに投稿します・・・

解説を書いておきます。

RainyRoad (250pt)

02:21 | RainyRoad (250pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - RainyRoad (250pt) - capythm@TopCoder RainyRoad (250pt) - capythm@TopCoder のブックマークコメント

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11635&rd=14550&rm=310668&cr=22881961

問題文の要約:

  • Fox Ciel さんは現在(0,0)の位置にいる
  • 彼女に会いに行きたい。彼女は(0,N-1)の位置にいる。
  • 道は 2xN マスになっている。
  • road[y][x] が道の情報になっている。水たまりは 'W'、それ以外は '.'
  • 上下左右に加えて、斜め方向にも進める。
  • 水たまりを歩かずに彼女の位置までたどり着けるか?

解法:

  • BFSやDFSを使う方法もあるが、煩雑です。
  • 水たまりでふさがって進めないのは road[0][x] も road[1][x] も水たまりの場合のみであることを利用すると簡単に解けます。
  • なお、x=0、x=N-1 はチェックしなくてもいい(road[0][0]、road[0][N-1] は水たまりではないことが問題中明記)
#include <vector> 
#include <string> 
using namespace std; 
class RainyRoad{ 
public: 
  string isReachable(vector <string> road){ 
    for( int i=1; i<road[0].size()-1; i++ ){ 
      if( road[0][i] == 'W' && road[1][i] == 'W' ) return "NO"; 
    } 
    return "YES"; 
  } 
};

DropCoins (600pt)

02:21 | DropCoins (600pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - DropCoins (600pt) - capythm@TopCoder DropCoins (600pt) - capythm@TopCoder のブックマークコメント

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11665&rd=14550&rm=310668&cr=22881961

問題文の要約:

  • 幅 W、高さ H の二次元平面がある。W×H マスある。
  • マスの上にはコインが載ってる場合がある。載ってたら board[y][x] は 'o'、そうでないなら '.'
  • W×Hマス全体を上下左右に動かすことができる。ただし、もともとの場所の W×H からはみ出た部分のコインは落ちてなくなってしまう。(文章じゃわかりにくいので、問題文の例題を見ることをおすすめします)
  • コインの枚数を K 枚にするための最小の移動回数は何回か?

解法(考え方):

  • 全探索する方針です。
  • W×Hの中で、いろいろな矩形に切り出してみて、ちょうどK枚になってるものを全て調べる。(ソースコード中「//count」の部分)
  • (x0,y0), (x1,y1) の範囲で切り出したときの移動回数はどう数えるか?(ソースコード中「//update」の部分)
    • 移動距離が短い方のコインを先に落としてから長い方のコインを落とすのが効率的。
    • x2 = W-x1, y2=H-y1 とすると、移動回数は x0+x2+min(x0,x2) + y0+y2+min(y0,y2) となる。
  • 最大30x30マスで計算量は n=30として O(n^4) 程度なので、間に合いそう。
#include <string> 
#include <vector> 
using namespace std; 
class DropCoins{ 
public: 
  int getMinimum(vector <string> board, int K){ 
    int ret = -1; 
    int height = board.size(); 
    int width = board[0].size(); 
    for( int y0=0; y0<height; y0++ ){ 
      for( int y1=y0; y1<height; y1++ ){ 
        for( int x0=0; x0<width; x0++ ){ 
          for( int x1=x0; x1<width; x1++ ){ 
            //count 
            int n=0; 
            for( int i=y0; i<=y1; i++ ){ 
              for( int j=x0; j<=x1; j++ ){ 
                if( board[i][j] == 'o' ) n++; 
              } 
            } 
            if( n != K ) continue; 
            //update 
            n=0; 
            int i0=x0, i1=(width-1)-x1; 
            if( i0 < i1 ) n += i0*2 + i1; 
            else n += i0 + i1*2; 
            i0=y0; i1=(height-1)-y1; 
            if( i0 < i1 ) n += i0*2 + i1; 
            else n += i0 + i1*2; 

            if( ret < 0 || ret > n ) ret = n; 
          } 
        } 
      } 
    } 
    return ret; 
  } 
};

MagicalSquare (900pt)

02:21 | MagicalSquare (900pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - MagicalSquare (900pt) - capythm@TopCoder MagicalSquare (900pt) - capythm@TopCoder のブックマークコメント

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11594&rd=14550&rm=310668&cr=22881961

問題文の要約:

  • 3×3マスのそれぞれに文字列を入れたい。それぞれのマスの文字列を S[i][j] とする。
  • 横方向につなげた文字列・縦方向につなげた文字列がそれぞれ rowStrings[i], columnStrings[j] となるようにしたい(問題文参照)
  • 上記のようになる組み合わせは何パターンあるか?

解法(考え方):

  • 全探索する方針です。
  • rowString[i] (i=0,i=1) を 3分割して S[i][j] (j=0,1,2)に割り当ててみる。
  • S[0][j]+S[1][j] は columnStrings[j] の先頭部分と一致しなければならない。
  • j=0,1,2 全て一致した場合、columnStrings[j] のそれぞれの余った部分をつなぎ合わせると rowStrings[2] に一致しなければならない。
  • 文字列長は最大n=50。3分割の組み合わせはおよそO(n^2)。3分割するのはi=0,1 の2つなので、計算量は O(n^4)で、n=50ならぎりぎり間に合うはず。

上記の考え方の元、以下のように実装したが、全ての入力文字列が"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (aが50個)の場合、処理時間が 2秒を超えてしまい TLEになってしまった。

#include <vector> 
#include <string> 
using namespace std; 
class MagicalSquare{ 
public: 
  long long getCount(vector <string> rowStrings, vector <string> columnStrings){ 
    long long ret=0; 
    for( int i0=0; i0<=rowStrings[0].size(); i0++ ){ 
      for( int i1=i0; i1<=rowStrings[0].size(); i1++ ){ 
        for( int j0=0; j0<=rowStrings[1].size(); j0++ ){ 
          for( int j1=j0; j1<=rowStrings[1].size(); j1++ ){ 
            string s = ""; 
            // check 
            if( rowStrings[0].substr( 0, i0 ) + rowStrings[1].substr( 0, j0 ) != columnStrings[0].substr( 0, i0+j0 ) ) continue; 
            s += columnStrings[0].substr( i0+j0 ); 
            if( rowStrings[0].substr( i0, i1-i0 ) + rowStrings[1].substr( j0, j1-j0 ) != columnStrings[1].substr( 0, i1+j1-(i0+j0) ) ) continue; 
            s += columnStrings[1].substr( i1+j1-(i0+j0) ); 
            if( rowStrings[0].substr( i1 ) + rowStrings[1].substr( j1 ) != columnStrings[2].substr( 0, rowStrings[0].size()+rowStrings[1].size()-(i1+j1) ) ) continue; 
            s += columnStrings[2].substr( rowStrings[0].size()+rowStrings[1].size()-(i1+j1) ); 
            if( s != rowStrings[2] ) continue; 
            ret++; 
          } 
        } 
      } 
    } 
    return ret; 
  } 
};

終わったあとに確認すると、stringオブジェクトの生成等にかなりの時間がかかっていたようだ。substr と '+' 演算子を使わずに compare メソッドを使ったところ、上記のパターンでも約1.4秒程度で実行完了した。考え方は全く同じでも、実装方法により計算時間が異なってしまうと言う落とし穴があった。以下がTLE対策後のソースコードである。

#include <vector>
#include <string>
using namespace std;
class MagicalSquare{
public:
  long long getCount(vector <string> rowStrings, vector <string> columnStrings){
    long long ret=0;
    string s;
    for( int i0=0; i0<=rowStrings[0].size(); i0++ ){
      for( int i1=i0; i1<=rowStrings[0].size(); i1++ ){
        for( int j0=0; j0<=rowStrings[1].size(); j0++ ){
          for( int j1=j0; j1<=rowStrings[1].size(); j1++ ){
            s.clear();
            // check
            if( rowStrings[0].compare( 0, i0, columnStrings[0], 0, i0 ) != 0 ) continue;
            if( rowStrings[1].compare( 0, j0, columnStrings[0], i0, j0 ) != 0 ) continue;
            s += columnStrings[0].substr( i0+j0 );
            if( rowStrings[0].compare( i0, i1-i0, columnStrings[1], 0, i1-i0 ) != 0 ) continue;
            if( rowStrings[1].compare( j0, j1-j0, columnStrings[1], i1-i0, j1-j0 ) != 0 ) continue;
            s += columnStrings[1].substr( i1+j1-(i0+j0) );
            if( rowStrings[0].compare( i1, rowStrings[0].size()-i1, columnStrings[2], 0, rowStrings[0].size()-i1 ) != 0 ) continue;
            if( rowStrings[1].compare( j1, rowStrings[1].size()-j1, columnStrings[2], rowStrings[0].size()-i1, rowStrings[1].size()-j1 ) != 0 ) continue;
            s += columnStrings[2].substr( rowStrings[0].size()+rowStrings[1].size()-(i1+j1) );
            if( s != rowStrings[2] ) continue;
            ret++;
          }
        }
      }
    }
    return ret;
  }
};