Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2013-02-27SRM 571 Div I

FoxAndMp3

17:28 |  FoxAndMp3 - agwの日記 を含むブックマーク はてなブックマーク -  FoxAndMp3 - agwの日記  FoxAndMp3 - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491

21分。

  • 1からnまでに収まる、1、10、100、...からの50個ずつの数値を文字列として用意。整列して先頭の50個の要素を得る戦略とした

以下は提出した実装(システムテストをパス)。

class FoxAndMp3 {
public:
  std::vector<std::string> playList(int n) {
    std::set<int> set;

    for (int i = 1; i <= n; i *= 10)
      for (int j = 0; j < 50; j ++)
        if (i + j <= n)
          set.insert(i + j);

    std::vector<std::string> filenames;

    EACH (it, set)
      filenames.push_back(filename(*it));

    std::sort(ALL(filenames));

    if (filenames.size() > 50)
      filenames.resize(50);

    return filenames;
  };

private:
  std::string filename(int i) const {
    std::ostringstream os;
    // XXX
    os << i << ".mp3";

    return os.str();
  };
};
  • std::ostringstreamを後で確認しようと思いコメントを入れていたが、記入していたことすら忘れていて恥ずかしい
  • 制約から、nの取りうる範囲は[1, 109]であった

f:id:agw:20130226221434p:image

  • intで宣言していたiがオーバーフローするであろうことに提出後気付いたが、109 × 10は1,410,065,408となり、命拾いした
  • SRM直後のTLやコードリーディングで目から鱗の発想を幾つか見つけた

  • すごい。無駄なくまとめている

これを参考にした実装は以下(システムテスト済)。

class FoxAndMp3 {
public:
  std::vector<std::string> playList(int n) {
    std::vector<std::string> filenames;

    for (int i = 1; i < 100; i ++)
      if (i <= n)
        filenames.push_back(filename(i));

    for (long long i = 100; i <= n; i *= 10)
      for (int j = 0; j < 50; j ++)
        if (i + j <= n)
          filenames.push_back(filename(i + j));

    std::sort(ALL(filenames));

    if (filenames.size() > 50)
      filenames.resize(50);

    return filenames;
  };

private:
  std::string filename(int i) const {
    std::ostringstream os;

    os << i << ".mp3";

    return os.str();
  };
};
  • コードリーディングでは内側の反復の範囲を工夫した実装を見つけた
  • iから始まる数値を50個、ただし10iまでのものを追加するものであった

f:id:agw:20130226221435p:image

これを参考にした実装は以下(システムテスト済)。

class FoxAndMp3 {
public:
  std::vector<std::string> playList(int n) {
    std::vector<std::string> filenames;

    for (long long i = 1; i <= n; i *= 10)
      for (int j = i; j < std::min(i + 50, i * 10); j ++)
        if (j <= n)
          filenames.push_back(filename(j));

    std::sort(ALL(filenames));

    if (filenames.size() > 50)
      filenames.resize(50);

    return filenames;
  };

private:
  std::string filename(int i) const {
    std::ostringstream os;

    os << i << ".mp3";

    return os.str();
  };
};
  • すっきりしている。この実装が一番好きだ
  • これ以外にも深さ優先探索を使った実装や、ジェネレータを使った実装があったようだ
  • std::vector::resize()を初めて使った。嬉しい
 |