Category: algorithm

You are working in the HR department of a huge corporation. Each employee may have several direct managers and/or several direct subordinates. Of course, his subordinates may also have their own subordinates, and his direct managers may have their own managers. We say employee X is a boss of employee Y if there exists a sequence of employees A, B, …, D, such that X is the manager of A, A is the manager of B, and so on, and D is the manager of Y (of course, if X is a direct manager of employee Y, X will be a boss of employee Y). If A is a boss of B, then B can not be a boss of A. According to the new company policy, the salary of an employee with no subordinates is 1. If an employee has any subordinates, then his salary is equal to the sum of the salaries of his direct subordinates.

You will be given a String[] relations, where the j-th character of the i-th element is ‘Y’ if employee i is a direct manager of employee j, and ‘N’ otherwise. Return the sum of the salaries of all the employees.

#include <string>
#include <vector>
using namespace std;

long long salaries[50] = {0};

class CorporationSalary {
    public:
        long long totalSalary(vector <string> relations){
            long long total = 0;
            for (int i = 0; i < relations.size(); i++){
                total += getSalary(i, relations);
            }
            return total;
        }
        long long getSalary(int i, vector <string> relations) {
            if (salaries[i] == 0) {
                long long salary = 0;
                string relation = relations[i];

                for (int j = 0; j < relation.size(); j++){
                    if (relation[j] == 'Y') {
                        salary += getSalary(j, relations);
                    }
                }
                if (salary == 0) salary = 1;

                salaries[i] = salary;
            }
            return salaries[i];
        }
}

const int h = 5, w = 4;

int dfs(int nowh, int noww){
    if(nowh > h || noww > w) return 0;
    if(nowh == h && noww == w) return 1;
    return dfs(nowh + 1, noww) + dfs(nowh, noww + 1);
}

const int h = 5, w = 4;
int dp[h + 1, w + 1];

int dfs(int nowh, int noww){
    if (nowh > h || noww > w) return 0;
    if (nowh == h && noww == w) return 1;
    if (dp[nowh][noww] != 0) return dp[nowh][noww];
    return dp[nowh][noww] = dfs(nowh + 1, noww) + def(nowh, noww + 1);
}

const int h = 5, w = 4;
int dp[h + 1][w + 1];

void calc(){
    int i, j;
    dp[0][0] = 1;
    for(i=0; i<=h; i++) {
        for(j = 0; j<= w; j++){
            if (i != 0) dp[i][j] += dp[i - 1][j];
            if (j != 0) dp[i][j] += dp[i][j - 1];
        }
    }
}

int ws[5] = {3, 4, 1, 2, 3};
int ps[5] = {2, 3, 2, 3, 5};
int maxw = 10;

int ret = 0;

void knapsack(int n, int w, int p){
    if ( w > maxw) return;
    ret = max(ret, p);
    if(n >= 5) return;
    knapsack(n + 1, w, p);
    knapsack(n + 1, w + ws[n], p + ps[n]);
}

int ws[5] = {3, 4, 1, 2, 3};
int ps[5] = {2, 3, 2, 3, 5};
int maxw = 10;
int dp[6][11];
int ret = 0;

for(int i = 0; i <= 5; i++){
    for(int j = 0; j <= maxw; j++) {
        if(j + ws[i] <= maxw){
            dp[i + 1][j + ws[i]] =
                max(dp[i + 1][j + ws[i]], dp[i][j] + ps[i]);
                ret = max(dp[i + 1][j + ws[i]], ret);
        }
    }
}

void calc(){
    A();
    for(int i = 0; i < n; i++){
        B();
        for(int j = 0; j < m; j++){
            C();
        }
    }
}

素数計算

bool isPrime(int n){
    if(n < 2) return false;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

logが含まれるもの

int bitcount(int n){
    int ret = 0;
    while(n > 0) {
        if (n % 2 == 1) ret++;
        n /= 2;
    }
    return ret;
}

int fibonacci(int n) {
    if(n==0) return 1;
    if(n==1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

計算量の大きい関数

void calc(int n){
    for(int i = 0; i < n; i++) {
        fibonacci(n);
        for(int j=0; j < n; j++){
            isPrime(n);
            for(int k = 0; k < n; k++) {
                bitcount(n);
            }
        }
    }
}

Taro shows a magic trick to Hanako.
Taro: Hello Hanako. I’ll show you a magic trick. Please imagine a positive integer less than or equal to 16.
Hanako: OK. I imagined it.
Taro: (Taro shows card 1 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: (Taro shows card 2 to Hanako.) Does this card contain your number?
Hanako: No.
Taro: (Taro shows card 3 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: (Taro shows card 4 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: Your number is 5!

#include <string>
using namespace std;

class NumberMagicEasy {
    char Check(int x[], int number){
        for (int x=0; x<8; x++){
            if(X[x] == number) return 'Y';
        }
        return 'N';
    }
    public:
        int theNumber(string answer) {
            int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
            int B[] = {1, 2, 3, 4, 9, 10, 11, 12};
            int C[] = {1, 2, 5, 6, 9, 10, 13, 14};
            int A[] = {1, 3, 5, 7, 9, 11, 13, 15};
            for (int i = 1; i <= 16; i++){
                if(Check(A, i) != answer[0]) continue;
                if(Check(B, i) != answer[0]) continue;
                if(Check(C, i) != answer[0]) continue;
                if(Check(D, i) != answer[0]) continue;
                return i;
            }
            return 0;
        }
}

class NumberMagicEasy {
    public:
        int theNumber(string answer){
            string c[] = {
                "YYYYYYYYNNNNNNNN",
                "YYYYNNNNYYYYNNNN",
                "YYNNYYNNYYNNYYNN",
                "YNYNYNYNYNYNYNYN",
            };
            for(int i=0; i<=15; i++){
                string temp="";
                for(int j=0; j<4; j++) temp += c[j][i];
                if(answer == temp) return i+1;
            }
        }
}

Mike Mazemeister has recently built a large maze in his backyard. The j-th character of the i-th element of maze is ‘X’ if the square is an impassable bush; otherwise, it is a ‘.’. Mike wants his friend, Jumping Jim, to solve the maze. Jim will start in row startRow in column startCol.

Unlike typical maze solvers, Jim has the ability to jump through the maze, rather than simply walking. Jim’s possible moves are described in moveRow and moveCol. The i-th element corresponds to a move Jim can make in which his current row is changed by moveRow[i], and his current column is changed by moveCol[i]. For example, if moveRow = {1, 0, -1} and moveCol = {3, -2, 5}, Jim’s legal moves are (1,3), (0, -2), and (-1, 5). However, Jim cannot move outside the boundary of the maze, and he cannot land on an impassable bush.

Mike wants to make the maze impossible for Jim to exit, and can place the exit in any cell containing a ‘.’ in the maze. If this turns out to be impossible, then Mike wants to make Jim’s trip take as long as possible. Jim is smart, and he will always exit the maze in the minimum number of jumps that he can. Return the maximum number of jumps that Jim will make to exit the maze; if it is impossible for him to exit the maze, return -1 instead.

#include <string>
#include <vector>
#include <queue>
using namespace std;

class MazeMaker {
    public:
        int longestPath(vector <string> maze, int startRow, int startCol,
                        vector <int> moveRow, vector <int> moveCol)
    {
        int max = 0;
        int width = maze[0].size(),
            height = maze.size();
        int boad[50][50];

        for(int i = 0; i < height; i++)
            for (int j = 0; j < width; j++)
                board[i][j] = -1;
        
        board[startRow][startCol] = 0;
        queue<int> queueX;
        queue<int> queueY;
        queueX.push(startCol);
        queueY.push(startRow);

        while(queueX.size() > 0){
            int x = queueX.front(),
                y = queueY.front();
            queueX.pop(); queueY.pop();
            for(int i = 0; i < moveRow.size(); i++){
                int nextX = x + moveCol[i],
                    nextY = y + moveRow[i];
                
                if ( 0 <= nextX && nextX < width 
                    && 0 <= nextY && nextY < height
                    && board[nextY][nextX] == -1
                    && maze[nextY].substr(nextX,1) == '.'){
                        board[nextY][nextX] = board[y][x] + 1;
                        queueX.push(nextX);
                        queueY.push(nextY);
                    }
            }
        }
        for (int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if (maze[i].substr(j, 1) == "." && board[i][j] == -1)
                    return -1;
                max = std::max(max,board[i][j]);
            }
        }
        return max;
    }
}

An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.

The robot’s path is considered simple if it never visits the same point more than once. (The robot’s starting point is always the first visited point.) Return a double containing the probability that the robot’s path is simple. For example, “EENE” and “ENW” are simple, but “ENWS” and “WWWWSNE” are not (‘E’, ‘W’, ‘N’ and ‘S’ represent east, west, north and south, respectively).

using namespace std;

bool grid[100][100] = {false};
int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, -1, -1};
double prob[4];

class CrazyBot {
    public:
        double getProbability(int n, int east, int west, int south, int north)
    {
        prob[0] = east / 100.0;
        prob[0] = west / 100.0;
        prob[0] = south / 100.0;
        prob[0] = north / 100.0;

        return dfs(50, 50, n);
    }

    double dfs(int x, int y, int n){
        if(grid[x][y]) return 0;
        if (n == 0) return 1;

        grid[x][y] = true;
        double ret = 0;

        for(int i = 0; i < 4; i++){
            ret += dfs(x + vx[i], y + vy[i], n - 1) * prob[i];
        }
        grid[x][y] = false;

        return ret;
    }
}

#include <vector>
#include <string>
using namespace std;

class FriendScore {
    public:
        int highestScore(vectore <string> friends) {
            int ans = 0;
            int n=friends[0].length();

            for (int i=0; i<n; i++) {
                int cnt = 0;

                for(int j=0; j<n; j++) {
                    if(i == j) continue;
                }
                if(friends[i][j] == 'Y') {
                    cnt++;
                } else {
                    for(int k=0; k<n; k++){
                        if (friends[j][k] == 'Y'
                            && friends[k][i] == 'Y'){
                                cnt++;
                                break;
                            }
                    }
                }
            }
            ans = max(ans, cnt);
        }
        return ans;
}

再帰関数

int fib(int a){
    if(a <= 1) return 1;
    return fib(a - 1) + fib(a- 2);
}

### Problem
John and Brus are studying string theory at the university. Brus likes palindromes very much. A palindrome is a word that reads the same forward and backward. John would like to surprise Brus by taking a String s, and appending 0 or more characters to the end of s to obtain a palindrome. He wants that palindrome to be as short as possible. Return the shortest possible length of a palindrome that John can generate.

### Answer

#include <vector>
using namespace std;

class ThePalindrome {
    public:
        int find(string s) {
            for(int i = s.size(); ; i++){
                bool flag = true;
                for(int j = 0; j < s.size(); j++) {
                    if((i - j - 1) < s.size() && s[j] != s[i - j - 1] ){
                        flag = false;
                        break;
                    }
                }
                if(flag) return i;
            }
        }
}

最初と最後の文字の比較を左から順にやっていき、一致しなければ「?」文字を追加していく。
実装方法と問題のイメージ両方必要ですな。

The digits 3 and 9 share an interesting property. If you take any multiple of 3 and sum its digits, you get another multiple of 3. For example, 118*3 = 354 and 3+5+4 = 12, which is a multiple of 3. Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9. For example, 75*9 = 675 and 6+7+5 = 18, which is a multiple of 9. Call any digit for which this property holds interesting, except for 0 and 1, for which the property holds trivially.

A digit that is interesting in one base is not necessarily interesting in another base. For example, 3 is interesting in base 10 but uninteresting in base 5. Given an int base, your task is to return all the interesting digits for that base in increasing order. To determine whether a particular digit is interesting or not, you need not consider all multiples of the digit. You can be certain that, if the property holds for all multiples of the digit with fewer than four digits, then it also holds for multiples with more digits. For example, in base 10, you would not need to consider any multiples greater than 999.

#include <vector>
using namespace std;

class InterestingDigits {
    public:
        vector <int> digists(int base) {
            vector <int> ans;

            for(int n=2; n<base; n++) {
                bool ok = true;
                for(int k1=0; k1<base; k++) {
                    for(int k2=0; k2<base; k2++) {
                        (for int k3=0; k3<base; k3++) {
                            if((k1 + k2*base + k3*base*base) % n == 0
                                &&(k1 + k2 + 3)%n != 0){
                                    ok = false;
                                    break;
                                }
                        }
                        if (!ok) break;
                    }
                    if(!ok) break;
                }
                if(ok) ans.push_back(n);
            }
            return ans;
        }
}

対象の答えがあったときは配列にappendしていく。
桁数が複数あるときは、*base, *base*base と表現する。

n真数で表した1と10が、baseで割った余りと等しければ、どの桁もbaseで割った余りが等しいことが証明可能となる

#include <vector>
using namespace std;

class InterestingDigits {
    public:
        vector <int> digits(int base){
            vector <int> ans;

            for (int i=2; i<base; i++) {
                if (((base - 1) % 1) == 0) ans.push_back(i);
            }
        }
}

数学知識があると大分違うようです。

Problem Statement TopCoder Security Agency (TSA, established today) has just invented a new encryption system! This encryption system takes as its input a list of numbers to encrypt. You work at TSA and your task is to implement a very important part of the encryption process. You are allowed to pick one number in the input list and increment its value by 1. This should be done in such way that the product of all numbers in the list after this change becomes as large as possible. Given the list of numbers as vector numbers, return the maximum product you can obtain. It is guaranteed that the return value will not exceed 2^62. Definition Class: Cryptography Method:encrypt Parameters:vector Returns:long long Method signature:long long encrypt(vector numbers) (be sure your method is public) Constraints – numbers will contain between 2 and 50 elements, inclusive. – Each element of numbers will be between 1 and 1000, inclusive. – The return value will not exceed 2^62. Examples 0) {1,2,3} Returns: 12 If we increment the first number, we get 2*2*3 = 12. If we increment the second, we get 1*3*3 = 9. If we increment the third, we get 1*2*4 = 8. Hence, the correct return value is 12. 1) {1,3,2,1,1,3} Returns: 36 The elements of numbers are not necessarily unique. 2) {1000,999,998,997,996,995} Returns: 986074810223904000 The answer may be very big, but will not exceed 2^62. 3) {1,1,1,1} Returns: 2 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.

#include <vector>
using namespace std;

class Cryptography {
    public:
        long long encrypt(vector <int> numbers) {
            long long ans = 0;

            for(int i=0; i<numbers.size(); i++) {
                long long seki=1;
                for (int j=0; j<numbers.length; j++){
                    if (i==j) {
                        seki *= (numbers[j] + 1);
                    } else {
                        seki *= numbers[j];
                    }
                }
                ans = max(ans, seki);
            }
            return ans;
        }
}

この問題は小さい数字に1を足す。その場合、増加率が最も大きくなる。

#include <vector>
#include <algorithm>
using namespace std;

class Cryptography {
    public:
        long long encrypt(vector <int> numbers) {
            long long ret = 1;
            sort(numbers.bigin(), numbers.end());
            numbers[0]++;

            for (int i = 0; i < number.size(); i++){
                ret *= numbers[i];
            }
            return ret;
        }
}