そのせいか、記事の順番が変。
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; } };
0 件のコメント :
コメントを投稿