Hatena::Grouptopcoder

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

Archive/suztomo

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,ありがとうございます.