Single Round Match 437 (Div2/500point)
「整数nを10進法表記にして、k回数字の入れ替えを行ってつくることのできる最大の値は何か」という問題。ただし0で始まる数字を作ってはいけない。それが避けられない場合は-1を返せ、とのこと。
for文で前置インクリメントを使ってないのはよくないな。あと最後で最大の値を検索しているけど、setはソートされてるんじゃないのか。
coding time: 0:26:30.942, Passed System Test, 305.56 points
vector<int> to_vec(int n){ vector<int> result; while(n){ result.insert(result.begin(), n % 10); n /= 10; } return result; } vector<int> swap(vector<int> n, int i, int j){ // n is a copy swap(n[i], n[j]); return n; } int to_int(vector<int> xs){ int result = 0; for(size_t i=0; i < xs.size(); i++){ result = result * 10 + xs[i]; } return result; } class TheSwap { public: int findMax(int n, int k) { vector<int> xs = to_vec(n); size_t N = xs.size(); if(N == 1) return -1; set<int> cur; cur.insert(n); set<int> next; typedef set<int>::iterator siter; for(size_t times=0; times < k; times++){ for(siter iter=cur.begin(), end=cur.end(); iter != end; iter++){ int n = *iter; vector<int> xs = to_vec(n); for(size_t i=0; i<N; i++){ for(size_t j=i+1; j<N; j++){ vector<int> new_xs = swap(xs, i, j); if(new_xs[0] != 0){ next.insert(to_int(new_xs)); } } } } if(next.empty()) return -1; cur = next; next.clear(); } int result = 0; for(siter iter=cur.begin(), end=cur.end(); iter != end; iter++){ if(*iter > result){ result = *iter; } } return result; } }