SRM334Div2

ここ数日、bloggerで投稿・編集ができない状態だった。
そのせいか、記事の順番が変。


250

class SupermarketDiscount {
public:
  int minAmount(vector <int> g) {
    int mn = 1 << 24;
    for(int i=0; i<(1 << 3); ++i){
      vector<int> v(1);
      for(int j=0; j<3; ++j){
        if( i & (1 << j) )v[0] += g[j];
        else v.push_back( g[j] );
      }
      int sum = 0;
      for(int j=0; j<v.size(); ++j){
        sum += v[j];
        if( 50 <= v[j] )sum -= 10;
      }
      mn = min(mn, sum);
    }
    return mn;
  }
};

500

pair<int, int> path[6 * 6 + 1];
bool vis[6][6];

bool rec(int idx)
{
  vis[ path[idx].first ][ path[idx].second ] = true;
  if(idx == 6 * 6)return true;
  const int di[] = {-2, -2, -1, -1, 1, 1, 2, 2};
  const int dj[] = {-1, 1, -2, 2, -2, 2, -1, 1};
  bool flg = false;
  for(int d=0; d<8; ++d){
    int ni = path[idx].first + di[d];
    int nj = path[idx].second + dj[d];
    if( ni == path[idx+1].first && nj == path[idx+1].second){
      flg = rec(idx+1);
      break;
    }
  }
  return flg;
}

class KnightTour {
public:
  string checkTour(vector <string> c) {
    for(int i=0; i<c.size(); ++i){
      int a = 5 - (c[i][0] - 'A');
      int b = c[i][1] - '1';
      path[i] = make_pair(a, b);
    }
    path[c.size()] = path[0];
    fill( &vis[0][0], &vis[6-1][6], false );
    if( !rec(0) )return "Invalid";
    if( count( &vis[0][0], &vis[6-1][6], true ) != 6 * 6 ){
      return "Invalid";
    }
    return "Valid";
  }
};

1000
コード中の変数pathをstackでやったらTimeLimitだった。

inline lli pw(lli n, int p)
{
  if( p == 1 )return n;
  if( p == 2 )return n * n;
  if( p == 3 )return n * n * n;
  if( p == 4 )return n * n * n * n;
  if( p == 5 )return n * n * n * n * n;
  if( p == 6 )return n * n * n * n * n * n;
  return -1;
}

map<lli, lli> mn;
set<lli> vis;

const int N = 1000000;
lli path[N];
int size;

lli rec(lli n, int k)
{ 
  if( mn.count(n) )return mn[n];
  vis.insert(n);
  path[ size++ ] = n;

  lli m = n;
  lli sum = 0;

  while( n ){
    sum += pw(n % 10LL, k);
    n /= 10LL;
  }

  lli r;
  if( vis.count(sum) ){
    r = min(m, sum);
    while( path[--size] != sum ){
      r = min(r, path[size]);
    }
  }
  else{
    r = min(m, rec(sum, k));
  }
  
  return mn[m] = r;
}

class ExtendedHappyNumbers {
public:
  long long calcTheSum(int A, int B, int K) {
    lli sum = 0;
    mn.clear();
    for(int i=A; i<=B; ++i){      
      vis.clear();
      size = 0;
      sum += rec(i, K);
    }
    return sum;
  }
};