ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

#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]);
            }

            fo (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;
        }
}

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;
            }
        }
}