Category: algorithm

There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.

John plans to travel through the country using the following rules:
He must start in one city and end in another city after travelling exactly N-1 roads.
He must visit each city exactly once.
You are given a String[] roads. If the j-th character of the i-th element of roads is ‘Y’, he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.

Return the number of paths he can choose, modulo 1,000,000,007.

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

bool visited[50] = {false};

class HamiltonPath {
    public:
        vector <string> roads;

        int countPaths(vector <string> roads){
            int group=0, free=0;
            int connect[50] = {0};

            long long sum = 1;

            this->roads = roads;

            for(int i=0; i<roads.size(); i++){
                int y = 0;
                for(int j=0; j<roads[i].size(); j++){
                    if(roads[i].substr(j, 1) == "Y"){
                        if( 2 < ++y) return 0;
                    }
                }
                connect[i] = y;
            }

            for (int i = 0; i<roads.size(); i++){
                if(connect[i]==0){
                    visited[i] = true;
                    free++;
                } else if(connect[i] == 1 && !visited[i]){
                    group++;
                    dfs(i);
                }
            }
            for (int i=0; i<roads.size(); i++)
                if(!visited[i]) return 0;
            for (int i=0; i<group+free; i++)
                sum = sum * (i+1) % 100000007;
            for (int i=0; i<group; i++)
                sum = sum * 2 % 100000007;
            return (int)sum;
        }

        void dfs(int city){
            visited[city] = true;
            for(int i=0; i < roads[city].size(); i++){
                if(road[city].substr(i, 1) == "Y" && !visited[i]) dfs(i);
            }
        }
};

Circles Country is a country that contains several circular-shaped districts. Some districts may be situated inside other districts, but their borders do not intersect or touch. Qatam is a resident of Circles Country. When he travels between two locations, he always tries to cross the fewest number of district borders as possible because crossing borders is usually a laborious task.

Imagine Circles Country as an infinite plane. You are given int[]s X, Y and R, where (X[i], Y[i]) are the coordinates of the i-th district’s center and R[i] is its radius. Qatam is currently at point (x1,y1) and he needs to get to point (x2,y2). Neither of these points lies on a district border. Return the minimal number of district borders he must cross to get to his destination.

#include <vector>
using namespace std;

class CirclesCountry {
    public:
        int leastBorders(vector <int> X, vector <int> Y, vector <int>R, int x1, int y1, int x2, int y2){
            int num = 0;

            for (int i = 0; i < X.size(); i++){
                if (inside(X[i], Y[i], x1, y1, R[i]) != (inside(X[i], Y[i], x2, y2, R[i])))
                    num++;
            }

            bool inside(int x1, int y1, int x2, int y2, int r){
                return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r * r;
            }
        }
};

(x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2) <= r * r;が x1y1とx2y2で正しくなければ境界線が1つとなる。すなわち、insideでは片方が円の中にあり、片方が円の外に点があるかどうかを判定している。コーディングというより問題の理解力の方が求められるか...

Auto dealerships frequently advertise tempting loan offers in order to make it easier for people to afford the “car of their dreams”. A typical sales tactic is to show you various cars, and then talk in terms of what your monthly payment would be, to say nothing of how much you are actually paying for the car, how much interest you pay, or how long you have to make payments.

A typical auto loan is calculated using a fixed interest rate, and is set up so that you make the same monthly payment for a set period of time in order to fully pay off the balance. The balance of your loan starts out as the sticker price of the car. Each month, the monthly interest is added to your balance, and the amount of your payment is subtracted from your balance. (The payment is subtracted after the interest is added.) The monthly interest rate is 1/12 of the yearly interest rate. Thus, if your annual percentage rate is 12%, then 1% of the remaining balance would be charged as interest each month.

You have been checking out some of the cars at your local dealership, TopAuto. An excited salesman has just approached you, shouting about how you can have the car you are looking at for a payment of only monthlyPayment for only loanTerm months! You are to return a double indicating the annual percentage rate of the loan, assuming that the initial balance of the loan is price.

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

class AutoLoan {
    double interestRate(double price, double monthlyPayment, int loanTerm){
        double balance;
        double high = 100, low = 0, mid = 0;

        while((1e-9 < high - low) && (1e-9 < (high -low)/high)){
            balance = price;
            mid = (high + low) / 2;

            for (int j=0; j<loanTerm; j++){
                balance *= mid / 1200 + 1;
                balance -= monthyPayment;
            }
            if (0 < balance) high = mid;
            else low = mid;
        }
        return mid;
    }
}

mid = (high + low) / 2; としてから、highとlowの差が限りなく小さくなるまでwhileで繰り返し処理を行う。
1e-2は0.01で、1e-9は0.000000001
“1e-n”という表現は覚えておいて損はなさそう

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

class BachSystem {
    public:
        vector <int> schedule(vector<int> duration, vector <string> user){
            int N = duration.size();

            map<string, long long> jobTime;
            for(int n=0; n<N; n++) jobTime[user[n]] += duration[n];

            vector<bool> done(N);
            vector<int> ans;
            while(ans.size() < N) {
                string next;
                for(int n=0; n<N; n++){
                    if(!done[n] && (next.empty() || jobTime[user[n]] < jobTime[next]))
                        next = user[n];
                }

                for(int n=0; n<N; n++){
                    if(user[n] == next){
                        done[n] = true;
                        ans.push_back(n);
                    }
                }
            }
            return ans;
        }
}

empty()は空かどうか。
done[N]はNが1以降にならないとtrueにならない。

You have recently been given a one-time bonus at work, along with a pay raise. In the interest of putting your new found money to good use, you have decided to invest in the stock market. To learn about recent market history, you have acquired historical data on several stocks you might be interested in purchasing.

For experiment’s sake, you want to evaluate the potential performance of your selected stocks. What you are wondering is how much money you could have made if, at the beginning, you had an initial investment of int initialInvestment dollars, and each month thereafter you had an additional int monthlyContribution dollars. Assume that you may buy any number of shares of stocks at the beginning of each month (including fractional numbers of shares), and that at the end of the timeframe (at the beginning of the last month) represented in the data, you sell all of your holdings. You may not sell stocks in the intermediate period. (See examples for clarification.)

You are given a String[], stockPrices, in which each element lists the prices of each stock at the beginning of a month. Each element of stockPrices is in the form “stock0 stock1 …” (quotes added for clarity), where each stocki is a positive integer with no leading zeroes. The first element of stockPrices gives the initial prices, the second element gives the prices at the beginning of the first month after you start investing, and so on.

You are to return an int indicating the maximum earnings (profit) you could make by the end of the timeframe. You should round your result to the nearest integer.

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

class StockHistory {
    public:
        int maximumEarnings(int initialInvestment, int monthlyContribution, vector <string> stockPrices){
            int money = initialInvestment;
            int month = stockPrices.size();
            int corp = 1:
            char *s = (char *)stockPrices[0].c_str();
            while(*s++) if(*s==' ') corp++;

            int prices[50][999];
            double max = 0; profit = 0;
            double proportion[50] = {0};
            bool buy[50] = {false};

            for(int i = 0; i < month; i++){
                string s = stockPrices[i];
                for(int j = 0; j < corp; j++){
                    int pos=s.find(" ");
                    if(pos == string::npos){
                        prices[i][j] = atoi(s.c_str());
                    } else {
                        prices[i][j] = atoi(s.substr(0, pos).c_str());
                        s = s.substr(pos+1, s.size());
                    }
                }
            }

            for(int i = month - 2; 0 <= i; i--){
                for(int j = 0; j < corp; j++){
                    double p = 1.0 * prices[month - 1][j] / prices[i][j] - 1;
                    if(0 < p && max < p) {
                        buy[i] = true;
                        max = p;
                        proportion[i] = p;
                    }
                    for(int i = 0; i < month; i++){
                        if(buy[i]){
                            profit += money * proportion[i];
                            money = 0;
                        }
                        money += monthlyContribution;
                    }
                    return (int)Math.round(profit);
                }
            }
        }
}

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