How We Coding

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)

PS/Topcoder training2018. 7. 16. 12:50

### 전체탐색 ###


### SRM 484 Div2 Level 1 ###


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <string>
using namespace std;
 
class NumberMagicEasy {
public:
    int theNumber(string answer) {
        int card[4][8] = {{1, 2, 3, 4, 5, 6, 7, 8},
                         {1, 2, 3, 4, 9, 10, 11, 12},
                         {1, 2, 5, 6, 9, 10, 13, 14},
                         {1, 3, 5, 7, 9, 11, 13, 15}};
        
        int cnt=0;
        int check[17]={0};
        for(int i=0; i<4; i++) {
            if(answer[i] == 'Y') {
                cnt++;
                for(int k=0; k<8; k++) 
                    check[card[i][k]]++;
            }
            else {
                for(int k=0; k<8; k++) 
                    check[card[i][k]]--;
            }
        }
       
        for(int i=1; i<=16; i++) {
            if(cnt == check[i])
                return i;
        }
        return 0;
    }
};
 
cs


>> 정답이 있는 카드들에 대한 교집합 - 정닶이 없는 카드에 대해 차집합

>> 정답 카드의 갯수만큼 카운트된 숫자가 정답이 된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)

PS/Topcoder training2018. 7. 16. 12:26

### 전체탐색 ###


### SRM 433.5 Div2 Level 2 ###


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <vector>
#include <queue>
#include <string>
using namespace std;
 
int rSize, cSize;
int visited[51][51];
 
struct P { 
    int r, c; 
    P(int r, int c) : r(r), c(c) {}
};
 
bool safe(int r, int c)
{
    return (0 <= r && r < rSize) && (0 <= c && c < cSize);
}
 
class MazeMaker {
public:
    int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
        rSize = maze.size();
        cSize = maze[0].size();
               
        P cur(startRow, startCol);
        visited[startRow][startCol] = 1;
        
        queue<P> q;
        q.push(cur);
 
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int sz = moveRow.size();
            for(int k=0; k<sz; k++) {
                int nr = curR + moveRow[k];
                int nc = curC + moveCol[k];
                if(safe(nr, nc) && maze[nr][nc] == '.' && !visited[nr][nc]) {
                    P tmp(nr, nc);
                    q.push(tmp);
                    visited[nr][nc] = visited[curR][curC]+1;
                }
            }
        }
        int ans = 0;
        for(int r=0; r<rSize; r++) {
            for(int c=0; c<cSize; c++) {
                if(maze[r][c] == '.' && visited[r][c] == 0) return -1;
                if(maze[r][c] == '.' && ans < visited[r][c]) {
                    ans = visited[r][c];
                }
            }
        }
        return ans-1;
    }
};
 
cs


>> 방문할 수 있는 모든 곳을 탐색. 방문을 못한 곳이 있으면 -1; 모두 방문했다면, 방문한 곳중 가장 먼 곳이 정답.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)

PS/Topcoder training2018. 7. 16. 11:15

### 수학 ###


### SRM 443 Div2 Level 2 ###



<소스트리>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
using namespace std;
 
double dist(int x1, int y1, int x2, int y2)
{
    return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}
 
class CirclesCountry {
public:
    int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
        
        int ans=0;
        for(int i=0; i<X.size(); i++) {
            double d1 = dist(X[i], Y[i], x1, y1);
            double d2 = dist(X[i], Y[i], x2, y2);
            double r = (double)R[i]*R[i];
            if(d1 < r) ans++;
            if(d2 < r) ans++;
            if(d1 < r && d2 < r) ans -= 2;
        }
        return ans;
    }
};
cs


>>> 기본 아이디어는 시작 좌표와 목표 좌표가 둥근성에 포함되어 있으면 카운트.

>>> 예외처리 : 같은 성에 동시에 포함되어 있으면 카운트하면 안된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<8-4> 그리디 - 배치 시스템 (BatchSystem)

PS/Topcoder training2018. 7. 16. 01:54

### Greedy ###


### SRM 481 Div2 Level 3 ###


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
 
typedef long long int lli;
 
struct P { 
    int i, duration; 
    P(int i, int duration) : i(i), duration(duration) {}
};
 
struct userInfo {
    vector<P> v;
    lli sum;
    userInfo(vector<P> v, lli sum) : v(v), sum(sum) {}
};
 
bool cmp(P a, P b)
{
    return a.i < b.i;
}
 
bool cmp2(userInfo a, userInfo b)
{
    return a.sum != b.sum ? a.sum < b.sum : a.v[0].i < b.v[0].i;
}
    
class BatchSystem {
public:
    vector<int> schedule(vector <int> duration, vector <string> user) {
        int userIdx=0;
        map<string, int> msi;
        vector<userInfo> info;
        for(int i=0; i<duration.size(); i++) {
            if(msi.find(user[i]) == msi.end()) {
                msi[user[i]] = ++userIdx;
                vector<P> v; v.push_back(P(i, duration[i]));
                info.push_back(userInfo(v, duration[i]));
            }
            else {
                int idx = msi[user[i]]-1;
                info[idx].sum += duration[i];
                info[idx].v.push_back(P(i, duration[i]));
            }
        }
            
        for(int i=0; i<info.size(); i++) {
            sort(info[i].v.begin(), info[i].v.end(), cmp);
        }
 
        sort(info.begin(), info.end(), cmp2);
        
        vector<int> ans;
        for(int i=0; i<info.size(); i++) {
            for(int j=0; j<info[i].v.size(); j++) {
                ans.push_back(info[i].v[j].i);
            }
        }
        return ans;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03

<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)

PS/Topcoder training2018. 7. 14. 23:47

### SRM 464 Div2 Level 1 ###



<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
using namespace std;
 
class ColorfulBoxesAndBalls {
public:
    int getMaximum(int numRed, int numBlue, int onlyRed, int onlyBlue, int bothColors) {
        int ans=0;
        int minCnt = min(numRed, numBlue);
 
        ans = max(onlyRed+onlyBlue, bothColors*2) * minCnt;
        ans += ((numRed-minCnt) * onlyRed);
        ans += ((numBlue-minCnt) * onlyBlue);
        return ans;
    }
};
 
cs


>> 둘중 적은 것의 갯수만큼 섞을 수 있다. 그래서 그 최소개를 제대로 넣은 경우와 섞은 경우중 최대값이 정답이 된다.

>> 나머지에서는 자기 박스에 자기 공을 넣을 것이기 때문에 그 값을 더해주면 된다.

'PS > Topcoder training' 카테고리의 다른 글

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01

<7-5> DP - 악수 (HandShaking)

PS/Topcoder training2018. 7. 4. 00:43

### DP ###

### SRM363 Div2 Level 2 ###


<소스코드>


d[i] : n 명이 하는 악수가 성립하는 조합의 수.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
 
long long d[51];
 
class HandsShaking {
public:
    long long countPerfect(int n) {
        long long *ret = &d[n];
        if(n < 2) return 1;
        if(n == 2) return 1;
        if(*ret) return *ret;
 
        for(int i=0; i<=n-2; i+=2) {
            *ret += (countPerfect(i)*countPerfect(n-2-i));
        }
        
        return *ret;
    }
};
 

cs


>> 이번 문제에서 나온 수를 카탈란 수 라고 한다...

'PS > Topcoder training' 카테고리의 다른 글

<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01

<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)

PS/Topcoder training2018. 7. 3. 00:55

### 전체탐색 ###

### SRM425 Div2 Level2 ###



<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <vector>
using namespace std;
 
int visited[50][50];
int dr[]={0, 0, 1, -1};
int dc[]={1, -1, 0, 0}; // E W S N
int stack[20];
 
class CrazyBot {
public:
    int n;
    int dir[4];
    double ans;
    void dfs(int cnt, int r, int c) {
        if(cnt == n) {
            double tmp=1.0;
            for(int i=0; i<n; i++) {
                tmp *= (double)dir[stack[i]]/100;
            }
            ans += tmp;
            return ;
        }
        visited[r][c] = 1; 
        
        for(int k=0; k<4; k++) {
            int nr = r+dr[k];
            int nc = c+dc[k];
            if(!visited[nr][nc]) {
                stack[cnt] = k;
                dfs(cnt+1, nr, nc);
            }
        }
        visited[r][c] = 0; 
    }
 
    double getProbability(int n, int east, int west, int south, int north) {
        this->n = n;
        dir[0] = east; dir[1] = west;
        dir[2] = south; dir[3] = north;
        ans = 0;
        dfs(0, 25, 25); 
        return ans;
    }
};
 
cs


>> n의 최대값이 14이므로 50x50 개의 판을 가정하고 그의 가운데인 (25,25)에서 로봇이 이동하기 시작한다고 생각하였다.

>> 성공적으로 보행할 확률은 이동할 수 있는 모든 경우의 수에 해당하는 확룰을 더하면 된다.

'PS > Topcoder training' 카테고리의 다른 글

<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01

<5-4> 전체탐색 - 회문 (ThePalindrome)

PS/Topcoder training2018. 7. 1. 21:39

### 전체탐색 ###

### SRM428 Div2 Level 1 ###



<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
using namespace std;
 
class ThePalindrome {
public:
    bool isP(char *str, int s, int e) {
        if(s >= e) return 1;
        return str[s]==str[e] ? isP(str, s+1, e-1) : 0;
    }
    int find(string s) {
        char str[101]={0};
        int size = s.size();
        for(int i=0; i<size; i++)
            str[i] = s[i];
        for(int i=0; i<size; i++) {
            if(isP(str, 0, size-1+i)) return size+i;
            for(int j=0; j<=i; j++) {
                str[size+i-j] = str[j];
            }
        }
        return size*2-1;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01
<7-2> DP - 회사 조직과 급여 (CorporationSalary)  (0) 2018.07.01

<7-4> DP - 킹 나이트 체스 (ChessMetric)

PS/Topcoder training2018. 7. 1. 15:09

### DP ###

### TopCoder Collegiate Challenge 2003 Round 4 Div 1 Level 1 ###


 <소스코드>


- d[r][c][rest] : (r, c) 에서 (er, ec) 까지 rest 번만에 갈 수 있는 방법의 수


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <vector>
#include <cstring>
using namespace std;
 
int n, er, ec;
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1, -2, -2, -1, 1, 2, 2, 1, -1};
int dc[] = {1, 0, -1, 1, -1, 1, 0, -1, 1, -1, -2, -2, -1, 1, 2, 2};
 
long long d[101][101][51];
 
bool safe(int r, int c)
{
    return (0 <= r && r < n) && (0 <= c && c < n);
}   
 
long long solve(int r, int c, int rest)
{
    long long *ret = &d[r][c][rest];
 
    if(rest == 0) {
        if(r == er && c == ec) return 1LL;
        return 0LL;
    }
    if(*ret != -1) return *ret;
 
    *ret = 0LL;
    for(int k=0; k<16; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc)) {
            *ret += solve(nr, nc, rest-1);
        }
    }
    return *ret;
}
 
class ChessMetric {
public:
    long long howMany(int size, vector<int> start, vector<int> end, int numMoves) {
        int sr = start[0];
        int sc = start[1];
        er = end[0]; ec = end[1];
        n = size;   
        
        memset(d, -1, sizeof(d));
        return solve(sr, sc, numMoves);
    }
};
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01
<7-2> DP - 회사 조직과 급여 (CorporationSalary)  (0) 2018.07.01

<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)

PS/Topcoder training2018. 7. 1. 12:37

### DP ###


### 2004 TCCC Online Round 4 Div 1 Level 1 ###


<소스코드>


- d[i][j][k] : i번째 차례, j == 0 이면 이전 이웃에게 기부를 받음, k == 1 이면 첫번째 집에서 기부를 받음


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[41][2][2];
 
class BadNeighbors {
public:
    int n;
    int donation(vector<int> &donations, int i, bool prev, bool first) {
        int *ret = &d[i][prev][first];
        if(first && i == n-1) return 0;
        if(!first && i == n) return 0;
        if(*ret) return *ret;
        
        *ret = donation(donations, i+1, 0, first);
        if(!prev) *ret = max(*ret, donation(donations, i+1, 1, first)+donations[i]);
        return *ret;
    }
 
    int maxDonations(vector<int> donations) {
        n = donations.size();
        int ans = donation(donations, 1, 1, 1)+donations[0];
        return max(ans, donation(donations, 1, 0, 0));
    }
};
cs


>> first 가 1 이면 마지막 집은 n-2 번째 집이 되고, first 가 0이면 마지막 집은 n-1번째 집이 된다. (첫번째 집이 0번째 집이라고 생각)



<해설 소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <vector>
using namespace std;
 
class BadNeighbors {
public:
    int maxDonations(vector<int> donations) {
        int i;
        int ans = 0;
 
        int N = donations.size();
        int *dp = new int[N];
 
        for(i=0; i<N-1; i++) {
            dp[i] = donations[i];
            if(i > 0) dp[i] = max(dp[i], dp[i-1]);
            if(i > 1) dp[i] = max(dp[i], dp[i-2]+donations[i]);
            ans = max(ans, dp[i]);
        }
 
        for(i=0; i<N-1; i++) {
            dp[i] = donations[i+1];
            if(i > 0) dp[i] = max(dp[i], dp[i-1]);
            if(i > 1) dp[i] = max(dp[i], dp[i-2]+donations[i+1]);
            ans = max(ans, dp[i]);
        }
 
        delete []dp;
        return ans;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-2> DP - 회사 조직과 급여 (CorporationSalary)  (0) 2018.07.01

티스토리툴바