IOI2008 1問目 (TYPE PRINTER) [C++]

| コメント(0) | トラックバック(0)

第20回国際情報オリンピック の第1問(TYPE PRINTER) を、 制限とか関係なく 解いてみた。

#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <algorithm>

namespace {
std::vector<char> operation;
std::string lastword;

void type(const std::string& s)
{
  std::string::const_iterator it,b1,b2,e1;
  if ( lastword.size() > s.size() ) {
    b1 = lastword.begin();
    e1 = lastword.end();
    b2 = s.begin();
  }
  else {
    b1 = s.begin();
    e1 = s.end();
    b2 = lastword.begin();
  }
  it = std::mismatch(b1,e1,b2).first;
  std::size_t matchlen = std::distance(b1,it);
  if ( matchlen < lastword.size() ) {
    for ( int i = 0; i < lastword.size()-matchlen; ++i ) {
      operation.push_back('-');
    }
  }
  it = s.begin();
  std::advance(it,matchlen);
  std::copy(it,s.end(), std::back_inserter(operation));
  operation.push_back('P');
  lastword = s;
}
}
int main()
{
  int n;
  std::cin >> n;
  std::vector<std::string> v;
  std::copy(std::istream_iterator<std::string>(std::cin),
      std::istream_iterator<std::string>(),
      std::back_inserter(v));
  std::sort(v.begin(),v.end());
  std::for_each(v.begin(),v.end(),type);
  std::vector<char> shortest_operation;
  shortest_operation.swap(operation);
  while ( std::next_permutation(v.begin(), v.end()) ) {
    operation.clear();
    lastword="";
    std::for_each(v.begin(),v.end(),type);
    if ( operation.size() < shortest_operation.size() )
      shortest_operation.swap(operation);
  }

  operation.swap(shortest_operation);
  std::cout << operation.size() << "\n";
  std::copy(operation.begin(), operation.end(), std::ostream_iterator<char>(std::cout, "\n"));
  return 0;
}

一応答えは正しく出るっぽいけど、 std::next_permutation とか使ってるからきっと単語数増えたらめちゃくちゃ遅い。

ちなみに制限は 単語数 1 <= N <= 25000 (但し、採点時にはNは18を超えない?)、実行時間1秒以内、使用メモリ64KiB以内 だそうです。

公式資料にはご丁寧にC++のI/O streamはボトルネックになるからprintf/scanfの使用を強く推奨します(意訳)って書いてある。うーむ

トラックバック(0)

トラックバックURL: http://floralcompany.jp/mt/mt-tb.cgi/119

コメントする

AUTHOR

  • turugina (虎王 剱奈)
  • E-mail: turugina {at} floralcompany.jp
  • pixiv
  • ニジエ

2014年5月

        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 5.2.10

- 警 告 -

本サイトにはいわゆる「18禁画像」(イラスト)へのリンクが存在します。 未成年の方や、その手の画像に不快感を覚える方は、 該当記事(「えちぃの」及び「ちょっとえちぃの」カテゴリ) をご覧にならないようお願いいたします。

上記を理解した上で非表示のブログパーツを表示する
あわせて読みたいブログパーツ
ついった
drawr/pixiv/twitpic