TopCoder SRM 438 DIV 2
| Problem | Check | Points |
| 250 | ○ | 204.20 |
| 500 | ○ | 222.36 |
| 1000 | - | - |
「問題が面白くない」と不評でした。力技だもんなぁ。
Problem 250 UnluckyNumbers
問題
You are given a set of integers called luckySet. An interval [A,B], where B is greater than A, and A and B are positive integers, is considered unlucky if none of the integers between A and B, inclusive, belongs to luckySet.
Given a vector
luckySet and a int n that is not greater than the maximum element in luckySet. Return the total number of unlucky intervals that contain n.
解説
The low constraints allowed us to enumerate all possible unlucky intervals and just count the number of unlucky intervals that contain n. First of all, convince yourself that we do not need to check for intervals [A,B] such that A or B are greater than the maximum element number in luckySet. This is because these intervals can never contain a number that is smaller than the largest number in luckySet.
We can now code a solution that iterates through all the intervals, verifies whether the interval is unlucky , and if it is an unlucky interval that contains n, increment our counter:
struct UnluckyNumbers { int getCount(vector <int> luckySet, int n) { int r=0; int C = *max_element( luckySet.begin(), luckySet.end() ); for (int A=1; A<=C; A++) for (int B=A+1; B<=C; B++) { bool good=true; for (int i=0; i<luckySet.size(); i++) if ( (B>= luckySet[i]) && (luckySet[i]>=A) ) good=false; if(good && (B>=n) && (n>=A) ) r++; } return r; } };This brute-force approach will prevent us from having to make assumptions like those that caused the low success rate in this problem.
Another approach:
It was of course possible to further analyze the problem and notice a more efficient solution::
- Add 0 to luckySet. It is observable that the problem statement implicitely defines 0 as a lucky.
- Sort luckySet.
- If n is in luckySet, return 0.
- Find two consecutive elements luckySet[i] and luckySet[i+1] such that (luckySet[i] < n) and (luckySet[i]>n).
- There are (n - luckySet[i]) different values for A and (luckySet[i+1] - n) different possible values for B. The total number of unlucky intervals becomes : (n - luckySet[i])*(luckySet[i+1] - n), since according to the statement, B>A, we subtract 1 from this result.
int getCount(vector<int> v, int X){ v.push_back(0); sort(v.begin(),v.end()); int idx=distance(v.begin(),lower_bound(v.begin(),v.end(),X)); if(v[idx]==X) return 0; return (n-v[idx-1]-1)*(v[idx] -n ) + (v[idx]-n-1); }http://www.topcoder.com/wiki/display/tc/SRM+438
My code
class UnluckyNumbers { public: int getCount(vector <int> luckySet, int n) { int result=0; sort(luckySet.begin(), luckySet.end()); int min=0, max=10000; for(int i=0 ; i<luckySet.size() ; i++){ if(min < luckySet[i] && luckySet[i] <= n) min=luckySet[i]; if(n <= luckySet[i] && luckySet[i] <= max) max=luckySet[i]; } int count=0; for(int i=min+1 ; i<max ; i++){ for(int j=i+1 ; j<max ; j++){ if(i<=n && n<=j){ count++; } } } return count; } };
Problem 500 FeudaliasBattle
問題
Feudalia's military is preparing a preemptive strike against Banania's military installations. Feudalia has two missile silos. Each silo has an unlimited number of missiles at its disposal, but can only fire a single missile at a time. When a missile is fired, it requires takeOffTime seconds before it can take off from its silo. Once it takes off, it requires distance/missileSpeed minutes to reach its target, where distance is the Euclidean distance between the silo and the target. When the missile reaches its target, the target is instantly destroyed. After a missile takes off, its silo requires rechargeTime minutes of preparation before it can launch another missile.
Two missile silos may not seem like a lot, but Banania is also a small country with only two military bases. It takes a single missile to destroy a military base. The general has ordered you to destroy both of Banania's military bases in as little time as possible. You are given vector
s siloX, siloY, baseX and baseY. Your silos are located at (siloX[0], siloY[0]) and (siloX[1], siloY[1]), and the enemy bases are located at (baseX[0], baseY[0]) and (baseX[1], baseY[1]). Return the minimum time in minutes required to destroy both enemy bases.
解説
Most coders used a variation of a solution based on classifying to which of up to 12 different cases a configuration belongs to and picking the best result among them. Instead, we are going to use an observation that does not only simplify the code and reduces the amount of thought given to each special case, it will also help us later when solving the harder version of this problem (Div1 1000).
After shooting a missile, a silo has to wait a constant amount of time before being able to shoot a new missile. This time is independent of the target that was picked for the first missile launch. Another useful observation is to notice that each silo needs to shoot at most two missiles. There is also no reason to target a base twice. We should know use these observations and simplify the problem, imagine that there are actually 4 silos each able to shoot at most one missile. Two of these silos are in the same coordinates as the others but need extra time before their first launch. Based on this idea, we can calculate the time that it will take each of the 4 silos to destroy each of the 2 bases.
The problem has become one in which we need to pick one of the four silos for each base. We canot pick the same silo for both bases (as each of our 4 silos represents one of the 2 original silos at an specific time, and the silos can't shoot two missiles at the same time).We may now use a brute force algorithm that goes through each of the 4*3 possible pairs of silos to assign to the bases, and pick the pair that provides the minimum time.
double getMinimumTime(vector <int> baseX, vector <int> baseY, vector <int> siloX, vector <int> siloY , int takeOffTime, int rechargeTime, int missileSpeed) { double required[4][2]; //required[i][j] = time for silo i to destroy base j for (int i=0; i< siloX.size(); i++) for (int t=0; t< 2; t++) //type of silo ( t=0 normal) (t=1 "imaginary" silo (second shot)) for (int j=0; j< 2; j++) { double dx = baseX[j] - siloX[i], dy = baseY[j] - siloY[i]; // the imaginary silos require extra time: required[i*2+ t][j] = sqrt(dx*dx+dy*dy) / missileSpeed + takeOffTime*(t+1)/60.0 + t*rechargeTime; } double res = 1e100; for (int i=0; i<4; i++) // try all pairs of for (int j=0; j<4; j++) // different silos if ( i!=j) res = std::min ( res, std::max(required[i][0] , required[j][1] ) ); return res; }http://www.topcoder.com/wiki/display/tc/SRM+438
My code
double distance(int ax, int ay, int bx, int by){ ll xx = bx-ax; ll yy = by-ay; return sqrt((double)( xx*xx + yy*yy )); } class FeudaliasBattle { public: double getMinimumTime(vector <int> baseX, vector <int> baseY, vector <int> siloX, vector <int> siloY, int takeOffTime, int rechargeTime, int missileSpeed) { double result; double takeOffTimeMinutes = (double)takeOffTime/60; double dist[2][2]; double misspeed[2][2]; for(int i=0 ; i<2 ; i++){ for(int j=0 ; j<2 ; j++){ dist[i][j] = distance(baseX[i], baseY[i], siloX[j], siloY[j]); misspeed[i][j] = dist[i][j] / (double)missileSpeed; } } double a, b; if(misspeed[0][0] > misspeed[1][0]) a = max(takeOffTimeMinutes+misspeed[0][0], takeOffTimeMinutes*2 + rechargeTime+misspeed[1][0] ); else a = max(takeOffTimeMinutes+misspeed[1][0], takeOffTimeMinutes*2 + rechargeTime+misspeed[0][0] ); b = min( misspeed[0][1] + takeOffTimeMinutes, misspeed[1][1] + takeOffTimeMinutes); if( a<=b ){ return a; } if(misspeed[0][1] > misspeed[1][1]) a = max(takeOffTimeMinutes+misspeed[0][1], takeOffTimeMinutes*2 + rechargeTime+misspeed[1][1] ); else a = max(takeOffTimeMinutes+misspeed[1][1], takeOffTimeMinutes*2 + rechargeTime+misspeed[0][1] ); b = min( misspeed[0][0] + takeOffTimeMinutes, misspeed[1][0] + takeOffTimeMinutes); if( a<=b ){ return a; } a = max(misspeed[0][0]+takeOffTimeMinutes , misspeed[1][1]+takeOffTimeMinutes ); b = max(misspeed[1][0]+takeOffTimeMinutes , misspeed[0][1]+takeOffTimeMinutes ); return min(a,b); } };
「プログラムなんて動きゃいいんだ」って強くいえないぐらいひどい。可読性無視。
Problem 1000 EndlessStringMachine
問題
A certain theoretical machine works by executing a program exactly s times. The first time it is executed, the program is given the String input as its input. For each subsequent execution, the program uses the output of the previous execution as its input.
The initial input is a string containing only lowercase letters. A program is defined as a string containing lowercase letters and '$' characters. The output of a program is simply this string with all instances of the '$' character replaced by the program's input. For example, if the input is "a" and the program is "$meric$", the first output would be "america". The second time it is executed, it will use "america" as its input, and its output will be "americamericamerica". This process is repeated s times, so for a large s, the output would be: "americamericamericamericamericamericamericamericamericamericamericamericamericamericamerica...".
Given the input, the program and s, return the substring of the machine's final output starting at index min and ending at index max, where min and max are inclusive 1-based indices. If an index between min and max exceeds the bounds of the final output, put a placeholder '-' character in its place.
解説
One should be careful to avoid overflows.
This problem requires 2 cases
1) When the number of $ is exactly 1.
2) When the number of $ in program is > 1Case 1 is of the form INPUT + $ + PROGRAM. => INPUT+(PROGRAM)^s
where a^b is string a concatenated b times and + concatenates string INPUT and the other string
if we want char at position X , then if it lies within INPUT.SIZE()
return INPUT[X] else return PROGRAM[ (X - INPUT.SIZE())% PROGRAM.SIZE()]; If we remove the input ,
we have a periodic string and the position of X in that periodic string is given.Case 2:
C is number of $ in string PROGRAM , C>=2
PC = PROGRAM.SIZE() - C , ie number of constants
We know that len[i] = len[i-1]*C + PC;How many lens should be computed ? A round estimate is around 31 lens should be atleast of the
length more than 2^31.seq after k moves is of length l[k], and there are p "$" and q chars in the replacement sequence,
l[k+1]= p*l[k] + q; l[k+2]=p*l[k+1] +q = p*(p*l[k] + q] + q = p^2*l[k] + pq + q;... looks like
l[n] = l[2]*p^n-2 + q*p^n-3 + ... + qBut we don't need lengths greater than max; We just store the lengths for each sequence until it exceeds max.
Once we have that ,
char get(int s,int pos);// returns the char at position after s iterations
if s==0 ie no iteration return inp.at(pos) // ie either '-' or inp[pos];
For each character in the string PROGRAM , process by either decrementing pos if it is a constant or
replacing $ with len[s-1] and checking if the string lies within it or after it.string get1(string input,string program,int s,int from,int to){ lint len=input.size() + (program.size()*1LL*s),isz=input.size(); int i; string ans; for(i=from;i<=to;i++){ if(i<len){ if(i<isz){ ans+=input[i]; } else { ans+= program[(i-isz)%program.size()]; } } else ans+="-"; } return ans; } string in,pr; char get2(int s,int pos){ if(s==0){ if(pos<in.size()) return in[pos]; else return '-'; } int i; for(i=0;i<pr.size();i++){ if(pr[i]=='$'){ if( len[s-1] > pos) return get2(s-1,pos); else pos=pos- len[s-1]; } else { if(pos==0) return pr[i]; else pos--; } } return '-'; } string getFragment(string input, string p, int s, int min, int max) { int c=0; in=input; pr=p; string ans,p1; int i; for(i=0;i<p.size();i++) if(p[i]=='$') c++; else p1+=p[i]; if(c==1) return get1(input,p1,s,min-1,max-1); s=std::min(s,40); len[0]=input.size(); for(i=1;i<s;i++){ len[i]=len[i-1]*c + (p.size()-c); if(len[i]>max) break; } s=i; for(i=min-1;i<=max-1;i++) ans+=get2(s,i); return ans; }http://www.topcoder.com/wiki/display/tc/SRM+438
