Hatena::Grouptopcoder

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

2012-07-24

Codeforces Round #130 (Div.2)

11:25 | Codeforces Round #130 (Div.2) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces Round #130 (Div.2) - capythm@TopCoder Codeforces Round #130 (Div.2) - capythm@TopCoder のブックマークコメント

参戦しました。今回は解説なしでメモだけ・・・

ちなみに、3ACで97位でした。

A. Dubstep

解法:やるだけ

#include <iostream>
#include <string>
using namespace std;
int main( void )
{
  string s;
  cin >> s;
  unsigned int loc;
  while( (loc = s.find( "WUB", 0 )) != string::npos ){
    s.replace( loc, 3, " " );
  }
  while( s[s.size()-1] == ' ' ){
    s.replace( s.size()-1, 1, "" );
  }
  int idx=0;
  while( s[idx] == ' ' ) idx++;
  char prev = '*';
  while( idx < s.size() ){
    if( prev == ' ' && s[idx] == ' ' ){ idx++; continue; }
    cout << s[idx];
    prev = s[idx];
    idx++;
  }
  cout << endl;
}

B. Solitaire

解法:メモ化再帰

#include <iostream>
#include <string>
#include <set>
using namespace std;

set<string> h;

int dfs( string s ){
  int N = s.size();
  if( N == 2 ) return 1;
  if( h.find( s ) != h.end() ) return 0;
  string t1( s.begin(), s.end()-2 );
  string t2( t1 );
  if( s[N-1] == s[N-3] || s[N-2] == s[N-4] ){
    t1[N-3] = s[N-1];
    t1[N-4] = s[N-2];
    int ret = dfs( t1 );
    if( ret ) return 1;
  }
  if( N > 6 && ( s[N-1] == s[N-7] || s[N-2] == s[N-8] ) ){
    t2[N-7] = s[N-1];
    t2[N-8] = s[N-2];
    int ret = dfs( t2 );
    if( ret ) return 1;
  }
  h.insert( s );
  return 0;
}

int main( void )
{
  int n;
  string c,s;
  cin >> n;
  for( int i=0; i<n; i++ ) { cin >> c; s += c; }
  if( dfs( s ) ) cout << "YES" << endl;
  else cout << "NO" << endl;
}

D. Prizes, Prizes, more Prizes

解法:やるだけ

#include <iostream>
using namespace std;
typedef long long ll;
ll p[52];
int main( void )
{
  int n;
  ll a[5];
  ll ret[5] = {0,0,0,0,0};
  cin >> n;
  for( int i=0; i<n; i++ ) cin >> p[i];
  for( int i=0; i<5; i++ ) cin >> a[i];
  ll cur=0LL;
  for( int i=0; i<n; i++ ){
    cur += p[i];
    for( int j=4; j>=0; j-- ){
      if( cur >= a[j] ){
        ret[j] += cur / a[j];
        cur -= ( cur / a[j] ) * a[j];
      }
    }
  }
  cout << ret[0];
  for( int i=1; i<5; i++ ){
    cout << ' ' << ret[i];
  }
  cout << endl << cur << endl;
}