Hatena::Grouptopcoder

Div2から抜けだしたいsuztomoの日記

Archive/suztomo

2008-12-09

SRM322 div2のつづき BattleshipChecker

01:01

1000点問題.ifififif.見落しやらこんがらがるやらで1時間かけてしまった.

Archive/suztomo/SRM322

10x10の盤面におかれたBattleshipが条件に合った並びかたをしているかどうかをチェックする.

class BattleshipChecker {
public:
  string checkBoard(vector <string> b) {
    int ret = 0;
    int ci, cj;
    int shipnumi[4] = {0, 0, 0, 0};
    int shipnumj[4] = {0, 0, 0, 0};
    int boxc = 0;
    REP(i, b.sz) {
      ci = 0;
      cj = 0;
      bool noboxi = true;
      bool noboxj = true;
      REP(j, b.sz) {
        if (j < b.sz-1 && i < b.sz-1) {
          if (b[i][j] == 'X' && b[i+1][j+1] == 'X') {
            return "REJECTED";
          }
        }
        if (j > 0 && i < b.sz-1) {
          if (b[i][j] == 'X' && b[i+1][j-1] == 'X') {
            return "REJECTED";
          }
        }
        if (b[i][j] == 'X') {
          cj += 1;
          if (cj > 4) return "REJECTED";
          boxc += 1;
          noboxj = false;
        } else if (cj > 1){
          shipnumj[cj-1] += 1;
          cj = 0;
        } else {
          cj = 0;
        }

        if (b[j][i] == 'X') {
          ci += 1;
          if (ci > 4) return "REJECTED";
          noboxi = false;
        } else if (ci > 1) {
          shipnumi[ci-1] += 1;
          ci = 0;
        } else {
          ci = 0;
        }
      }
      if (cj > 1)
        shipnumj[cj-1] += 1;
      if (ci > 1)
        shipnumi[ci-1] += 1;

      if (noboxi)
        ret++;
      if (noboxj)
        ret++;
    }
    REP(i, 4) {
      if (i>0)
        boxc -= (shipnumi[i] + shipnumj[i])*(i+1);
    }
    shipnumi[0] = boxc;
    int shipnum[] = {4, 3, 2, 1};
    REP(i, 4) {
      if (shipnumi[i] + shipnumj[i] != shipnum[i]) {
        return "REJECTED";
      }
    }

    ostringstream oo;
    oo << "ACCEPTED, " << ret << " POINTS";

    return oo.str();
  }
};

盤面上を走査するのはifがいっぱいあってどれか見落してしまうので苦手です.

Problemset and analysisを見ると斜めに接しているマスをRejectする方法はこう.

for(int i=0;i<9;i++)for(int j=0;j<9;j++)
   if ((board[i][j]=='X' && board[i+1][j+1]=='X') ||
       (board[i+1][j]=='X' && board[i][j+1]=='X')) return "REJECTED";

言われればそうなのだけれども,いざ自分でやろうとすると上のように汚くやってしまう.

難しいアルゴリズムではないのだけれど,見落してしまう罠がある問題が嫌だ.問題を解いても新しいアルゴリズムを覚えたわけじゃないから次に繋ぎにくいです.こういう問題を何というジャンルに分類するのでしょう.


解答へのリンク

13:52

http://www.topcoder.com/stat?c=problem_solution&rm=299577&rd=13519&pm=10182&cr=22712423

rmがルームID,crがメンバID,rdがラウンド,pmが解答ID

かな.

[SRM:428:suztomo:easy]

もしくは

http://srm.example.com/428/suztomo/easy

で上のリンクが出たら嬉しいな.

2008-12-08

push_backはどれだけできる?

05:43

さっきのGroupWork::bestGroupでpush_backのやりすぎで落ちたやつをみつけた.10^9のループで時間で落ちたのかと思いきや,どうやら下のコードをArenaを通して実行するとメモリアロケーションで落ちているようだ.

class GroupWork {
public:
  public:
    long long bestGroup ( vector<int> p, vector<int> s ){
      p.clear();
      REP(i, 10000000)
        p.push_back(1);
      p = s;
      return (long long)p.size();
    } 

10^6にしたら上のエラーは出なかったので,目安としては10^7以上push_backするようなコードがあったら撃墜できると覚えておくことにする.

手元とArenaの実行時間

05:43

計ってみた.最適化の具合にも依存すると思うけれど,一応目安になるように.

class GroupWork {
public:
  public:
    long long bestGroup ( vector<int> p, vector<int> s ){
      int sum = 0;
      p.clear();
      REP(i, 1000000000)
        sum += 1;
      p = s;
      return (long long)p.size();
    } 

g++ -Wall -O2 -ggdb GroupWork.cpp -lm -o GroupWork

でコンパイルして実行したら手元で540msecぐらい.Arenaで470msecぐらいなのでだいたい同じぐらいだとわかった.ちなみに-O2をつけなかったら3850msecぐらいで,これではArenaとの差がずいぶんになってしまう.

というわけで-O2がつくようにsmart-compile.elのsmart-compile-alistを変更した.*1これでArenaと手元の環境がだいたい同じぐらいの速度で動くと覚えておく.

過去問SRM322

04:48

眠れないなら,過去問を解けばいいじゃない.

Archive/suztomo/SRM322

250 DerivativeSequence

問題文をすぐ読めたのはよかったが,答えが合わない.ループがありえない回数まわった.

原因はdefineマクロが間違っていたという罠でした.バグが出たのが本番でなくてよかった.

#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))

class DerivativeSequence {
public:
  vector <int> derSeq(vector <int> a, int n) {
    vector <int> ret = a;
    vector <int> tmp;

    REP(i, n) {
      tmp.clear();
      REP(j, ret.sz-1) {
        int t = ret[j+1] - ret[j];
        tmp.push_back(t);
      }
      ret = tmp;
    }
    return ret;
  }
};

すぐ書けるべきなのにコーディングに15分かかってしまった.

原因のマクロ

#define REP(a, b) for (size_t (a) = 0; (i)<(size_t)(b); ++(a))

正しくは

#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))

コンパイル通るんだもんなぁ.


500 GroupWork

値の大きい人に合わせてGreedyに見ていけばいいと思ったらSystem Testで落ちた.例えば「10, 4, 3*2, 2*3」のときに最初10を選んで他を選ばないという方法をとっていた.2*7=14のほうがProductivityが高いのに.

結局,ProductivityのためのKがとりうる値がたかだか50通りしかないのでそれを利用すればokだった.

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define Fill(a, b) memset((a), (b), sizeof(a))
#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))
#define sz size()
#define Tr(c, i) for(typeof((c).begin()) i= (c).begin(); (i) != (c).end(); ++(i))
#define All(c) (c).begin(), (c).end()
#define Present(c, x) ((c).find(x) != (c).end()) // for Map or Set
#define CPresent(c, x) (find(All(c), x) != end()) // for vector

class GroupWork {
public:
  long long bestGroup(vector <int> p, vector <int> s) {
    vector <ii> k;
    REP(i, p.sz) {
      ii t(s[i], p[i]);
      k.push_back(t);
    }
    sort(All(k));
    long long ret = 0LL;
    REP(i, k.sz) {
      ii t = k[i];
      long long num = 0LL;
      int tpow = t.first;
      REP(j, k.sz) {
        ii tt = k[j];
        int ttpow = tt.first;
        if (ttpow >= tpow) {
          num += tt.second;
        }
      }
      if (num*tpow > ret) {
        ret = num*tpow;
      }
    }
    return ret;
  }
};

vector<ii>を覚えた.これで要素(ある集合の要素数とその集合の評価値)などを関連づけてソートができる.

ナカーマ!

*1:-O3のほうがちょっとだけ遅かったりした

2008-12-07

記録用キーワード

つくったけど...みづらい.

Archive/suztomo - TopCoder部

SRM336 div2 250 VowelLatin

せっかくイテレータについて書いたので過去問で使ってみた.

class VowelLatin {
public:
  string translate(string word) {
    string ret;
    string app;
    Tr(word, c) {
/*      if (
          *c == 'a' || *c == 'i' || *c == 'u' || *c == 'e' || *c == 'o' ||
          *c == 'A' || *c == 'I' || *c == 'U' || *c == 'E' || *c == 'O'
          ) {*/
      if (strchr("aiueoAIUEO", *c) {
        app += *c;
      } else {
        ret += *c;
      }
    }
    return ret+app;
  }
};

これは問題を読み始めてから5分でできた.ifはきれいに書けないものか.

ebdさんの解答を見るとtolower()を使うことでちょっと楽になりそう.

追記.

strchrをtsukunoさんにコメント欄で教えてもらいました.ありがとうございます.

関数名strchrから引数はstrが先で,charが後と覚えることにします.

Tutorial : Power up C++ with the Standard Template Library #1

22:13

Power up C++ with the Standard Template Library #1を店内にカポーがいっぱいいるハンバーガ屋で,むしゃむしゃハンバーガを食べながら読んだ.

基本的なSTLのコンテナ/イテレータの使い形が書いてある.

イテレータ

苦手.

今回のTutorialによるとIteratorには2種類,normal iteratorsとrandom access iteratorsがあってコンテナによって違う.normal iteratorは"=="や"!="の比較はできるけど,それらの減算はどはできない.

end()が返すイテレータは前々から変なものだと思っていたのだけれど,このTutorialでは

The end iterator is pointing not to the last object, however, but to the first invalid object, or the object directly following the last one.

という説明があってちょっと納得した.

イテレータを使ってtraverseに便利なマクロtr

void f(const vector<int>& v) { 
     int r = 0; 
     // Traverse the vector using const_iterator 
     for(vector<int>::const_iterator it = v.begin(); it != v.end(); it++) { 
          r += (*it)*(*it); 
     } 
     return r; 
}

ここで"vector<int>::const_iterator"などをコンテナごとに替えるのは面倒なので,

#define tr(container, it) \ 
      for(typeof(container.begin()) it = container.begin(); it != container.end(); it++) 

void f(const vector<int>& v) { 
     int r = 0; 
     tr(v, it) { 
          r += (*it)*(*it); 
     } 
     return r; 
}

とできる.

find

MapやSetには普通のfindではなく,MapやSetが持っているfindを使いましょう.O(log n)で探してくれます.

MapやSetに一度入れたデータを変更するのには注意しましょう.

next_permutation

sortしてdo/whileしましょう.

sort(all(v));
do {
    // hogehoge
} while(next_permutation(all(v));

Challengeのコツ

19:14

キーワードChallengeのコツを作りました.脊髄反射でChallengeができる人の書き込みをおまちしています.

SRM428の復習 TheDictionary

18:51

SRM428 - Div2から抜けだしたいsuztomoの日記 - TopCoder部の復習です.


思考

  • 木を伝っていけばよさそう.Combinationの数でどっちの枝に進むかを決める
  • このための関数をsearch関数とする.

木を伝う

返り値は木のノードの評価値(この場合はstring).木の根の評価値がfindメソッドの返り値となるようにするとすっきりしそう.

引数は木のノードのパラメータ.前から何番目の文字列がほしいか,使えるaの数,使えるzの数の3つ.

コード1

ざーっと,書いたらシステムテスト通らず.最大の条件100, 100, 1000000000だったのでどこかでオーバーフローしている可能性が高そうだ.

!

コンビネーションをこんなふうに書いていた.

  int c(int a, int b) {
    // requires a >= b
    int ret = 1;
    REP(i, b)
      ret *= a-i;
    REP(i, b)
      ret /= i+1;
    return ret;
  }

これではc(100, 100)が渡されたときに100*99*98*..*3*2*1を計算してしまう.あたり前だがintの範囲には入らない.

ここでNarashyさんの解答を見たらなんかマトリックスを埋めてから探索を実行している.しかもintじゃなくてlong long.

intしか使わずにもしtmpの掛け算の途中で1000000000を越えたら10000000000よりすこし大きな値を返すことにする,というのも考えたが,100!の途中では一気に2桁以上増える可能性もあるので,long longを使わないといけないんだろう.

ということで真似てみたら正解.

class TheDictionary {
public:
  long long d[101][101];
  int c(int a, int b) {
    return (int)d[a-b][b];
    // requires a >= b
    int ret = 1;
    REP(i, b)
      ret *= a-i;
    REP(i, b)
      ret /= i+1;
    return ret;
  }
  string search(int a, int z, int n) {
    string ret;
    if (a == 0 || z == 0) {
      REP(i, z)
        ret.append("z");
      REP(i, a)
        ret.append("a");
      if (n == 1) return ret;
      return "";
    }
    int front = c(a-1+z, z);
    if (front >= n)
      return "a" + search(a-1, z, n);
    return "z" + search(a, z-1, n-front);

  }
  string find(int n, int m, int k) {
    REP(i, 101) d[i][0] = 1;
    REP(i, 101) d[0][i] = 1;
    for (int i=1; i<101; i++)
      for (int j=1; j<101; j++) {
        long long t = d[i-1][j] + d[i][j-1];
        if (t > 1000000000) t = 1000000000;
        d[i][j] = t;
      }

    string ret;
    ret = search(n, m, k);
    if (ret.sz < (size_t)n+m) return "";
    return ret;
  }
};

途中のミス

  • search関数で"a"や"z"をつけるのを忘れていた: return search(..としていた
  • c(100, 100)を計算するのに必要なマトリックスのサイズはd[101][101].c(100, 0)からc(100, 100)まであるので.

system testを通すまで1時間でした.問題は本番のときに読んでいたのにこれだけかかってしまう...

2回目は5分でした.

メモ

intとlongとlong long.

intじゃ足りないからってまちがえてlongとか使ってしまいそう.

2^31が10桁,そのだいたい2乗の2^63はだいたい20桁.対数.

tsukunotsukuno2008/12/08 09:17> ifはきれいに書けないものか.

これですが、TopCoderだと"AIUEOaiueo"みたいな文字列を持っておいて、そいつにstrchr使うってコードを良く見かけます。(僕はJavaなのでindexOfですが。

suztomosuztomo2008/12/09 01:12strchr,ありがとうございます.

2008-12-06

Tutorial : Planning an Approach to a TopCoder Problem #1

21:59

ちょくちょくチュートリアルを読んでいます.印刷してしまえばコンピュータよりももちはこびやすいです.

今日読んだのはPlanning an Approach to a TopCoder Problem #1.

要約すると,

パターンにはまっちゃだめ

問題のパターンを覚えるのは確かに役に立つけど,パターンにあてはまらない問題もあるよ

"Kata"に従って過去問を解くといい

  • 過去問で練習するときに"Kata"をつくるといい.問題は3回解いて,それぞれ時間を計るべし.
    • 1回目は何も読まずに解く.解放をノートに書く.
    • 2回目も解く.
    • 3回目に解いたものが,問題を読んですぐに解法がわかったときに必要な時間.

過去問について解答を書きだすのはもちろん,自分なりに分析を書くのがよい.

問題を分割し,デバッグも考えろ

問題はいくつかのフェイズに分割できる.

もしテストケースが動かなかった場合にどこをデバッグすればいいかを考えながらコードを書くべし.

ライブラリに頼りすぎるな

既にあるライブラリ(その中身を知らないやつ)に頼りすぎると,そのアルゴリズムのちょっとの変更ができなくて困るときがあるので,自作ライブラリを使うといいよ.

2008-12-04

TZTester編集する流れ

17:43

に乗れない.

naoya_tさんのやつをダウンロードしてコンパイル.

suztomo@SuzAir.local ~/srm/TZTester
~/srm/TZTester $ javac -classpath ContestApplet.jar -deprecation TZTester.java
TZTester.java:88: warning: [deprecation] toPlainText(com.topcoder.shared.language.Language) in com.topcoder.shared.problem.Renderer has been deprecated
        try { m_Tags.put(k_PROBLEM, Render.toPlainText(m_Language)); } catch (Exception Ex) { }
                                          ^
1 warning
suztomo@SuzAir.local ~/srm/TZTester
~/srm/TZTester $ javac -version
javac 1.5.0_16

warningこわいなー.1.4じゃないとだめかなと思いつつも

ARENAを開いて設定を開いてみたらエラー.

んー? [あとでやる]

追記

ソースからじゃなくてjarファイルを落としてそれを使ったらいけた.あるえー

(FileEditのテンプレートを見るとnaoya_tさんがjava...? いや,しかしtemplateとか言ってるからC++か)

追記2

↓のコメントにてnaoya_tさんが教えてくれました.ありがとうございます.

クラスパスはディレクトリの階層に対応してないとだめでしたね.

n4_tn4_t2008/12/05 00:381) そのwarningは無視してよい
2) jarにするときにtangentz/TZTester.classみたいにtangentzの下にないと駄目
なので置いてあるjarを使ってもらえば良いです。テンプレート例はC++です。

suztomosuztomo2008/12/05 23:42完璧に忘れてました!>tangentz/TZTester.classみたいにtangentzの下にないと駄目
そういえばActionScriptもそんなんだったな.