Google Code Jam 2005 Qualification I 250

練習問題はもう一セットありますが、スキップして本番の Qualification Round I の 250 点問題を紹介していきます。250 点問題は、 全部で 5 種類あって他の人となるべく問題が重ならないようになっていますが、とても簡単です。

まずは、Crops という問題を紹介します。

引数 image には、次のような値が与えられます。

{".........",

 "X.XXXXXXX",

 "....X....",

 "........." }

引数 crops には、次のような値が与えられます。

{"1 0 2 8", "0 0 1 1"}

引数 image は、イメージをあらわしていて “.” と “X” の文字自体には特に意味がありません。引数 image には、順番に座標が与えられて最初の “1 0 2 8″ は (1,0) と (2, という意味で四角形をあらわしています。問題の内容は、引数 image のイメージに対して引数 crop の四角形を順番に切り取って最終的に残った引数 image のイメージを返しなさいというものです。

上の例では、引数 image のイメージを (1, 0) (2, の範囲で切り取ったものから、(0, 0) (1, 1) の範囲の四角形を切り取りますので、次のような値になります。

{"X.", ".." }

というわけで、回答コードは次のようになりました。

#include 

#include 

#include 

using namespace std;

class Crop {

private:

  vector sub_crop(vector s, int r1, int r2, int c1, int c2) {

    vector ret;

    for (int x = r1; x < = r2; x++) {

      string t;

      for (int y = c1; y <= c2; y++) {

        t += s[x][y];

      }

      ret.push_back(t);

    }

    return ret;

  }

public:

  vector crop(vector image, vector crops) {

    for (int i = 0; i < crops.size(); i++) {

      int r1, c1, r2, c2;

      sscanf(crops[i].c_str(), "%d %d %d %d", &r1, &c1, &r2, &c2);

      image = sub_crop(image, r1, r2, c1, c2);

    }

    return image;

  }

};

この問題は、本番ではあたりませんでしたが、回答コードができるまで約 20 分ほどかかりました。これではまったく通用しないレベルです。

イメージを切り取る部分を関数化してあることによりコードの量がすこし減っています。