SRM 321 ~ 330

(2013. 05. 30 ~ )

 

(명시하지 않은 경우, Easy = 250, Mid = 500, Hard = 1000)

	Easy	Mid	Hard
SRM 321 DIV 1	○ (= DIV 2 Mid)	△ (Failed System Test  & Fixed)
DIV 2	○	△ (Failed System Test  & Fixed)	X -> △ ( Editori_ & Code )
SRM 322 DIV 1	○ (= DIV 2 Mid)	X -> (Cannot Understand Editorial)
DIV 2	○ (7' 00, 236.32점)	○ (17' 30, 382.04점 but 검증 X)	○ (1시간 28분(초과), 347.86)
SRM 323 DIV 1	○ (= DIV 2 Mid)	△ (Failed System Test  & Fixed)
DIV 2	△ (급히 내고 두번 Fail)	○ (한번에 통과, 그러나 시간 안 쟀음)	○ (시간 안 쟀음, 458.06)
SRM 324 DIV 1	○ (= DIV 2 Mid)	○ (한번에 통과, 326.82)
DIV 2	△ (급히 내고 두번 Fail) (30분이나 소모함)	○ (한번에 통과, 15분, 438.03)	○ (한번에 통과, 60분, 399.05)
SRM 325 DIV 1	X -> △ (간단한 문제였는데 시간 복잡도를 잘못 추측)	(DIV 2 Hard와 같음)
DIV 2	○ (한번에 통과, 4분 37초, 243.83)	○ (한번에 통과, 약 20분, 383.22)	X -> △ ( Editori_ & Code ) 그러나 다른 방법은 이해 못함.
SRM 326 DIV 1	X -> △ (= DIV 2 Mid)	X -> (Cannot Understand Editorial)
DIV 2	○ (쉬움. 점수 잊음)	X -> △ (Editorials)	X -> △ ( Editori_ & Code )
SRM 327 DIV 1	X -> △ (= DIV 2 Hard)	X -> △ (Editorials)
DIV 2	○ (247.68)	○ (310.47 / 550) (두 번째로 푼 것의 점수)	X -> △ ( Editori_ & Code )
SRM 328 DIV 1	○ (= DIV 2 Mid)
DIV 2	○	○ (시간은 초과했으나 풀긴 품)	X
SRM 329 DIV 1
DIV 2	○ (234.92)	○ (343.62)	X
SRM 330 DIV 1	○ (= DIV 2 Mid)	X -> Trie 이용 문제
DIV 2	○ (249.39 - 두 번째 푼 것)	○ (432.25 / 450 - 두 번째 푼 것)	△ (Failed System Test  & Fixed) (922.50 - 세 번째 반복으로 푼 것)

 

(SRM 321 DIV 2 - Easy : Just code it. Test all word cases)

 

 

SRM 321 DIV 2 - Mid : Failed in System Test -> Fixed and passed.

[Problem]  With given rectangular chocolate, return how many cuts are needed to make   another rectanglar chocolate with given traget area.  Chocolate is consisted of several 1 x 1 square cells, and dividing the chocolate only can be done by cutting   along straight lines between the cells.    [My approach]  - If target area is greater than given chocolate, it is impossible.  - If target area is same with given chocolate, no cut is needed.  - Else, get all the divisor pairs of target chocolate area,     If one of the divisor is same with height(or width) of given original chocolate, only one cut is needed.     Else, two cuts are needed.  - Of course, width / height of the target chocolate must be shorter, or equal to than original chocolate.    [ What was wrong? ]  - Let the original chocolate's width and height be ori_w, ori_h.    Also. name the target chocolate's be tar_w, tar_h.    When comparing four values, there are four ways.    :: 1. (ori_w == tar_w && ori_h > tar_h)   / 2. (ori_w > tar_w && ori_h == tar_h)    :: 3. (ori_w == tar_h && ori_h > tar_w)   / 4. (ori_w > tar_h && ori_h == tar_w)  - However, I considered only case 1 and 2. It made the code fail system test.      [ To solve this problem easy ]  - To simplfy each case, we do the simple things as follow :   1. Care the impossible & 'no need' cases :: (area exceeds : (-1))  (target area == original area : (0) )   2. Now, the target area is smaller than original chocolate.       In this case, if the width (or height) is a divisor of the target area, only one cut is needed!   3. Else, care the all divisors of target area, and check whether target area can be made.       If it is possible, two cuts will be needed.   4. Else, now in this case, there is no possible way to make target chocolate. return -1.    [Tips]  1. To get the divisor pairs, do not use sqrt(x), but use this code instead : // when getting the divisor pairs. vector > divs; for(int i = 0; i * i <= x; i++) if( x % i == 0 ) divs.push_back(make_pair(i, x/i)); // Don't use this code for(int i = 0; i <= (int) sqrt((double)x); i++) if( x % i == 0 ) divs.push_back(make_pair(i, x/i));

 

 

SRM 321 DIV 2 - Hard : Couldn't make answer -> read editorials and other's code.

[Problem]  Get the minimum key input to print all alphabets in one word, in lexicographical order.  For example, suppose we want to deal with "cab". Initial position is zero.  At first, we must print 'a' first, because this is the lexicographically first alphabet.  So, we move cursor to 'a' by pressing right arrow key. Now, to print the alphabet 'a', press Enter key.  Next, we have to print 'b', so we press the right arrow key. and enter key.  Last, we want to print 'c', so we press left arrow key for 2 times, and enter key.  Total number of key press is =  2 + 2 + 3 = 7.  In a word, duplicated alphabet can exist. Find the minimum key input to print all alphabets.    [What was hard for me]  - I had no idea. I could realize this problem is kind of DP, not greedy.    However, I could not define the partial problems. and also could not make the code.    [ How to Solve]  - The key idea is that :    when we are printing one kind of alphabets, the cursor must end at the leftmost or rightmost position    among the same alphabets. (How can I prove it ?)  - Optimal way to print one kind of alphabet 'a' is clearly move to the last 'a', and print 'a's along the way.     For 'b' and next alphabets, there are two choices :      - go leftmost, and rightmost  / go righmost, and leftmost.    [Tips]  - DO NOT USE LONG & COMPLEX variable names if the meaning is clear.     (ex. leftMost -> L)     IT IS NOT USEFUL in problem solving. Even it makes it harder to read the code.  - Finding duplicated elements' leftmost & rightmost position, use this code(and also the number) : int cnt = 0, L = INF, R = -INF; for(int i = 0; i < s.size(); i++) if(s[i] == now) { L = min(L, i); R = max(R, i); cnt++; }

 

 

SRM 321 DIV 1 - Mid : Time limit Exceeded -> Fixed and passed.

[Problem]  For given integer array, find the lexicographicall first sort result with given condition.   - condition : for 0 <= i < V.size(), V[i] + 1 must be different from V[i+1].    [Anlaysis]  Because the maximum number of elements that the vector has is 50, so we cannot consider all cases.  Instead, since we just have to make the lexicographically first array, we do the following :  1. Just make the cases in lexicographical order,  2. Check if it satifies the condition.  3. If we get the answer, immediately stop and return the answer.    [My approach]  At first I failed because I thought that all same elements must be consecutive to each other.  However, it was totally wrong idea, so I failed just 5th case of system test -_-...  Before writing the code, I should have verified my algorithm with much more test cases,  with my pencil. I wasted much time to make code for totally wrong algorithm...    [2nd approach]  Next algorithm : Find the unused & lexicographically first elements, push it to the answer vector.  At the first moment that all elements of given vector are used, we'll have the right answer.  -> It is a DP approach (Dynamic Programming)  However, it failed to pass the time limit for large input cases.  That's because much time was consumed to search unused elements in vector (vector<int> used).    [3rd approach]  I decided to revise the 2nd approach. The key is to use multiset<int>, instead of vector<int>.  After 10~20 minutes, I finally got the answer, and passed the system test.    [Tips]  - When iterating set<int>, deleting some element using 'that' iterator is dangerous.     ('erase' : Iterators, pointers and references referring to elements removed by the function are invalidated.                    All other iterators, pointers and references keep their validity.)  - When we need to delete an element and restore it, (from <set> or <map>) use this code : void makeSort(vector& v) { if(!ans.empty()) return; if(s.empty()) { ans = v; return;} multiset::iterator iter; for(iter = s.begin(); iter != s.end(); iter = s.upper_bound(*iter)) { // using upper_bound() instead of iter++ , beacuse we need to erase things, if(v.empty() || v.back() + 1 != *iter) // and we don't have to check duplicate elements. { int tmp = *iter; v.push_back(tmp); s.erase(iter); // deleting one element makeSort(v); v.pop_back(); // restoring one element s.insert(tmp); iter = s.find(tmp); // restoring the iterator (Note : It is NOT same with prior value !!) } } }    [느낀 점]  1. 손으로 테스트 케이스 여러 개 만들어보지도 않고 그냥 코드 짜지 말자. 시간만 더 버린다.  2. 코드 제출 전 컴퓨터로 다양한 테스트 케이스 만들어서 손으로 한 것과 비교해보자.       막 제출하는 습관이 아직도 남아있다. 각종 테스트 케이스를 만들어보기 전엔 절대 제출하지 말자.    [P. S]  1. 에디토리얼의 풀이는 DP가 아니다!!   -> 이제야 이해했다. 원소를 앞에서부터 검사하는데, 넣을 수 없는 경우는 단 두 가지.   1. 이 원소가 ret.back() + 1 과 같은 경우. 이는 조건에 따라서 넣을 수 없다.   2. 이 원소가 남은 원소 중의 최소이며, 그 값이 남은 원소들 중 최대값보다 1 작은 경우. (ex. 1 1 1 1 1 1 2)    그것을 푸는 코드는 다음과 같다.   http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm321

 

(SRM 322 DIV 2 - Easy : 쉬움. 내가 짠 코드의 모양이 고수의 코드 모양과 별로 다르지 않아 뿌듯했다.)

 

SRM 322 DIV 2 - Mid

[Problem]  There are several groups of workers. In each group, all workers have same skill level.  We are going to hire some of them. We can choose any number of people of any groups.  Productivity is defined by (Minimum skill level of people we hired) * (number of people we hired).  Our goal is to carefully select workers to maximize the productivity.    [My Idea]  - If we decided to choose one of workers whose skill level is 'c',  we must hire all workers    who have same skill level, of course. (Because hiring same level of workers does not decrease    the minimum skill level, but increases the number of people)  - If we decided to choose one group whose skill level is 'c', we must choose all people    whose skill level is not less than 'c'. (Of course, same reason with above)  - So, we just sort this groups according to skill levels. From fully skilled groups     to poorly skilled groups, calculate the total productivity for each minimum skill level.     For each iteration, find max value, and it will be the answer.    [Other's code]  - ACRush give another insight. He noticed that there are only 1000 kinds of skill level.    So, he get the result by iterating all cases from skill level 1 to skill level 1000.    His code is very simple and clear, so i was impressed.    [Tips]  - We can get insight by "Carefully Inspecting the Range of Inputs !!"    (Like ACRush's method)  - When sorting "pair" in 'largest number first' order, don't forget to use greater<pair<int, int> >().    ( It is not greater<int> !! )

 

 

SRM 322 DIV 2 - Hard : Passed. but could not submit in 70 minutes.

[Problem]  A 10 x 10 checkboard is given. On the board, there are ships whose length is in range from 1 to 4.  Ships must be placed parallel to edges of the checkboard, and must occupy some cells equal to their lengths.  Ships must NOT touch each other. Touching is defined that "For two ships, occupied cells share vertex(es)".  For given checkboard and ships, find that if the checkboard satisfies the conditions.    [My approach]  - (Expect) The function which gets the number of neighboring 'X' for given position will be used many times.  - If the number of all occupying cells are different from (sum of all ships' lengths), it must be "REJECTED"  - We can check all 'X' in the board, and get the length when we are going down / right.     - If the length exceeds 4, it is an error. (No ship is longer than 4)     - Count the number of each length to some vector<int> : it will be used for checking the # of ships.  - Then we covert all 'X' that we discovered into 'T' (another alphabet).     - After converting these, check all neighbors for each 'T' we just have discovered.      - If we have neighboring 'X', two ships are touching each other.  - Next, check the # of ships. If it is wrong, return "REJECTED";  - Now get score and return it.    - Here is my code : // global variables int n; vector s; int len[5]; struct BattleshipChecker { string checkBoard(vector board){ s = board; n = s.size(); for(int y = 0; y < n; y++) { for(int x = 0; x < n; x++) { if(s[y][x] == 'X') { pair k = maxLen(y, x); if(k.first > 4 || k.second > 4) return "REJECTED"; // length exceeds 4 // no two-way check (It will be checked by neighbors check) for(int j = 0; j < k.first; j++) s[y][x+j] = 'T'; for(int i = 0; i < k.second; i++) s[y+i][x] = 'T'; for(int j = 0; j < k.first; j++) if(numOfAdjX(y, x+j) != 0) return "REJECTED"; for(int i = 0; i < k.second; i++) if(numOfAdjX(y+i, x) != 0) return "REJECTED"; len[max(k.first, k.second)]++; } } } for(int i = 1; i <= 4; i++) if(len[i] != 5-i) return "REJECTED"; // # of ships int k, l, point = 0; for(k = 0; k < n; k++) { for(l = 0; l < n; l++) if(s[k][l] != '.') break; if( l == n) point++; } for(k = 0; k < n; k++) { for(l = 0; l < n; l++) if(s[l][k] != '.') break; if( l == n) point++; } char str[30]; sprintf(str, "ACCEPTED, %d POINTS", point); return string(str); } // return the max length when going right / down pair maxLen(int y, int x) { int right = 0, down = 1; // going right for(int j = x; j < n; j++) if(s[y][j] == 'X') right++; else break; for(int i = y+1; i < n; i++) if(s[i][x] == 'X') down++; else break; cout << right << " " << down << endl; return make_pair(right, down); } int numOfAdjX(int y, int x) { int sum = 0; for(int i = -1; i <= 1; i++) for(int j = -1; j <= 1; j++) if(getVal(y+i, x+j) == 'X') sum++; return sum; } int getVal(int y, int x) { if(x < 0 || x >=n || y < 0 || y >= n) return 0; else return s[y][x]; } };    [Other Approach (Editorial) : Much simpler ]  - At first, we check the diagonal touch.     - If there is no diagonal touch, all ships are placed like straignt lines.  - Next, we explore all 'X' by DFS(depth first search). From the search, we get the length of each lines.     - If the length exceeds 4, it is "REJECTED".     - Count the number of each length to some vector<int> : it will be used for checking the # of ships.  - Next, check the # of ships are correct.  - Last, get the score.    => The key idea that made this approach much simpler than my solution is,      1. After we checking diagonal touching, we don't have to think more about touching.      2. By using DFS, finding lengths became much simpler.    => Here is the code : // global variables vector bd; int used[10][10]; int len[5]; struct BattleshipChecker { string checkBoard(vector board){ bd = board; // 1. diagonal check for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++) if( (bd[i][j] == 'X' && bd[i+1][j+1] == 'X') || (bd[i+1][j] == 'X' && bd[i][j+1] == 'X') ) return "REJECTED"; // 2. DFS for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) if(bd[i][j] == 'X') { int length = size(i, j); if(length > 4) return "REJECTED"; len[length]++; } // 3. # of ships check for(int i = 1; i <= 4; i++) if(len[i] != 5-i) return "REJECTED"; // 4. get score int rows[10] = {0, }, cols[10] = {0, }; for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) if(bd[i][j] != '.') { rows[i] = 1; cols[j] = 1; } int points = 20; for(int i = 0; i < 10; i++) points -= (rows[i] + cols[i]); stringstream ss; ss << points; string str; ss >> str; return "ACCEPTED, " + str + " POINTS"; } int size(int y, int x) { if(y < 0 || y >= 10 || x < 0 || x >= 10 || used[y][x] || bd[y][x] != 'X') return 0; used[y][x] = 1; return 1 + size(y+1, x) + size(y, x+1) + size(y-1, x) + size(y, x-1); } };      [ Tips ]  - Passed System Test -> the result of :    - Verifying the algorithm with many cases before coding it.    - careful examining with many manually-made inputs.  - We can use DFS even in 'BOARD' problem !!  - Don't confuse the getVal(int y, int x) function's condition.     - If (y >= height), it should be handled as exceptional case. NOT (y > height).     - Instead of directly changing the value of 'BOARD', use int mark[10][10] instead.       (in above code, it is used[10][10])    [ Feelings]  - Maybe the first code in here is the longest code I have ever made in Topcoder SRM practice.     - Although I could not submit in 70 minutes, I am pleased that I've made this solution pass the system test at once !!  - I should practice how to imagine new idea that makes my code much simpler.

 

 

SRM 323 DIV 2 - Easy

[Comment]  It is easy problem when the (# of elements <= 3), but if we deal with more elements,  we should use another algorithm.    [My approach]  Just care the all combinations in three (or less) elements.  Here is the code :    [From Editorial]  http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm323  In this approach, we can handle the problem which have more than 3 elements.  It uses a method similar to 'mathmatical induction'.  Here is the code : struct IrreducibleNumber{ int getIrreducible(vector A){ sort(A.begin(), A.end()); int ret = 0; for(int i = 0; (i < A.size() && A[i] <= ret+1); i++) ret += A[i]; return ret + 1; } };    [Feeling]  I repeated the mistakes   - Didn't test the algorithm before coding.   - Didn't test the code before submitting.   - So Failed to Pass the system Test.

 

 

SRM 323 DIV 2 - Mid

[Problem]  Given integer sequence A[], and we can replace each element A[i] to (len - A[i]),  is it possible to make A[] to strictly increasing sequence? If possible, is the answer unique?    [What was Hard for me]  At first, I misunderstood the problem - I thought that this problem is saying :  "With the given milestions, find the number of ways that we can place these milestones".  It was a completely different problem, but I coded it without examining Example Cases.  So after my code is written, it failed just to pass example case 0.    Carefully, aggresively read and analyze problems in English. Read more and more.  It is better than re-writing the code because of misunderstanding the problem.    [New Approach]  After I correctly understood the problem, I cannot help using DP to solve it.  It is simple : For each A[i]   - Making strictly increasing sequence. If impossible, stop.   - If A[i]or (len - A[i]) are larger than last element of the current path,      push it to the path and check next element.   - If path is completed, store it and increase (the # of answer) by 1.   - If (the # of answer >= 2), it means there are multiple solutions, so STOP searching.   - Make answer and return it : end.   - Here is the code : int n, len; vector f, ret; int ansNum = 0; struct RoadsAndFools { void solve(int pos, int last, vector& path) { if(ansNum >= 2) return; if(pos == n) { ret = path; ansNum++; } // x <= y int x = min(f[pos], len-f[pos]); int y = max(f[pos], len-f[pos]); if(last < x) { path.push_back(x); solve(pos+1, x, path); path.pop_back(); if(x == y) return; path.push_back(y); solve(pos+1, y, path); path.pop_back(); } else if(last < y) { path.push_back(y); solve(pos+1, y, path); path.pop_back(); } } string determineOrientation(int length, vector frontSides){ len = length; f = frontSides; n = f.size(); vector path; solve(0, -1, path); if(ansNum >= 2) return "MULTIPLE SOLUTIONS"; else if(ansNum == 0) return "NO SOLUTION"; string ans; for(int i = 0; i < n; i++) { char c[20]; sprintf(c, " %d", ret[i]); ans += string(c); } return ans.substr(1); } };    [Tips]  - At first, I dealed with the "first add case" seperately, using if(pos == 0) ~~.    However, by reading JongMan's Code, I realized that if we use another variable 'last' -    which means the last added element -, we don't have to deal that case seperately !    (Assuming that A[-1] = -INFINITY. Use this technique!!)  - Also, by JongMan's code, I got the another technique :    when making string like "3 5 4 7", use [sprintf(s, " %d", value)] and [ ans.substr(1); ]    It is slightly simpler than [sprintf(s, "%d ", value)] and [ ans.substr(0, ans.size()-1); ].    [Editorial's Approach]  - Making sequence by using smallest possible element for each A[i]. (lexicographically first)  - If impossible, it has no solutions.  - If possible, check all elements of compeleted sequence (vector<int> ret)    whether it still strictly increase even if we replace ret[i] with (len-ret[i]).      (It is sufficient to make only one replacement for each index - more than two replacement are not needed.)  - This code is somewhat simpler than my approach.

 

 

SRM 323 DIV 2 - Hard

[Problem]  Make the string which does not have 'k' identical consecutive strings as its substrings.  The kinds of alphabet we use is limited, and the length of wanted string is fixed.  Make this string that is lexicographically first.    [My approach]  1. Make the test function which determines that given string is 'k-unrepeatable' or not.  2. Make string from the first character to last character. For each position :    - At first, try 'A', test the string : If it passed the test, go next position. If didn't, try next alphabet 'B', repeat.    - Repeat until : we find the solution OR no solution exists. If there is no solution, go back to the previous position.    - Get the result string.    [ Theory ]   - The method I used to solve this problem is called 'backtracking'. I didn't know that.   - From WikiPedia : Backtracking      Backtracking is a general algorithm for finding all (or some) solutions to some computational problem,      that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks")      as soon as it determines that c cannot possibly be completed to a valid solution.    [ To improve this solution ]   - My test function is inefficient. It tests intervals duplicately even if it already checked previously.     - The key is, we just have to check repeat of the substrings which includes the last character of current string.     - So I modified it. It will be much faster than before.   - If the length of string were longer than 50, this change may be crucial for this solution to pass time limit.

 

 

SRM 323 DIV 1 - Mid

[Problem]  A person is floating in an ocean. In two-dimensions coordinate, he is at the origin.  He can swim at V units/sec, and the ocean wave moves him to the +x direction by U units/sec.  In this case, for given reach point (x, y). we must determine whether he can reach there.  Also, if he can get there, find the minimum time spent on reaching there.    [My Approach]  - It is just solving an 1-variable, 2nd-order equations. So we use quadratic formula (근의 공식)  - So, divide the cases into 3 categories, and solve them seperately.    [Why I failed to pass the Sys. test]  - I sholud have dealt with EVERY case by writing/drawing with my pencils.  - To care all cases, when using 'IF' (or 'ELSE IF'), end it with ELSE.  - After writing the all cases, I could passed the test.    [Much Simpler Approach]  - After solving the problem, I read the AlMag's code. It was MUCH simpler then mine.   - His idea was that :    1. The answer should be found by solving 2nd-order equations.    2. So, in ax^2 + bx + c = 0, specially care all cases when a == 0. Now it is always 2nd-order eqn.    3. After that, find that this Eqn has real roots, by using Discriminant(판별식).    4. Solve the 2nd-order Eqn and get the roots. The answer is the value of minimal non-negative root.       - If all roots are negative, there is no answer.  - This is my code which resembles his code : struct Survived{ double minTime(int x, int y, int V, int U){ double a = V*V - U*U; double b = 2*U*x; double c = -(x*x + y*y); if(fabs(a) < 1e-9) // V == U { if(fabs(b) < 1e-9) // x == 0 || V == 0 ( == U) { if(fabs(c) < 1e-9) return 0.0; // x == y == 0 else return -1.0; // From equation } if(x < 0) return -1.0; else return -c/b; } double D = (b/2)*(b/2) - a*c; if(D < 0) return -1.0; double t1 = ((-b/2) - sqrt(D)) / a; double t2 = ((-b/2) + sqrt(D)) / a; if(t1 > t2) swap(t1, t2); if(t1 < 0 && t2 < 0) return -1.0; else if(t1 < 0) return t2; else return t1;    [Tips]  - When dealing with the "FLOATING NUMBERS", use very small number. (epsilon, eps)    (For example, if we want to find that 'V*V-U*U == 0', use fabs(V*V-U*U < 1e-9), as above code).      - It really happens. At first, I failed the test because of just 1e-7 difference.....  - Dealing with the 1-variable, 2nd-order equation, use above code. (ax^2 + bx^2 + c = 0)  - If we have two values(roots), and we want to make t1 <= t2,     do not use t1 = min(ans1, ans2), t2 = max(ans1, ans2).    use if (t1 >= t2) swap (t1, t2); (as above code)

 

 

SRM 324 DIV 2 - Easy

[Problem]  For given strings, find the number of 'intervals' whose strings have all same initial alphabet.   - count intervals only that : 1. cannot be extended  / 2. is longer than 1.   - consider lowercase & uppercase alphabets as same things.    (ex. Traffic transfer goto gocc gogom Gos trans giraffe)  -> There are 2 intervals : [ Traffic transfer ], [goto gocc gogom Gos]    [What was hard for me]  - 아직도 index와 연속(consecutive) 문제만 나오면 맥을 못 추고 있다!!  - 이 쉬운 문제에 이렇게나 시간을 많이 쓰고, 그것도 Fail을 하다니..  - Index 변수를 자유 자재로 다루어야 하는데, 어떻게 연습할까?!    => 규칙적인 문양을 배열에 담는 연습을 많이 하라!! (kcm 조언)    [Tips]  - For changing alphabet to lower(upper)case, use char tolower(c) or toupper(c)     - also, there is checking function -> bool islower(c) or isupper(c)  or isalpha(c)  - When finding some 'consecutive' intervals, use this code :

(SRM 324 DIV 2 - Mid : 제일 쉬움. 그냥 구현하면 끝.)

(그렇지만, 사람들의 코드를 보니 나보다 1줄, 2줄이라도 더 간단히 구현했다.)

 

 

SRM 324 DIV 2 - Hard

[어려웠던 점]  데이터를 분석하고 알고리즘을 만드는 데 너무 많은 시간이 걸렸다.    [풀이]  결국 이건, 모든 고객이 똑같은 구매 패턴을 보이는 두 상품이 하나의 번들이 되는 것이다.  주어진 행렬을 transpose 하면, 한 string은 한 상품에 대한 각 고객의 구매 여부를 나타내는 것이 된다.  이 string이 같으면 바로 번들로 묶을 수 있는 것!    [느낀 점]  - 주어진 행렬을 transpose했을 때 얻을 수 있는 정보를 생각해보는 것도 좋은 습관이다.    - Transpose하지 않고 구현한 코드가 매우 긴 반면, 했을 때는 if(a == b)로 간단히 구현 가능.

 

당분간 다시 한글로 써야겠다.

영어로 쓰는 것도 좋지만, 지금 당장은 코딩 실력부터 늘릴 때.

 

 

SRM 324 DIV 1 - Mid

[문제 해석]  격자 위에 여러 점들의 위치가 주어질 때, 모든 격자점들 사이의 맨하탄 거리가 최소인 점 P를 찾아서,  그 P와 다른 격자점들 사이의 거리의 총합을 반환하라.  - 이렇게 되는 이유는, 다음과 같이 나눌 수 있다.   1. 두 플레이어가 있을 때, 둘 사이의 x, y값을 두고 오히려 벗어나서 택할 필요가 없으며(거리 낭비)   2. 맨하탄 거리이므로, X와 Y는 서로 영향을 주지 않는다.     [문제를 푼 방법]  이 문제를 보고 나서 JMBook 1장에 나와 있는 문제와 똑같다는 것을 알아챘다.  하지만 부끄럽게도 직접 답을 생각하기보다는 빨리 풀어보고픈 마음이 앞서 그 풀이를 기억해내기보다는  책에서 빠르게 찾아서 그대로 사용하고, 그것을 검증한 뒤에 제출하였다.    [다른 사람들의 코드]  다른 사람들의 풀이는 크게 다음과 같은 두 가지로 나뉜다.   - 1. 나와 같은 풀이로, 가운데 있는 점을 직접 지목해서 구한 경우   - 2. 모든 Player의 위치에서 다른 플레이어들 간의 위치를 구하고, 그것의 min값을 구한 경우.        - 이는 정답 위치 P가, 플레이어의 위치들 중 하나일 것이라는 가정에 바탕을 둔 답이다.    1은 이해가 가는데, 2의 가정이 왜 옳은 것일까?  -> 1을 통해 2를 증명할 수 있다. 점의 개수가 홀수인 경우, 가운데 있는 점의 위치가 최소 총합 거리를 만들며,      점의 개수가 짝수인 경우, 가운데 있는 두 점 '사이(경계 포함)' 의 어느 곳을 잡아도 최소 총합 거리가 된다.      즉, 가운데 있는 점을 아무거나 잡으면 거리를 최소화 하게 된다는 것이다.    [Editorial]  에디토리얼은 정확한 증명이 나와 있었다.  1. 한 점에서 모든 선수가 경기를 치루는 것이 이익이라는 증명(귀납법을 통해서)  2. 그 점은 앞에서 말했던 점(각각의 median)이 된다는 증명  멋진 증명이다.  http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm324

 

(SRM 325 DIV 2 - Mid : 쉬운 문제인데 입력을 잘못 받아서 디버깅하느라 한참을 해멨다 !)

  - 완전히 익숙해지기 전까지는, 입력을 확인해보는 습관을 들이자.

 

SRM 325 DIV 2 - Hard

[문제]  vector<int> A가 주어질 때, 어떤 정수 X에 대해, A의 각 원소와의 차의 절대값을  모두 더한 값이 P이하가 되도록 하는 X의 개수를 구하여라.    [접근법]  점과 점 사이의 구간을 통해서 접근해야한다는 것은 어느 정도 감을 잡았지만,  그 이상으로 나아가는 것이 너무 막막했다. 어떻게 시작해야 할 지, 어디서 예외를 처리해야 할 지.  가짓수가 너무 많아 보였고, 어떻게 해야 모든 경우를 처리할 수 있는지가 너무 막막했다.    [Editorial]  세부적 처리를 잘 해 놓은 모범 코드를 보았다.  그걸 몇 번씩 읽고서도, 한참 동안 고민하고 나서야 어떤 알고리즘인지, 어떻게 처리했는지를 알았다.  대체 이걸 어떻게 생각해낼 수 있다는 말인가...?  어떻게 연습해야 하는 것일까?    Editorial에는 각각을 처리하는 방법 대신 또 다른 하나의 방법을 제시한다   이는 이 함수가 아래로 볼록한 함수임을 이용하여 이분 검색으로 푸는 것인데,  이분 검색을 몰라서 이해하지 못했다.    [느낀 점]  이렇게 세부적인 처리를 생각해내는 능력은 어디서 나오는 것일까....?

 

 

SRM 325 DIV 1 - Easy

(쉬움, 세부내용 없음)  - 그냥 DP로 푸는 문제인데, 시간 복잡도를 잘못 계산해서 DP가 불가능하다고 생각하고    한참동안 다른 답을 찾아 해멨다.. 결국 포기하고 Editorial을 보니 그냥 DP라고..  - DP의 시간 복잡도는 부분 문제의 개수에 달려 있다. 완전 탐색처럼 n! 등이 아니니 조심할 것!    - Recurrence Function으로 작성하기는 익숙한데, 다른 사람들을 보니 Iterative method를 사용했다.    - Iterative로 짜는 것도 익숙해져야 할 필요가 있다. 세 번 정도 다시 짜 보았다.

 

(325 DIV 1 - Mid는 어디로?)

 

 

SRM 326 DIV 2 - Mid

[문제]  각 사람이 가진 특징들을 모두 알고 있다고 하자. 예를 들어 사람 0은 a, b, c의 성질을,  사람 1은 b, e, z의 성질을, 사람 2는 b, c, f의 성질을... 등등등.  이 때, 이 여러 가지 성질들 중에 몇 가지를 골라서, 다음 조건을 만족하는 성질 집합을 만든다고 하자.    1. 최소 한 사람은 이 집합에 있는 모든 성질을 가지고 있다.    2. 이 집합의 성질을 모두 가진 사람은 최소 두 사람이다. (즉, 이 집합만으로 단 한 사람이 결정되지 않는다.)  이 때, 이런 집합들 중 원소의 개수가 최대인 집합의 원소 개수를 구하여라.    [나의 접근법]  - 표현 방식을 바꾼다 : 각 사람마다 그가 가진 성질로 표현하는 것이 아니라,     각 성질마다 그에 해당하는 사람을 비트로 표현해서 나타냈다.  - 즉, 성질 a를 가진 사람의 목록이 이진수로 1101 이고, 성질 b를 가진 사람의 목록이 0110이면,     성질 a, b를 가진 사람의 목록은 1101 & 0111 == 0101 이다.  - 각 성질들을 모은 부분집합을 하나하나 만들어서 집합이 완성될 때마다 그 원소의 개수를 체크하면 된다.     시간 복잡도는 2^(성질의 개수) 가 된다.    [틀린 점]  - 성질의 종류는 50개 이상이 될 수 있다. 2^50만 되어도 시간 내에 탐색할 수 없다.    - 그래서 가지치기 및 휴리스틱 / 최적화를 시도하였다.      - 성질을 공유하는 사람의 수가 0명이면, 탐색 중단.      - 앞으로 남은 모든 성질을 집합에 추가해도 best보다 종류가 적거나 같다면, 탐색 중단.      - 어떤 성질 a를 가진 사람이 많다면, 그 성질부터 탐색 (best를 빨리 찾을 수 있게 함).   => 이렇게 가지치기를 하여 상당히 속도를 향상시켰으나, test case 한두 개는 TLE로 통과하지 못했다.    [Editorial]  - 이 문제는 사실 두 사람씩 짝지어서 공통으로 가진 원소의 개수를 찾으면 되는 문제였다...    두 사람만 비교해도 되는 이유는 다음과 같다.     1. 어차피 그 성질 집합에 해당하는 사람은 두 사람만 있으면 되고,     2. 세 사람을 비교한다고 했을 때는 두 사람을 비교했을 때보다 그 성질의 개수가 적어진다.   - 즉, 간단한 find문으로 이 문제를 해결할 수 있다.    [Tips]  - string 하나에, 공백으로 구분되어 있는 string 여러 개가 있을 때, 그 각각을 나누는 방법!    아래 코드와 같이 하면 된다. (공백이 토큰인 문자열을 여러 문자열로 나누어 저장하기) // For example, givenString = "Apple Banana Melon Grapes" // After spliting, elemetns = { "Apple", "Banana", "Melon", "Grapes" } void split(string givenString, vector elements) { stringstream ss(givenString); string tmp; while(ss >> tmp) elements.push_back(tmp); }     - 만일 콤마나 기타 문자로 구분된 경우에는, 콤마를 공백으로 바꿔주고 함수를 실행하면 된다.

 

 

SRM 326 DIV 2 - Hard

[문제 설명]  풀장 각 위치에서의 벽의 높이가 주어질 때, 채울 수 있는 물의 양을 구하여라.    [내 접근]  전혀 감이 오지 않아서 접근하지 못했다.    [풀이]  - Editorial의 풀이    - 각 위치의 'Flow Level'을 만들어서 시뮬레이션한다. Flow Level은, 인접한 4개의 땅 중 물의 높이가 가장 낮은 곳의      높이로 정의가 된다. 이렇게 바뀐 물 높이가 벽 높이보다 낮을 경우, Flow Level은 벽 높이로 바꾼다.    - 이렇게 했을 때에 풀리는 이유는, 인접한 땅 중 자기보다 낮은 물높이가 있을 경우.       현재 물 높이는 그 높이보다 클 수 없게 되기 때문이다.    - 이렇게 시뮬레이션해서 더이상 값이 변하지 않을 때가 바로 물이 더이상 흐르지 않을 때이다.    - Rng_58 의 풀이 (이쪽이 더 직관적이다)    - 물 높이 x를 정한다. (1로는 채울 수 없으므로, 우리가 탐색할 물 높이는 2부터 9까지.)    - 가장자리에서 시작해서, 물 높이가 x가 되도록 모든 땅을 채웠을 때, 밖으로 새나가는 땅들을 표시해둔다.       (dfs를 이용한다.)    - 마크가 끝나면, 물이 새지 않는 곳이면서 땅의 높이가 x 보다 낮은 곳을 찾는다.      그곳이 바로 (x - 땅높이) 만큼을 저장할 수 있는 땅이다. 그만큼 ans를 증가시키고, 땅 높이를 그만큼 올린다.    - 사실 우리는 높이를 2부터 9까지 순차적으로 탐색하므로, 저장 가능한 물의 양인 (x - 땅높이) 는 항상 1이다.       따라서 ans++, 땅높이++; 을 해주는 것이 좋다.    - 땅 높이를 올려주는 이유는, 겹쳐서 세지 않게 하기 위해서이다.         - 높이가 1인 땅에 물을 2로 채울 때와, 3으로 채울 때는 각각 1, 2만큼을 저장할 수 있는데,            이걸 더해서 3만큼 저장한다 하면 이는 겹쳐서 센 것이다. 이를 방지하기 위해서 땅의 높이를 1 증가시킨다.    [느낀 점]  - 별걸 다 DFS로 풀수 있구나... rng_58 좀 짱인 듯 싶다.  - 물을 시뮬레이션 할 수 있다니. 배울 것이 정말 많이 있다.    [Tips]  - 상하좌우 칸을 탐색할 때, dx와 dy 배열을 따로 두고 하면 좋다. 하나 만들어두자. 예를 들면 다음과 같다. // 상, 하, 좌, 우 int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; // 주어진 좌표의 상하좌우 칸을 탐색하며 조건을 수행한다. void dfs(int y, int x) { if(~~~~~) return; // 종료 조건 ~~작업 수행. // 실행문 for(int k = 0; k < 4; k++) // 탐색 dfs(y+dy[k], x+dx[k]); }

 

 

SRM 327 DIV 2 - Mid

처음에 풀 땐 못 풀었는데, 시간이 지나고 다시 도전하니 답이 보였다.  연필로 식을 적다보니 아이디어가 보여서, 그것으로 풀어보니 맞았다.    [문제 설명]  주어진 수열의 규칙성을 찾아, 다음에 나올 숫자를 반환하는 함수를 작성하는 것이 목표이다.  {1, 3, 5, 7, 9}의 경우 11을, {3, 6, 12, 24, 48}의 경우 96을 반환한다.  규칙은 "multiply by a and add b" 이다. 즉, 전항과 후항의 관계가 선형 식으로 정의된다.  만일 이러한 규칙으로 주어진 수열을 만들 수 없을 경우는 "BUG"를,  주어진 수열이 너무 적거나 하여 다음에 올 수 있는 숫자의 종류가 두 가지 이상인 경우는 "AMBIGUOUS"출력.    [나의 접근]  내가 해결한 방법은, 최초 3항을 가지고 보면 a와 b가 확정된다는 것이다.  (a2, a1) 의 관계식에서, (a1, a0)의 식을 빼면, a의 값을 확정지을 수 있고, 따라서 b의 값도 확정지어진다.  여기서 분모가 0이 되는 경우만 잘 처리해주면 된다. (모든 항이 같아야 한다)    이런 방식으로 접근할 수 없는 경우는, 항의 개수가 2개 이하일 때 뿐이다.  항의 개수가 1개라면 무조건 "AMBIGUITY"가 되며, 2개인 경우는,  두 항이 같은 경우는 그 값으로 하면 되고, 두 항이 다른 경우는 "AMBIGUITY"가 된다.      [Editorial의 접근 방식]  a가 될 수 있는 값들과, b가 될 수 있는 값들을 다 시도해 보는 것이다.  이는 주어진 숫자의 범위가 [-100, 100] 으로 제한되어 있기 때문에 가능한 풀이이다.  -> 이 방식으로 푸는 것도 굉장히 간단하다. 원소가 하나인 경우와 두개인 경우만 잘 생각해주고,       나머지는 일일이 a와 b값을 시도해보면서 '되나 안 되나' 를 확인하면 된다.  -> 내가 모르겠는 것은, 왜 a값의 범위가 최대 200, 최소 -200 인 것일까? 에디토리얼에도 결론만 있다.        -> 이럴 때는 그냥, 큰 값이라 생각하는 정도를 잡아서 돌려보는 것도 하나의 방법이 된다.    [느낀 점]  저번에 풀 때는 참 안 풀렸었는데,지금 보니 잘 되서 기분이 좀 좋다.

 

 

SRM 327 DIV 2 - Hard

[문제 설명]  주어진 string이 자음, 모음, 그리고 '?"로만 이루어진다.  모음이 3개 연속이거나, 자음이 5개 연속일 시 ugly 라고 하며, ugly하지 않은 string은 nice 라고 한다.  '?'을 자음이나 모음으로 어떻게 바꾸던 nice하게 만들 수 없으면(무조건 ugly 이면) defintely ugly이며,  그 반대로 '?'를 어떻게 바꾸어도 ugly하게 만들 수 없으면 definitely nice라고 한다.    주어진 string이 def, nice인지, def, ugly인지, 아니면 ugly도 되고 nice도 될 수 있는지 알아내라.    [나의 접근]  완전 탐색으로, 물음표를 만날 때 마다, 이것이 자음일 때와 모음일 때로 나누어서 탐색했다.  DP로 풀고 싶었으나, 각각의 상태가 개별적으로 정의될 수 있다고 생각하지 못했다. 그래서 완전 탐색이 됐다.  그러나 시간 초과로 2^50 개를 탐색할 수는 없었고, 이런저런 최적화 시도에도 불구하로 fail하고 말았다.    [Editorial의 풀이]  두 가지 풀이를 제공한다.    1. DP로 푸는 법. 나는 이것이 불가능할 것이라 생각했는데, dp의 캐쉬를 구성할 때,      [현재 위치][직전 연속한 모음의 개수][직전 연속한 자음의 개수] 로 구성하면 된다고 한다.      생각해보면,  ???A??B? 와 같은 상황에서, BBBA??B? 나, AABA??B? 나,      뒤에 미치는 영향은 똑같다. 정작 중요한 것은 물음표 직전에 있는 연속한 자/모음의 수이다.      -> 즉 이 문제에서는 cache의 각 원소가,        반드시 "고유한(유일한)" 단어 배치를 가질 필요가 없음을 보여준다!     -> 이걸 알아채고 캐쉬만 잘 만들면 간단히 해결되는 DP문제였다.      -> 두 가지 함수 (아래 나온 2개) 를 DP로 구현하면 된다.    2. 두 번째 풀이는 간단한 듯 하지만 좀 어렵기도 하다. 이 풀이에선 두 가지 함수를 만든다 :     1) 적절히 변환해서 Ugly하게 될 수 있는지 여부를 반환하는 함수.     2) 적절히 변환해서 Nice하게 될 수 있는지 여부를 반환하는 함수.    여기서 어려운 것은 2) 를 만드는 것이다. 어떻게 해야 적절히 변환해서 Nice가 될 수 있는지를 아는가?       이 풀이에서는, 각 물음표마다 'Nice'로 만들 수 있는 값들만을 넣어가며, 매 번 이 string을 검사한다.    그래서 마지막 물음표를 채웠을 때까지 Ugly하지 않으면, '이 string은 nice할 수 있다.' 라고 판단한다.    어떻게 보면 당연한 것 같기도 한데, 여러 가지 경우의 경우가 생긴다고 생각해서 처음엔 이해가 좀 어려웠다.    여러 가지 경우가 생기는 것은(물음표가 정해지지 않는 것은).      'nice' 한 경우가 두 개 이상이라는 것이므로 문제가 없다.    [Tips]  1. v.size() 의 type은 unsigned int 이다. 지금까지는 전혀 이것이 중요하다고 생각하지 않았는데,      오늘 이로 인해 버그를 고쳐야 했다. 다음과 같은 코드를 보자.      이 코드는 주어진 string에 대해서, "ABC" 가 들어있는지를 찾아 반환하는 코드이다. bool findABC(string s) { for(int i = 0; i <= s.size() -3; i++) if(s.substr(i, 3) == "ABC") return true; return false; }  이 함수는 (조금 비효율적이지만) 잘 작동한다. index가 0부터 시작해서, 마지막까지 3글자씩 떼어 보면서,  "ABC"와 같은 것이 있는지를 찾는 것이다. 여기서 대체 무엇이 틀린 것일까?    답은 이것이다 => 이 함수에, 3글자보다 작은 string을 대입하면, false가 나지 않고 runtime error가 난다.  그 이유는 s.size() - 3에 있다. s.size() 는 unsigned int로서, 오직 0이상의 값을 갖는다. 또한,  프로모션에 의해서 unsigned int와 int가 계산될 때는, 값이 unsigned int가 되는 것이다.    따라서, (unsigned)2 - 3 을 계산하면, -1의 값이 나오는 것이 아니라, (2^32)-1 의 매우 큰 값이 나온다.  그러므로 엉뚱한 곳에서 substr을 실시하게 되어 런타임 에러가 발생한다.    그러므로, v.size() 등을 사용할 때는, index가 음수의 값이 나올 수 있는 경우  잊지 말고 (int)v.size() - 3과 같이 써주자.  사실 size가 int의 범위를 넘어가는 경우는 흔치 않으므로,  그냥 애초에 매크로로 (int)v.size() 라고 기록해 두고 쓰는 사람도 많다.      2. find라는 이름을 가진 함수는 STL에 참 많다. 살펴보자.     1) std::find (algorithm 헤더에 들어 있는 것으로, 가장 일반적)          - find(v.begin(), v.end(), value) 와 같이 사용한다. 반환 값은 찾은 위치의 iterator.     2) string::find          - 주어진 string에서 원하는 string(또는 character)을 찾는다.             찾은 index를 반환한다. 못 찾은 경우 -1 ( == std::npos) 을 반환한다.          - 쓰임새가 많으니, 살펴봐두자.          - http://www.cplusplus.com/reference/string/string/find/     3) set::find, map::find, multiset::find, ~~~ 등, 여러 가지 경우가 있다.         - Tree 구조로 값을 저장하는 컨테이너의 경우, find를 좀 더 효율적으로 구현해 놓아서           이렇게 따로 마련된 find를 쓰는 것이 더 낫다.

 

 

SRM 327 DIV 1 - Mid

[문제 설명]  이차(또는 일차)방정식의 근이 주어질 때, 이 근을 만들 수 있는 이차방정식의 개수를 구하여라.  (각 계수의 제한 범위가 주어진다.)    [풀면서 느낀 것]  너무 어려웠다..... 오랜만에 SRM을 풀어서 그런 것인지, (물론 성공 비율도 엄청 작긴 했으나)  예외 처리할 것도 많고, 부딪히다 못해 답답해서 3시간이나 자다가 결국 Editorial 보고 나서야 풀었다.  Petr이 문제를 냈다는데... 나쁜.........    [푸는 법]  기본적으로 이 근이 유리수냐, 무리수냐에 따라 풀이가 나뉜다.  이 방정식의 모든 계수가 정수이므로, 근이 무리수인 경우라면 이차방정식은 1개 뿐이다.  이 1개의 식에 특정한 계수를 곱해서 만들 수 있는 모든 식의 개수를 찾으면 답이 되는 것 (0을 곱하는 경우도 포함)    어려운 것은, 근이 유리수로 나오는 경우이다.  예를 들어, 근이 유리수 a/b 로 나왔다고 하자. 이 경우, (at-b)(ct-d) 에서, c와 d를 임의로 정할 수 있다.  범위만 맞으면, 이 식은 주어진 근을 해로 갖는 방정식이 되는 것이다. (이차식 뿐만 아니라, 일차식도 가능)    푸는 방법은, 조건을 만족하는 c와 d를 정하면 되는 것이다.  내가 최종적으로 해결하지 못 한 것은, c와 d를 일일이 탐색 (10만 X 10만) 하여 찾으려 했다는 것.  시간 초과에 걸려 해결하지 못했다.    푸는 방법은, c와 d 중 하나의 문자에 대해서만 iteration을 돌고,  각 c의 값에 대해 d의 개수들을 부등식으로 따로 찾을 수 있다는 것이다.  그 교집합의 d를 세어 주면, 우리가 찾는 모든 식의 개수가 나온다.    [느낀 점]  수학의 식이 간단해 보여도, 그것을 잘 활용할 수 있는 능력은 사람에 따라 천차만별이다.  난 당연히 모든 값을 탐색해야 찾을 수 있을 거라고 생각했는데,  부등식을 조금만 조작하니 O(N)에도 찾을 수가 있었다.  더 공부해야겠다.

 

(SRM 328 ~ 329 는 건너뛰었음)

 

SRM 330 DIV 2 - Mid

[문제 설명]  <=, <-, =>, -> 이와 같은 것들을 Arrow라고 할 때, 주어진 문자열에서 가장 긴 Arrow의 길이를 찾으시오.    [나의 접근 방식]  나는 주어진 문자열을 왼쪽에서부터 순회하면서 <--- 와 <==== 를 찾으려 했고,  오른쪽에서부터 왼쪽으로 순회하면서 반대 방향의 화살표를 찾으려 했다.  결과적으로 답은 나왔으나, 처음 제출시엔 틀렸고, 구현이 느리고 복잡했다.    [모범 답안]  1. 다른 사람의 코드를 보니, 주어진 문자열의 길이가 최대 50이라는 점을 이용하여     모든 substring을 만들어서 비교했다. 이 경우, 시간 복잡도는 문자열을 만드는 데 O(N^2)에,     문자열을 비교하는 데에 O(N)으로 약 O(N^3) 이 걸린다. 이 정도면 충분하다.   => 문자열 문제에서는 항상 substr을 이용할 수 있는지 생각해보자. 구현이 매우 간단해진다.    2. Editorial 에서는, string::find을 이용해서 찾았다. 이것의 시간 복잡도 역시 O(N^3)이나, 좀 더 빠르다.     구현이 정말 간단해서 깜짝 놀랬다. 정말 말도 안 되게 간단하더라..    [Tips]  1. (부분)문자열 문제에서는 아까도 썼지만, string::substr과 string::find를 쓸 수 있는지 항상 생각하자.     구현이 무지하게 간단해진다.

 

 

SRM 330 DIV 2 - Hard

[문제 설명]  주어진 숫자에 대해, 이 숫자보다 큰 수 중 가장 작은 팰린드롬을 구하시오.  (ex. 주어진 숫자가 12345 이면, 답은 12421)    [나의 접근]  - 처음에는 string을 int로 바꾸고자 했으나, 크기가 50자리임을 보고 불가능함을 알았다.     어떻게 보면 그 사이즈 덕분에 문자열을 이용해서 풀면 된다는 힌트가 되기도 했다.  - 팰린드롬인 만큼, 기본 아이디어는 '반을 떼서 뒤에 뒤집어 붙이면 된다' 이다.  - 케이스를 3개로 나누었다.    1. 그냥 주어진 숫자로 팰린드롬을 만들어도 답이 되는 경우    2. 1이 아닌 경우      2-1.  주어진 문자열의 문자 개수가 홀수인 경우      2-2.  주어진 문자열의 문자 개수가 짝수인 경우  - 각각 주의해서 코드를 작성하면 되긴 했으나, 각 경우마다 테스트를 제대로 하지 않고 무작정 제출해서     시스템 테스트로 계속 150점씩 깎아먹었다.  - 세 번 정도 다 지우고 다시 짜고 나서야 한 번에 Accept를 받았다.  => 결과적으로 이 방법은, 아주 정확히 구현하지 않는 이상 좀 비효율적인 방법이다.    [다른 풀이]  - Editorial의 방법이다. 매우 간단한다.  - 모든 숫자가 9로 이루어진 경우만 제외한다면, 만들어지는 수의 자리수는 원래 수의 자리수와 똑같다.    따라서 그 경우만 예외 처리를 하고, 이후에는 숫자의 왼쪽 반을 가지고 오른쪽에 반대로 붙여서 일단    팰린드롬을 만든다. 이 수가 만일 원래 수보다 크다면 그냥 이것이 답이 된다.    만일 원래 수보다 크지 않다면, 가운데에 있는 값을 1 증가시키면 그게 답이다. 그래야 가장 적게 증가하니까.    증가시키려는 수가 9라면, 그것을 0으로 바꾸고, 그 바깥쪽의 두 수를 1 증가시키면 된다.    [Tips]  - string으로 주어진, 같은 길이의 긴 숫자 두 개(long long 변환 불가)를 크기 비교하는 경우,     그냥 string 크기 비교(<, >)를 활용하면 된다. 자리수가 같아서 가능한 것.  - 문자열로 주어진 숫자의 '다음 숫자(= 1을 더한 숫자)' 를 문자열로 반환하는 함수는,    그냥 1의 자리부터 시작해서 각 문자를 검사하면서, 9를 만나면 0으로 바꾸고 다음 자리를 검사,    9가 아닌 문자를 만나면 1 증가시키고 반복문 종료하면 된다. 쉬움.