Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2010-10-27SRM 486 DIV2

3問全問submitしたが・・・

TxMsg

11:10 | TxMsg - capythm@TopCoder を含むブックマーク はてなブックマーク - TxMsg - capythm@TopCoder TxMsg - capythm@TopCoder のブックマークコメント

規則に従って与えられた文字列の省略形を生成せよ、という問題。

250点問題の割にかなり面倒な問題だった。

基本的に C++ での文字列処理の仕方がわかりません。誰か教えて(´・ω・`)

Ruby なら簡単にかけたと思う。

#include <string>
#include <vector>
#include <sstream>
using namespace std;
class TxMsg{
  vector<string> split( string s ){
    vector<string> ret;
    int idx = 0;
    for( int i=0; i < s.size(); i++ ){
      if( s[i] == ' ' ){
        ret.push_back( s.substr( idx, i-idx ) );
        idx = i+1;
      }
    }
    ret.push_back( s.substr( idx, s.size()-idx ) );
    return ret;
  }
  bool is_vowel( char c ){
      switch( c ){
      case 'a':
      case 'e':
      case 'i':
      case 'o':
      case 'u': return true;
      default: return false;
      }
  }
  bool is_vowel_only( string s ){
    for( int i=0; i<s.size(); i++ ){
      if( !is_vowel( s[i] ) ) return false;
    }
    return true;
  }
  string abbreviate( string s ){
    stringstream ss;
    bool state = true;
    for( int i=0; i<s.size(); i++ ){
      if( is_vowel( s[i] ) ){
        state = true;
      } else if( state ){
        ss << s[i];
        state = false;
      }
    }
    return ss.str();
  }
public:
  string getMessage(string original){
    vector<string> a;
    stringstream ss;
    a = split( original );
    for( int i=0; i<a.size(); i++ ){
      if( !is_vowel_only( a[i] ) ){
        a[i] = abbreviate( a[i] );
      }
    }
    for( int i=0; i<a.size(); i++ ){
      if( i > 0 ) ss << ' ';
      ss << a[i];
    }
    return ss.str();
  }
};

OneRegister

11:10 | OneRegister - capythm@TopCoder を含むブックマーク はてなブックマーク - OneRegister - capythm@TopCoder OneRegister - capythm@TopCoder のブックマークコメント

BFSで全探索すれば解けそう、ってことで書いたけど Challenging Phaseで破られた。

ソースさらすけど、以下の2点修正の必要あり。

  • オーバーフロー対策(乗算をlong long で計算するとか)
  • TLE対策(連想配列に探索済みの値をメモしておいて2重に探索しないようにする)

#include <string>
#include <deque>
using namespace std;
struct Data{
  string s;
  int d;
  Data( string ss, int dd ) : s(ss), d(dd) {}
};
class OneRegister{
public:
  string getProgram(int s, int t){
    deque<Data> q;
    if( s == t ){
      return "";
    } else {
      q.push_back( Data( "*", s*s ) );
      q.push_back( Data( "+", s+s ) );
      q.push_back( Data( "/", s/s ) );
    }
    while( !q.empty() ){
      Data d = q[0]; q.pop_front();
      if( d.d == t ) return d.s;
      else if( d.d < t ){
        if( d.d > 1 ){
          q.push_back( Data( d.s+"*", d.d*d.d ) );
        }
        q.push_back( Data( d.s+"+", d.d+d.d ) );
      }
    }
    return ":-(";
  }
};

CrazyLine

11:10 | CrazyLine - capythm@TopCoder を含むブックマーク はてなブックマーク - CrazyLine - capythm@TopCoder CrazyLine - capythm@TopCoder のブックマークコメント

サンプルの結果から法則性を見つけたので、そのように計算するプログラムを書いたが、

どうやらだめっぽかった。Failed System Test

レート

11:10 | レート - capythm@TopCoder を含むブックマーク はてなブックマーク - レート - capythm@TopCoder レート - capythm@TopCoder のブックマークコメント

結局250点問題+Challenging成功1回という結果。

1108→1106

LaviniaLavinia2011/08/30 19:25Stay inomfrtaive, San Diego, yeah boy!

drokjlsdrokjls2011/09/01 01:11Yiyo5V <a href="http://bruvxjoqhsqk.com/">bruvxjoqhsqk</a>

yfsmefnwyfsmefnw2011/09/02 21:25R2zlcR , [url=http://iqhbczvnuudn.com/]iqhbczvnuudn[/url], [link=http://xcdzrjnfpatg.com/]xcdzrjnfpatg[/link], http://msjprkqfxkud.com/

jcompsryjcompsry2011/09/03 19:16rjEC8w <a href="http://ujlfnjeyhsmc.com/">ujlfnjeyhsmc</a>

ywmfzdufywmfzduf2011/09/04 02:28rhKcNG , [url=http://dhbhcawaglkr.com/]dhbhcawaglkr[/url], [link=http://flghkklmovot.com/]flghkklmovot[/link], http://qhjauflxhwar.com/