How We Coding

<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

<7-2> DP - 회사 조직과 급여 (CorporationSalary)

PS/Topcoder training2018. 7. 1. 11:06

### DP ###


### SRM407 Div2 Level 2 ###



<소스코드>


- d[i] : i번 매니저의 부하직원들에 대한 salary의 합.

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
#include <vector>
#include <algorithm>
using namespace std;
 
class CorporationSalary {
public:
    vector<int> child[51];
    long long d[51];
 
    long long salary(int k) {
        if(child[k].size() == 0) return 1;
        if(d[k]) return d[i];
 
        long long ret = 0LL;
        for(int i=0; i<child[k].size(); i++)
            ret += salary(child[k][i]);
        return d[k] = ret;
    }
 
    long long totalSalary(vector<string> relations) {
 
        for(int i=0; i<relations.size(); i++) {
            d[i] = 0;
            for(int j=0; j<relations[i].size(); j++) {
                if(relations[i][j] == 'Y')
                    child[i].push_back(j);
            }
        }
 
        long long ans = 0LL;
        for(int i=0; i<relations.size(); i++)
            ans += salary(i);
        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-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01

[POJ/2431] Expedition

PS/etc.2018. 6. 27. 10:38

[2431] Expedition : http://poj.org/problem?id=2431


### Priority Queue ###


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct Exp { int dist, fuel; };
 
int n, L, P;
 
bool cmp(Exp a, Exp b)
{
    return L-a.dist < L-b.dist;
}
 
int main()
{
    scanf("%d", &n);
 
    vector<Exp> v;
    for(int i=0; i<n; i++) {
        int d, f;
        scanf("%d%d", &d, &f);
        v.push_back((Exp){d, f});
    }
 
    scanf("%d%d", &L, &P);
    sort(v.begin(), v.end(), cmp);
 
    int ans=0;
    int curL = P;
    priority_queue<int> pq;
 
    v.push_back((Exp){0, 0});
 
    for(int i=0; i<=n; i++) {
        while(L-v[i].dist > curL && !pq.empty()) {
            curL += pq.top(); pq.pop();
            ans++;
        }
        if(curL < L-v[i].dist) break;
        pq.push(v[i].fuel);
    }
 
    if(curL < L) ans = -1;
    printf("%d\n", ans);
    return 0;
}
 
cs

>> 34 번 라인이 없으면 틀렸다고 뜬다.

'PS > etc.' 카테고리의 다른 글

[POJ/1182] 먹이 사슬  (0) 2018.07.25
[카카오 코드 / 예선] 카카오프렌즈 컬러링북  (0) 2018.05.04
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

[3124] 최소 스패닝 트리

PS/SW Expert Academy2018. 6. 20. 21:11

### SW Expert Academy - D4 ###


[3124] 최소 스패닝 트리 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE


<소스코드>


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 <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int f, t, w; };
 
int p[100001];
 
bool cmp(P a, P b)
{
    return a.w < b.w;
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
bool Union(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        for(int i=1; i<=v; i++)
            p[i] = i;
 
        vector<P> g;
        for(int i=0; i<e; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g.push_back((P){a, b, c});
        }
        
        sort(g.begin(), g.end(), cmp);
 
        long long ans=0LL;
        for(int i=0; i<e; i++) 
            if(Union(g[i].f, g[i].t)) 
                ans += g[i].w;
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}
 
cs


>> Union-Find 를 이용한 크루스칼 알고리즘 사용.

>> ans 값은 int 범위를 벗어남에 주의.


'PS > SW Expert Academy' 카테고리의 다른 글

[1486] 장훈이의 높은 선반  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

티스토리툴바