LoginSignup
19
20

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@rsahara(Runo Sahara)

Codilityで練習

Last updated at Posted at 2020-02-18

練習問題が複数あって面白い。
得意なC++とSwiftでやってみた（やっている）。
新しく習った言語をマスターするために良さそうなのと、英語の勉強にもなる。

Lesson 1: Iterations

BinaryGap (painless)

2進数で表現した整数Nの、一番長い、1に囲まれた連続0の最大の長さを求める。

例
N = 9 // 1001
  -> 2
N = 529 // 1000010001
  -> 4
N = 20 // 10100
  -> 1   
N = 15 // 1111
  -> 0
  • Nの範囲は[1..2,147,483,647]とする。

回答例

C++
int solution(int N) {
    int result = 0;
    int count = -1;
    for (; N != 0; N >>= 1) {
        if ((N & 1) != 0) {
            if (result < count) {
                result = count;
            }
            count = 0;
        }
        else if (count != -1) {
            count++;
        }
    }
    return result;
}
Swift4
public func solution(_ N : Int) -> Int {
    var remain = N
    var result = 0
    var count = -1
    while remain != 0 {
        if (remain & 1) != 0 {
            if result < count {
                result = count
            }
            count = 0
        } else if count != -1 {
            count += 1
        }
        remain >>= 1
    }
    return result
}

最下位の桁を処理して次の桁に進む。

C++、無駄なチェック排除
int solution(int N) {
    if (N == 0) {
        return 0;
    }
    for (; (N & 1) == 0; N >>= 1);
    do { N >>= 1; } while ((N & 1) != 0);
    int result = 0;
    while (N != 0) {
        int count = 0;
        for (; (N & 1) == 0; N >>= 1) {
            count++;
        }
        if (result < count) {
            result = count;
        }
        do { N >>= 1; } while ((N & 1) != 0);
    }
    return result;
}

意味はないが初回かのチェック（count != -1）を無くす。

桁を一つずつ1回列挙、処理時間は桁数に比例。
使用するメモリの量は固定。

Lesson 2: Arrays

CyclicRotation (painless)

整数の配列Aに要素がN個あるとする。
この配列の要素を右にK回ローテーションする。
ローテーションした後の配列を求める。

例
A = [3, 8, 9, 7, 6], K = 3
  -> [9, 7, 6, 3, 8]
A = [0, 0, 0], K = 1
  -> [0, 0, 0]
A = [1, 2, 3, 4], K = 4
  -> [1, 2, 3, 4]
  • NとKの範囲は[0..100]とする。
  • Aの要素は[−1,000..1,000]の範囲内の整数とする。

回答例

C++
vector<int> solution(vector<int> &A, int K) {
    if (A.empty()) {
        return vector<int>();
    }
    auto cutIterator = A.end() - K % A.size();
    vector<int> result;
    result.reserve(A.size());
    result.insert(result.end(), cutIterator, A.end());
    result.insert(result.end(), A.begin(), cutIterator);
    return result;
}
Swift4
public func solution(_ A : inout [Int], _ K : Int) -> [Int] {
    guard !A.isEmpty else { return [] }
    let cutIndex = A.count - K % A.count
    var result = [Int](A[cutIndex ..< A.count])
    result.append(contentsOf: A[0 ..< cutIndex])
    return result
}

ローテーション後の位置を計算して、配列を再構築。

配列Aの要素を1回列挙（コピー）し、処理時間はNに比例。
使用するメモリの量もNに比例。

OddOccurrencesInArray (painless)

整数の配列Aに要素がN個あるとする。
この配列は奇数の数の要素を持ち、要素は1つを除き全てペアが存在する。
ペアが存在しない要素を求める。

例
A = [9, 3, 9, 3, 9, 7, 9]
  -> 7
  • Nは[1..1,000,000]の範囲の奇数とする。
  • Aの要素は[1..1,000,000,000]の範囲内の整数とする。

回答例1（ハッシュテーブル）

C++
#include <unordered_set>

int solution(vector<int> &A) {
    unordered_set<int> needPair;
    for (auto value: A) {
        auto it = needPair.find(value);
        if (it == needPair.end()) {
            needPair.emplace(value);
        }
        else {
            needPair.erase(it);
        }
    }
    return *needPair.begin();
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    var needPair = Set<Int>()
    for value in A {
        if needPair.contains(value) {
            needPair.remove(value)
        }
        else {
            needPair.insert(value)
        }
    }
    return needPair.first!
}

ハッシュテーブルを使ってペアの有無を確認する。

配列Aを1回列挙し、処理時間がNに比例。
使用するメモリはハッシュテーブルのみでNに比例。

回答例2（XORで算出）

C++
int solution(vector<int> &A) {
    int result = 0;
    for (auto value: A) {
        result ^= value;
    }
    return result;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    return A.reduce(0) { x, y in x ^ y }
}

x XOR xすると0になるため、全部XORすれば仲間はずれが残る。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量は固定。

Lesson 3: Time Complexity

FrogJmp (painless)

カエルが道を渡ろうとしている。現在位置をX、目的地の位置をYとする。
カエルが1回のジャンプで移動できるのは固定距離Dとする。

カエルが目的地にたどり着くために必要なジャンプの回数を求める。

例
X = 10, Y = 85, D = 30
    -> 3
  • X, Y, D の範囲は[1..1,000,000,000]とする。
  • X <= Y とする。

回答例

C++
int solution(int X, int Y, int D) {
    int delta = Y - X;
    return delta / D + (delta % D == 0 ? 0 : 1);
}
Swift4
public func solution(_ X : Int, _ Y : Int, _ D : Int) -> Int {
    let delta = Y - X
    return delta / D + (delta % D == 0 ? 0 : 1)
}

処理時間と使用するメモリの量は固定。

PermMissingElem (painless)

整数の配列Aに異なる要素がN個あるとする。
その配列の要素は全て[1..(N + 1)]の範囲の整数で、配列に含まれていない整数が1つだけある。
配列に無い整数を求める。

例
A = [2, 3, 1, 5]
    -> 4
  • Nは[0..100,000]の範囲内の整数とする。
  • Aの要素は全て異なる値とする。
  • 配列の要素は[1..(N + 1)]の範囲内の整数とする。

回答例1（フラグの配列）

C++
#include <algorithm>

int solution(vector<int> &A) {
    vector<bool> found(A.size() + 2, false);
    for (auto value: A) {
        found[value] = true;
    }
    auto it = find(found.begin() + 1, found.end(), false);
    return it - found.begin();
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    var found = Array<Bool>(repeating: false, count: A.count + 2)
    for value in A {
        found[value] = true
    }
    return found.lastIndex { $0 == false }!
}

フラグの配列で抜けているものを探す。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量はNに比例。

回答例2（算出）

C++
int solution(vector<int> &A) {
    long long result = A.size();
    result = (result + 1) * (result + 2) / 2;
    for (auto value: A) {
        result -= value;
    }
    return result;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    return A.reduce((A.count + 1) * (A.count + 2) / 2) { x, y in x - y }
}

1 + ... + N は N * (N + 1) / 2である。
そこから算出する。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量は固定。

TapeEquilibrium (painless)

N個の要素を持つ配列Aがあるとする。配列Aはテープ上の整数を表す。
任意の整数Pでテープを2つのパートに分けることができる：A[0] ... A[P-1]とA[P] ... A[N-1]。
2つのパートの 差（difference） を次のように定義する：| (A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1]) |（2つのパートの和の差の絶対値）。

配列Aにおいて、この 差 の最小値を求める。

例
A = [3, 1, 2, 4, 3]
    -> 1

理由：
P = 1, 差 = |3 − 10| = 7
P = 2, 差 = |4 − 9| = 5
P = 3, 差 = |6 − 7| = 1
P = 4, 差 = |10 − 3| = 7
  • Nの範囲は[2..100,000]とする。
  • 配列Aの要素は、[−1,000..1,000]の範囲の整数とする。

回答例

C++
#include <limits>

int solution(vector<int> &A) {
    int totalSum = 0;
    for (auto value: A) {
        totalSum += value;
    }
    int result = numeric_limits<int>::max();
    int currentSum = 0;
    auto end = A.end() - 1;
    for (auto it = A.begin(); it != end; it++) {
        currentSum += *it;
        int testValue = currentSum - (totalSum - currentSum);
        testValue = testValue < 0 ? -testValue : testValue;
        if (result > testValue) {
            result = testValue;
        }
    }
    return result;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    let totalSum = A.reduce(0) { x, y in x + y }
    return A[0 ..< A.count - 1].reduce ((0, Int.max)) { prev, value in
        let (prevSum, prevResult) = prev
        let newSum = prevSum + value
        let testValue = abs(newSum - (totalSum - newSum))
        return (newSum, prevResult > testValue ? testValue : prevResult)
    }.1
}

全体の和 - 片方のパートの和 = もう片方のパートの和。

配列Aを2回列挙し、処理時間はNに比例。
使用するメモリの量は固定。

Lesson 4: Counting Elements

Reading material には、配列に含まれた値の数を、ハッシュテーブル（または別の配列）に保存して数える方法が記述されている。
固定時間の処理で、値の出現回数が確認できるようになる。

FrogRiverOne (painless)

カエルが川を渡りたがっている。カエルの位置を0、川の反対側の位置をX+1とする。
川の水面に葉っぱが落ちてくる。

配列Aに要素がN個あるとする。A[K]は経過時間Kに落ちてくる葉っぱの位置を表す。
カエルが川を渡れるのは、位置1からXまで、葉っぱが埋まった時である。

カエルが川を渡れる一番早い時間を求める。渡ることができない場合は-1を返す。

例
A = [1, 3, 1, 4, 2, 3, 5, 4], X = 5
    -> 6
  • NとYの範囲は[1..100,000]とする。
  • 配列Aの要素は[1..X]の範囲の整数とする。

回答例

C++
int solution(int X, vector<int> &A) {
    vector<bool> hasLeaf(X + 1, false);
    int leavesNeeded = X;
    for (auto it = A.begin(); it != A.end(); it++) {
        int leaf = *it;
        if (leaf <= X && !hasLeaf[leaf]) {
            hasLeaf[leaf] = true;
            leavesNeeded--;
            if (leavesNeeded == 0) {
                return it - A.begin();
            }
        }
    }
    return -1;
}
Swift4
public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    var hasLeaf = Array<Bool>(repeating: false, count: X + 1)
    var leavesNeeded = X
    for (index, leaf) in A.enumerated() {
        guard leaf <= X, !hasLeaf[leaf] else { continue }
        hasLeaf[leaf] = true
        leavesNeeded -= 1
        if leavesNeeded == 0 {
            return index
        }
    }
    return -1
}

葉っぱの有無を表す一時配列を用意し、道を作るのに必要な葉っぱの数をカウントダウン。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量もNに比例。

PermCheck (painless)

N個の要素を持つ配列Aがあるとする。
1からNまでの整数を1個だけもつ配列を 順列（permutation） と呼ぶ。

配列Aが 順列 かどうかを求める。
順列 の場合は1を返し、そうでない場合は0を返す。

例
A = [4, 1, 3, 2]
    -> 1
A = [4, 1, 3]
    -> 0
  • Nの範囲は[1..100,000]とする。
  • 配列Aの整数は[1..1,000,000,000]の範囲の整数とする。

回答例

C++
int solution(vector<int> &A) {
    vector<bool> found(A.size() + 1, false);
    long long remain = A.size();
    remain = remain * (remain + 1) / 2;
    for (auto value: A) {
        if (value > A.size() || found[value]) {
            return 0;
        }
        remain -= value;
        if (remain <= 0) {
            break;
        }
        found[value] = true;
    }
    return remain == 0 ? 1 : 0;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    var found = Array<Bool>(repeating: false, count: A.count + 1)
    var remain = A.count * (A.count + 1) / 2
    for value in A {
        guard value <= A.count, !found[value] else { return 0 }
        remain -= value
        guard remain >= 0 else { break }
        found[value] = true
    }
    return remain == 0 ? 1 : 0
}

要素が1回だけ出現するかをフラグの配列で確認。
全ての値が揃っていることを確認をするため、全要素の和（1 + ... + N）がN * (N + 1) / 2になっているかを確認。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量もNに比例。

MissingInteger (respectable)

配列Aに整数がN個あるとする。
配列Aに含まれていない、一番小さい、0を超える整数を求める。

例
A = [1, 3, 6, 4, 1, 2]
    -> 5
A = [1, 2, 3]
    -> 4
A = [-1, -3]
    -> 1
  • Nの範囲は[1..100,000]とする。
  • 配列Aの要素は[−1,000,000..1,000,000]の範囲の整数とする。

回答例

C++
#include <algorithm>

int solution(vector<int> &A) {
    vector<bool> found(A.size() + 1, false);
    for (auto value: A) {
        if (value > 0 && value < found.size()) {
            found[value] = true;
        }
    }
    auto it = find(found.begin() + 1, found.end(), false);
    return it - found.begin();
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    var found = [Bool](repeating: false, count: A.count + 1)
    for value in A {
        guard value > 0, value < found.count else { continue }
        found[value] = true
    }
    return found.dropFirst().firstIndex { $0 == false } ?? (A.count + 1)
}

答えの範囲は[1..N+1]に入る。
この範囲で出現する値をフラグの配列に保存し、出現しない一番低い数字を求める。

配列Aを1回列挙し、検索する際同じ大きさの配列をもう1回列挙。
処理時間はNに比例。使用するメモリの量もNに比例。

MaxCounters (respectable)

初期値が0のカウンターがN個あるとする。
カウンターには、次のオペレーションが存在する。

  • increase(X)：カウンターXを1インクリメントする。
  • max counter：全てのカウンターを、現在のカウンターの最大値に設定する。

これらのオペレーションを表す、M個の整数を含む配列Aがあるとする。

  • A[K] = X（ただし 1 <= X <= N）の場合、オペレーションKは increase(X) を表す。
  • A[K] = N+1の場合、オペレーションKは max counter を表す。

全てのオペレーションを実行した後のカウンターを求める。

例
A = [3, 4, 4, 6, 1, 4, 4]
    -> [3, 2, 2, 4, 2]

各オペレーション後のカウンターの状態：
    [0, 0, 1, 0, 0]
    [0, 0, 1, 1, 0]
    [0, 0, 1, 2, 0]
    [2, 2, 2, 2, 2]
    [3, 2, 2, 2, 2]
    [3, 2, 2, 3, 2]
    [3, 2, 2, 4, 2]
  • NとMの範囲は[1..100,000]とする。
  • 配列Aはの要素は[1..N + 1]の範囲の整数とする。

回答例

C++
#include <unordered_map>

vector<int> solution(int N, vector<int> &A) {
    int maxCounterOperation = N + 1;
    unordered_map<int, int> counters;
    int currentMaxValue = 0;
    int maxCounterValue = 0;
    for (auto value: A) {
        if (value == maxCounterOperation) {
            counters.clear();
            maxCounterValue = currentMaxValue;
        }
        else {
            auto it = counters.find(value);
            int newValue;
            if (it == counters.end()) {
                newValue = maxCounterValue + 1;
                counters[value] = newValue;
            }
            else {
                newValue = it->second + 1;
                it->second = newValue;
            }
            if (currentMaxValue < newValue) {
                currentMaxValue = newValue;
            }
        }
    }
    vector<int> result;
    result.reserve(N);
    for (int counter = 1; counter <= N; counter++) {
        auto it = counters.find(counter);
        if (it == counters.end()) {
            result.emplace_back(maxCounterValue);
        }
        else {
            result.emplace_back(it->second);
        }
    }
    return result;
}
Swift4
public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    let maxCounterOperation = N + 1
    var currentMax = 0
    var counters = [Int: Int]()
    var lastMaxCounterValue = 0
    for value in A {
        if value == maxCounterOperation {
            lastMaxCounterValue = currentMax
            counters = [Int: Int]()
        }
        else {
            let newCounterValue = (counters[value] ?? lastMaxCounterValue) + 1
            counters[value] = newCounterValue
            if currentMax < newCounterValue {
                currentMax = newCounterValue
            }
        }
    }
    return (1 ... N).map { counter in counters[counter] ?? lastMaxCounterValue }
}

最後の max counter オペレーションで全カウンター同じ値になるため、最後の max counter オペレーション時からの差分カウンターを管理する。
max counter オペレーション時、差分カウンターのクリアを固定時間で行う。

配列Aは1回列挙し、1カウンターの結果の計算は固定時間で行えるが、カウンターごとN回行う。
処理時間はNに比例し、使用するメモリはNに比例。

Lesson 5: Prefix Sums

Reading material には、 prefix sums という配列について記述されている。
Prefix sumsを使うと、配列の一部分の要素の合計を固定時間で計算できるようになる。

Prefix sums配列はリニア時間で作成でき、内容は、気になる値の、各インデックスごとの累計値の配列。
配列の任意範囲の合計は、その範囲の始点と終点のPrefix sumsの差分で算出できる。

PassingCars (painless)

整数N個の配列Aがあるとする。この配列は道路を走る車を表し、0か1しか含まない。

  • 0は東（east）に向かう車を表す。
  • 1は西（west）に向かう車を表す。

車のペア (P, Q)　（0 <= P < Q < Nとして） は、Pが東へ向かいQが西へ向かう場合、 すれ違う（passing） という。
すれ違う車の数を求める。
その数が1,000,000,000を超える場合は-1を返す。

例
A = [0, 1, 0, 1, 1]
    -> 5

すれ違う車は次のペアになる：(0, 1), (0, 3), (0, 4), (2, 3), (2, 4)
  • Nの範囲は[1..100,000]とする。
  • Aの要素は全て0か1とする。

回答例

C++
int solution(vector<int> &A) {
    int passingCount = 0;
    int currentEastCount = 0;
    for (auto value: A) {
        if (value == 0) {
            currentEastCount++;
        }
        else {
            passingCount += currentEastCount;
            if (passingCount > 1000000000) {
                return -1;
            }
        }
    }
    return passingCount;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    var passingCount = 0
    var currentEastCount = 0
    for value in A {
        if value == 0 {
            currentEastCount += 1
        }
        else {
            passingCount += currentEastCount
            if passingCount > 1_000_000_000 {
                return -1
            }
        }
    }
    return passingCount
}

西に向かう車を見つける度にその時点で交差する東に向かう車を加算。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量は固定。

GenomicRangeQuery (respectable)

DNAのシーケンスは各ヌクレオチドである 'A', 'C', 'G', 'T' を含む文字列で表すことができる。
それぞれのヌクレオチドには インパクトファクター（impact factor） があり、それを整数で表せる。

各ヌクレオチド'A', 'C', 'G', 'T'のインパクトファクターはそれぞれ1, 2, 3, 4とする。
特定のDNAシーケンスに対し、それを構成するヌクレオチドの最も小さいインパクトファクターを求める。

長さNのDNAシーケンスを表す文字列S、M個のクエリを表す配列Pと配列Qがあるとする。
K個目のクエリ（0 <= K < Mとする）は、DNAシーケンスのP[K]からQ[K]までのヌクレオチドの最も小さいインパクトファクターを求めることとなる。

例
S = "CAGCCTA", P = [2, 5, 0], Q = [4, 5, 6]
    -> [2, 4, 1]

2から4番目のヌクレオチドは'G'と'C'であるが、インパクトファクターは3と2であり、最小値は2となる。
5から5番目のヌクレオチドは'T'であるため、インパクトファクターは4となる。
0から6番目のヌクレオチドは全ヌクレオチドを含むが、'A'のインパクトファクターが1であり、最小値である。
  • Nの範囲は[1..100,000]とする。
  • Mの範囲は[1..50,000]とする。
  • 配列Pと配列Qの要素は[0..N − 1]の範囲の整数とする。
  • P[K] <= Q[K] とする（0 <= K < M）。
  • 文字列Sの文字は'A', 'C', 'G', 'T'とする。

回答例

C++
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    int prefixes[(S.size() + 1) * 4];
    int dnaValues[256];
    dnaValues['A'] = 0;
    dnaValues['C'] = 1;
    dnaValues['G'] = 2;
    dnaValues['T'] = 3;
    
    for (int index = 0; index < 4; index++) {
        prefixes[index] = 0;
    }
    int* currentPrefix = prefixes + 4;
    for (int dnaChar: S) {
        int dnaValue = dnaValues[dnaChar];
        int* prevPrefix = currentPrefix - 4;
        for (int index = 0; index < 4; index++) {
            currentPrefix[index] = prevPrefix[index];
        }
        currentPrefix[dnaValue]++;
        currentPrefix += 4;
    }
    
    vector<int> result;
    for (int index = 0; index < P.size(); index++) {
        int* startPrefix = prefixes + P[index] * 4;
        int* endPrefix = prefixes + (Q[index] + 1) * 4;
        for (int dnaValue = 0; dnaValue < 4; dnaValue++) {
            if (startPrefix[dnaValue] != endPrefix[dnaValue]) {
                result.emplace_back(dnaValue + 1);
                break;
            }
        }
    }
    return result;
}

位置xでの各ヌクレオチドの合計を一時配列bに保存。（xは[0..N-1]。）
各クエリで配列bの差分でヌクレオチドの存在を確認。

文字列の文字を1回列挙してN*4の配列bを作成。

クエリの配列を1回列挙するが、各クエリの計算は固定時間。
処理時間はNに比例し、使用するメモリの量もNに比例。

MinAvgTwoSlice (respectable)

N個の要素を持つ配列Aがあるとする。
0 <= P < Q < Nを満たす整数のペア (P, Q) を配列Aの スライス（slice） と呼ぶ。（スライスは必ず2個以上の要素が含まれる。）
スライス (P, Q) の 平均（average） を次のように定義する。
(A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1)

配列Aのスライスのうち、平均が最も小さいスライスの開始インデックスを求める。

A = [4, 2, 2, 5, 1, 5, 8]
    -> 1

スライスの例：
スライス (1, 2)の平均は (2 + 2) / 2 = 2
スライス (3, 4)の平均は (5 + 1) / 2 = 3
スライス (1, 4)の平均は (2 + 2 + 5 + 1) / 4 = 2.5
  • Nの範囲は[2..100,000]とする。
  • 配列Aの要素は[−10,000..10,000]の範囲の整数とする。

回答例

C++
int solution(vector<int> &A) {
    int currentSum = A[A.size() - 1] + A[A.size() - 2];
    int currentSumLength = 2;
    int bestIndex = A.size() - 2;
    int bestSum = currentSum;
    int bestSumLength = currentSumLength;
    for (int index = A.size() - 3; index >= 0; index--) {
        if (A[index + 1] * currentSumLength > currentSum) {
            currentSum += A[index];
            currentSumLength++;
        }
        else {
            currentSum = A[index] + A[index + 1];
            currentSumLength = 2;
        }
        if (bestSum * currentSumLength >= currentSum * bestSumLength) {
            bestSum = currentSum;
            bestSumLength = currentSumLength;
            bestIndex = index;
        }
    }
    return bestIndex;
}

次の要素を繋げて平均したほうが低くなるか、切り離して平均するほうが低くなるか、後ろから確認しつつ、最低値を求める。

任意の位置x（xは[0..N-2]）に対してxから開始する最低平均のスライスは次のいずれかになる：

  • A[x]とA[x+1]の平均（最小のスライスのほうが良い場合）
  • A[x]とx+1から開始する最低平均のスライスの平均（前の答えを拡張したほうが良い場合）

前者は (A[x]+A[x+1]) / 2。
後者は (A[x]+prevSum) / (prevLength + 1)。

配列Aを1回列挙し、処理時間はNに比例。
使用するメモリの量は固定。

CountDiv (respectable)

整数A, B, Kがあるとする。
[A..B]の範囲でKで割れる整数の数を求める。

例
A = 6, B = 11, K = 2
    -> 3

[6..11]の範囲で2で割れる数字は6, 8, 10である。
  • AとBの範囲は[0..2,000,000,000]とする。
  • Kの範囲は[1..2,000,000,000]とする。
  • A <= B とする。

回答例

C++
int solution(int A, int B, int K) {
    int modA = A % K;
    int first = modA == 0 ? A : A + K - modA;
    int modB = B % K;
    int last = modB == 0 ? B : B - modB;
    if (last < first) {
        return 0;
    }
    return (last - first) / K + 1;
}

処理時間と使用するメモリの量は固定。

Lesson 6: Sorting

Triangle (painless)

N個の要素の配列Aがあるとする。
整数のトリプレット (P, Q, R) は次の条件を満たす時、 三角形（triangular） であるという。（0 <= P < Q < R < Nとする。）

  • A[P] + A[Q] > A[R]（条件1）
  • A[Q] + A[R] > A[P]（条件2）
  • A[R] + A[P] > A[Q]（条件3）

配列Aに三角形なトリプレットが存在するか求める。
存在する場合は1を返し、そうでない場合は0を返す。

例
A = [10, 2, 5, 1, 8, 20]
    -> 1

トリプレット (0, 2, 4) は三角形である。

A = [10, 50, 5, 1]
    -> 0
  • Nの範囲は[0..100,000]とする。
  • 配列Aの要素は[−2,147,483,648..2,147,483,647]の範囲の整数とする。

回答例

C++
#include <algorithm>

int solution(vector<int> &A) {
    if (A.size() < 3) {
        return 0;
    }
    sort(A.begin(), A.end());
    int lastIndex = A.size() - 3;
    for (int index = 0; index <= lastIndex; index++) {
        long long lowestSum = (long long)A[index] + (long long)A[index + 1];
        if (lowestSum > A[index + 2]) {
            return 1;
        }
    }
    return 0;
}

A[P] + A[Q] > A[R]（条件1）とA[Q] + A[R] > A[P]（条件2）は、A[P] > A[R]を意味し、
A[Q] + A[R] > A[P]（条件2）とA[R] + A[P] > A[Q]（条件3）は、A[Q] > A[P]を意味する。
3つの条件を次の条件に書き換えられる。

  • A[P] > A[R]（条件a）
  • A[Q] > A[P]（条件b）
  • A[R] + A[P] > A[Q]（条件c）

配列Aをソートした上（条件aと条件bを達成したトリプレットの連続）で、条件cを確認する。

ソート時間以外に配列Aを1回列挙するのみで、処理時間はN*log(N)に比例。
使用するメモリの量はlog(N)に比例。

MaxProductOfThree (painless)

N個の要素の配列Aがあるとする。
トリプレット (P, Q, R) の 積（product） を A[P] * A[Q] * A[R] と定義する。（0 <= P < Q < R < Nとする。）

配列Aの要素で構成したトリプレットのうち、最も大きい積を求める。

例
A = [-3, 1, 2, -2, 5, 6]
    -> 60

トリプレット(0, 1, 2)の積は−3 * 1 * 2 = −6。
トリプレット(1, 2, 4)の積は1 * 2 * 5 = 10。
トリプレット(2, 4, 5)の積は2 * 5 * 6 = 60。
  • Nの範囲は[3..100,000]とする。
  • Aの要素は[−1,000..1,000]の範囲の指数とする。

回答例

C++
#include <algorithm>

int solution(vector<int> &A) {
    sort(A.begin(), A.end());
    int candidate1 = A.back() * *(A.rbegin() + 1) * *(A.rbegin() + 2);
    int candidate2 = A.front() * A[1] * A.back();
    return max(candidate1, candidate2);
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    A.sort()
    let candidate1 = A.dropFirst(A.count - 3).reduce(1) { $0 * $1 }
    let candidate2 = A[0] * A[1] * A.last!
    return max(candidate1, candidate2)
}

次の候補を比較する。

  • 最も大きい3つの値のトリプレット。
  • 最も大きい値、最も小さい2つの値で構成したトリプレット。（負数×負数の対応。）

ソート時間以外は固定時間。処理時間はN*log(N)に比例。
使用するメモリの量はlog(N)に比例。

（検討：ソートせずに候補を出せそう。）

Distinct (painless)

N個の整数を含む配列Aがあるとする。
その配列に含まれる異なる値の数を求める。

例
A = [2, 1, 1, 2, 3, 1]
    -> 3

異なる値は1, 2, 3である。
  • Nの範囲は[0..100,000]とする。
  • 配列Aの要素は[−1,000,000..1,000,000]の範囲の整数とする。

回答例

C++
#include <unordered_set>

int solution(vector<int> &A) {
    unordered_set<int> distinctValues(A.begin(), A.end());
    return distinctValues.size();
}

ハッシュテーブルに突っ込む。

処理時間はNに比例。使用するメモリの量もNに比例。

NumberOfDiscIntersections (respectable)

平面に円をN個、描画する。
円には0からN-1までの数字を割り当てる。
配列Aに含まれるN個の正数が各円の半径だとする。
円Jは、座標 (J, 0) を中心とし、半径はA[J]て描画される。

円Jと円Kの間で共通の点が1個でもあるとき（境界線を含む）、 交差する（intersect） という。（J != K のとき。）

交差する円のペアの数を求める。
答えが10,000,000を超える場合、-1を返す。

例
A = [1, 5, 2, 1, 4, 0]
    -> 11

円1と円4は交差し、いずれも他の全ての円と交差する。
円2は円0と円3とも交差する。
  • Nの範囲は[0..100,000]とする。
  • 配列Aの要素は[0..2,147,483,647]の範囲の整数とする。

回答例

C++
#include <algorithm>

struct Compare {
    vector<long long>& leftBorders;
    Compare(vector<long long>& leftBorders):
        leftBorders(leftBorders) {
    }
    bool operator()(int a, int b) {
        return leftBorders[a] < leftBorders[b];
    }
};

int solution(vector<int> &A) {
    if (A.size() <= 1) {
        return 0;
    }
    vector<long long> leftBorders;
    vector<int> orderedDiscs;
    leftBorders.reserve(A.size());
    orderedDiscs.reserve(A.size());
    for (int index = 0; index < A.size(); index++) {
        leftBorders.emplace_back((long long)index - (long long)A[index]);
        orderedDiscs.emplace_back(index);
    }
    sort(orderedDiscs.begin(), orderedDiscs.end(), Compare(leftBorders));

    int pairs = 0;
    auto last = orderedDiscs.end() - 1;
    for (auto it = orderedDiscs.begin(); it != last; it++) {
        long long rightBorder = (long long)*it + (long long)A[*it];
        for (auto checkIt = it + 1; checkIt != orderedDiscs.end(); checkIt++) {
            if (leftBorders[*checkIt] > rightBorder) {
                break;
            }
            pairs++;
            if (pairs > 10000000) {
                return -1;
            }
        }
    }
    return pairs;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    guard A.count > 1 else { return 0 }
    let leftBorders = A.enumerated().map { (index, value) in
        index - value
    }
    let discs = (0 ..< A.count).sorted { a, b in
        leftBorders[a] < leftBorders[b]
    }
    var pairs = 0
    for (index, disc) in discs.dropLast(1).enumerated() {
        let discRight = disc + A[disc]
        for checkDisc in discs.dropFirst(index + 1) {
            guard leftBorders[checkDisc] <= discRight else { break }
            pairs += 1
            if pairs > 10_000_000 {
                return -1
            }
        }
    }
    return pairs
}

各円をY軸に投影して範囲が被るかどうかで考える。
各園の最低X座標を計算し、ソートする。
ソートした順に交差するかを確認していく。

ソート時間以外、配列Aを1回列挙し、交差の確認にもう1回、残りの円を列挙。
処理時間はN*log(N)に比例。
使用するメモリはlog(N)に比例。

Lesson 7: Stacks and Queues

Nesting (painless)

N文字を含む文字列Sは、次の条件を満たすとき、 適切にネストされた（properly nested） という。

  • Sは空の文字列。
  • Sは"(U)"の形をしており、Uが適切にネストされている。
  • Sは"VW"の形をしており、VとWは適切にネストされている。

Sが適切にネストされているかを求める。
適切にネストされている場合は1を、そうでない場合は0を返す。

例
S = "(()(())())"
    -> 1
S = "())"
    -> 0
  • Nの範囲は[0..1,000,000]とする。
  • 文字列Sに含まれる文字は'('か')'のみとする。

回答例

C++
int solution(string &S) {
    int needToClose = 0;
    for (auto value: S) {
        switch (value) {
        case '(': needToClose++;
            break;
        case ')': needToClose--;
            if (needToClose < 0) {
                return 0;
            }
            break;
        }
    }
    return needToClose == 0 ? 1 : 0;
}

閉じれるカッコが後いくつあるかをカウントしながら確認していく。

文字列Sの文字を1回列挙し、処理時間はNに比例。
使用するメモリの量は固定。

Brackets (painless)

N文字を含む文字列Sは、次の条件を満たすとき、 適切にネストされた（properly nested） という。

  • Sは空の文字列。
  • Sは"(U)"、"[U]"、"{U}"のいずれかの形をしており、Uが適切にネストされている。
  • Sは"VW"の形をしており、VとWは適切にネストされている。

Sが適切にネストされているかを求める。
適切にネストされている場合は1を、そうでない場合は0を返す。

例
S = "{[()()]}"
    -> 1
S = "([)()]"
    -> 0
  • Nの範囲は[0..200,000]とする。
  • 文字列Sに含まれる文字は、'('、')'、'['、']'、'{'、'}'のみとする。

回答例

#include <stack>

int solution(string &S) {
    stack<char> bracketStack;
    bracketStack.emplace(0);
    for (char c: S) {
        switch (c) {
        case '(':
        case '{':
        case '[':
            bracketStack.emplace(c);
            break;
        case ')':
            if (bracketStack.top() != '(') {
                return 0;
            }
            bracketStack.pop();
            break;
        case ']':
            if (bracketStack.top() != '[') {
                return 0;
            }
            bracketStack.pop();
            break;
        case '}':
            if (bracketStack.top() != '{') {
                return 0;
            }
            bracketStack.pop();
            break;
        }
    }
    return bracketStack.size() == 1 ? 1 : 0;
}

カッコを開けた時にスタックに保存して、カッコを閉じたときにスタックの先頭が同じ種類のカッコかを確認していく。

文字列Sの文字を1回列挙し、処理時間はNに比例。
使用するメモリの量はNに比例。

Fish (painless)

配列Aと配列BはN個の整数を含み、川を泳ぐ魚を表す。

魚には0からN-1の番号を割り当てられ、
P < Q のとき、初期状態で魚Pは魚Qより上流にいることを表し、初期状態では全ての魚が異なる位置にいる。

魚は配列Aと配列Bで表す。
配列Aは魚の大きさを表すが、配列Aの値はユニークである。
配列Bは魚の泳ぐ方向を表すが、値は0か1となる。

  • 0は上流に泳ぐ魚を表す。
  • 1は下流に泳ぐ魚を表す。

逆の方向に泳ぐ魚は、間に他の魚がいない状態で遭遇すると、大きい魚が小さい魚を食べ、大きい魚だけが生き残る。

すなわち、P < Qのとき、B[P]が1でB[Q]が0で間に他の魚がいないとき、魚Pと魚Qは遭遇する。
遭遇した後、

  • A[P] > A[Q] なら、魚Pは魚Qを食べ、魚Pはそのまま下流に進む。
  • A[Q] > A[P] なら、魚Qは魚Pを食べ、魚Qはそのまま上流へ進む。

各魚は同じ速度で移動しているとする。すなわち、同じ方法に泳ぐ魚が遭遇することはない。

最終的に生存する魚の数を求める。

例
A = [4, 3, 2, 1, 5], B = [0, 1, 0, 0, 0]
    -> 2

魚1以外は上流に向かう。
魚1は魚2に遭遇し、魚2を食べる。
更に魚3に遭遇し、魚3を食べる。
最後に魚4に遭遇し、魚4に食べられる。
魚0と魚4が生き残る。
  • Nの範囲は[1..100,000]とする。
  • 配列Aの要素は[0..1,000,000,000]の半位の整数。
  • 配列Bの要素は1か0の値のみ。
  • 配列Aの要素は全て異なる。

回答例

C++
#include <stack>
#include <limits>

int solution(vector<int> &A, vector<int> &B) {
    int upFishAliveCount = 0;
    stack<int> downFishAlive;
    const int downFishEnd = numeric_limits<int>::max();
    downFishAlive.emplace(downFishEnd);
    for (int index = 0; index < A.size(); index++) {
        int fishSize = A[index];
        int fishDir = B[index];
        if (fishDir == 1) {
            downFishAlive.emplace(fishSize);
            continue;
        }
        while (downFishAlive.top() < fishSize) {
            downFishAlive.pop();
        }
        if (downFishAlive.top() == downFishEnd) {
            upFishAliveCount++;
        }
    }
    return upFishAliveCount + downFishAlive.size() - 1;
}

下流に進む魚をスタックする。
上流に進む魚を見た時、その大きさより小さい魚をスタックから出して処分する。スタックが空にった場合、その上流に進む魚は生存するためカウントする。
最後にスタックに残った生存した下流に進む魚と、上流に進んでいた生存した魚から結果を出す。

配列を1回列挙し、スタックする魚もNに比例するため、処理時間はNに比例。
使用するメモリの量はNに比例。

StoneWall (painless)

石でできた壁、石垣（stone wall）を作るとする。
壁はまっすぐな壁で、長さNメートル、厚さは固定、ただし、高さは所々変化する。
壁の高さは、正数をN個含む配列Hで表す。

H[I]は、壁の左から、IメートルからI+1の範囲の高さを表す。
したがって、H[0]は壁の左の端、H[N-1]は壁の右の端の高さを表す。

壁は、直方体（全ての面が長方形）の石のブロックで作られる。
この壁を作るために必要最低な石のブロックの数を求める。

例
H = [8, 8, 5, 7, 9, 8, 7, 4, 8]
    -> 7

図：
9        |-|
8|---|   | |-|   |-|
7|   | |-------| | |
6|   | |       | | |
5|   |---------| | |
4|   |         |---|
3|   |         |   |
2|   |         |   |
1|   |         |   |
0-------------------
  0 1 2 3 4 5 6 7 8
  • Nの範囲は[1..100,000]とする。
  • 配列Hの要素は[1..1,000,000,000]の範囲の整数とする。

回答例

C++
#include <stack>

int solution(vector<int> &H) {
    stack<int> stones;
    stones.emplace(0);
    int stonesCount = 0;
    for (auto height: H) {
        while (stones.top() > height) {
            stones.pop();
        }
        if (stones.top() != height) {
            stonesCount++;
            stones.emplace(height);
        }
    }
    return stonesCount;
}
Swift4
public func solution(_ H : inout [Int]) -> Int {
    var stones = [0]
    return H.reduce(0) { stonesCount, height in
        while stones.last! > height {
            stones.removeLast()
        }
        if stones.last! != height {
            stones.append(height)
            return stonesCount + 1
        }
        return stonesCount
    }
}

土台となっている石の高さをスタックする。
次の高さが低い場合は、高さが合う土台までスタックから石を外す。

配列Aを1回列挙し、スタック操作もNに比例するため、処理時間はNに比例。
使用するメモリの量はNに比例。

Lesson 8: Leader

Reading material には、 leader を検出するアルゴリズムが説明されている。
Time complexityがベストなアルゴリズムはリニア時間で、次のようなアプローチで検出している。

  1. 値が異なるペアを捨てていって、残った値がleader候補。
  2. leader候補が配列の中で何回出現するかカウント。
  3. そのカウントが配列の長さの半分以上なら、leaderである。

EquiLeader (painless)

整数N個の配列Aがあるとする。
この配列の要素の半数以上を占める値を リーダー（leader） と呼ぶ。
次の条件を満たすインデックスSを エクイリーダー（equileader） と呼ぶ。

  • 0 <= S <= N-1であること。
  • 次の2つのシーケンスのリーダーが同じ値であること：A[0], A[1], ..., A[S]とA[S + 1], A[S + 2], ..., A[N − 1]。

配列Aのエクイリーダーの数を求める。

例
A = [4, 3, 4, 4, 4, 2]
    -> 2

インデックス0はエクイリーダーである：[4] と [3, 4, 4, 4, 2] のリーダーは4であるため。
インデックス2はエクイリーダーである：[4, 3, 4] と [4, 4, 2] のリーダーは4であるため。
  • Nの範囲は[1..100,000]とする。
  • Aの要素は[−1,000,000,000..1,000,000,000]の範囲の整数とする。

回答例

Swift4
func leadersArray(from A: [Int]) -> [Int] {
    var valueCounts = [Int:Int]()
    var result = [Int]()
    result.reserveCapacity(A.count)
    var candidate = -1
    var dominance = 0
    for (index, value) in A.dropLast().enumerated() {
        let valueCount = (valueCounts[value] ?? 0) + 1
        valueCounts[value] = valueCount
        if dominance == 0 {
            candidate = value
            dominance = 1
        }
        else {
            dominance += candidate == value ? 1 : -1
        }
        let candidateIsLeader = dominance != 0 && valueCounts[candidate] ?? 0 > (index + 1) / 2
        result.append(candidateIsLeader ? candidate : -1)
    }
    return result
}

public func solution(_ A : inout [Int]) -> Int {
    let leaders = leadersArray(from: A)
    var valueCounts = [Int:Int]()
    return A.dropFirst().reversed().enumerated().reduce(0) { prev, current in
        let (index, value) = current
        let valueCount = (valueCounts[value] ?? 0) + 1
        valueCounts[value] = valueCount
        let leader = leaders[leaders.count - index - 1]
        guard leader != -1, valueCounts[leader] ?? 0 > (index + 1) / 2 else {
            return prev
        }
        return prev + 1
    }
}

各サブシーケンスA[0], ..., A[x]のリーダーを一時配列bのb[x]として保存する。（xは[0..N-2]。）
各b[y]が、サブシーケンスA[y+1], ..., A[N-1]のリーダーであるか確認する。（yは[0..N-2]。）

配列Aを1回列挙し、同じ大きさの配列をもう1回列挙。処理時間はNに比例。
使用するメモリの量はNに比例。

Dominator (painless)

整数をN個含む配列Aがあるとする。
この配列に含まれる値の中で、半分以上が同じ値の場合、その値を 支配者（dominator） よ呼ぶ。
配列Aの支配者の値のインデックスを一つ求める。
支配者が存在しない場合は-1を返す。

例
A = [3, 4, 3, 2, 3, -1, 3, 3]
    -> 0

配列の長さは8で、5回出現する3は支配者であり、インデックス0, 2, 4, 6, 7にこの値がある。
  • Nの範囲は[0..100,000]とする。
  • 配列Aの要素は[−2,147,483,648..2,147,483,647]の範囲の整数とする。

回答例

C++
int solution(vector<int> &A) {
    int candidate = 0;
    int dominance = 0;
    for (auto it = A.begin(); it < A.end(); it++) {
        if (dominance == 0) {
            candidate = *it;
            dominance = 1;
        }
        else {
            dominance += candidate == *it ? 1 : -1;
        }
    }
    if (dominance == 0) {
        return -1;
    }
    int candidateCount = 0;
    int requiredCount = A.size() / 2;
    for (auto it = A.begin(); it != A.end(); it++) {
        if (*it == candidate) {
            candidateCount++;
            if (candidateCount > requiredCount) {
                return it - A.begin();
            }
        }
    }
    return -1;
}

リーダーの候補を探し、その候補の出現回数を確認する。

配列Aを2回列挙。処理時間はNに比例。
使用するメモリの量は固定。

Lesson 9: Maximum slice problem

Reading material には、maximum sliceの検出アルゴリズムが説明されている。
配列どの部分の合計が最大値になるかを探すためのアルゴリズムで、
一番time complexityが良いアルゴリズムはリニア時間でこの問題を解決している。（Kadane's algorithm）

このアルゴリズムは次のようなアプローチ。

  • 配列の各要素を列挙する。
    • 要素ごとに、現在のindexで終わる maximum slice の合計値を計算する：
      index-1で終わるmaximum slice の合計値 + indexの値 と indexの値を比較し、大きい方を取る。
    • 列挙中に現在のindexで終わる maximum slice の合計値の最大値を保存する。

MaxProfit (painless)

N個の整数を含む配列Aがあるとする。
この配列は連続N日の株価を表す。

P日目に株を買い、Q日目に株を売った場合（0 <= P <= Q < Nとする）、
A[Q] >= A[P]のときはこの取引は A[Q] − A[P]の 利益（profit） を表し、
それ以外のときはA[P] − A[Q]の 損失（loss） を表す。

配列Aで可能な取引のうち、最高の利益を求める。
利益になる取引が不可能な場合は0を返す。

例
A = [23171, 21011, 21123, 21366, 21013, 21367]
    -> 356

0日目に買って2日目に売った場合、2048の損失になる。A[2] − A[0] = 21123 − 23171 = −2048であるため。
4日目に買って5日目に売った場合、354の利益になる。
1日目に買って5日目に売った場合、356の利益になる。こちらが最高の利益である。
  • Nの範囲は[0..400,000]とする。
  • 配列Aの要素は[0..200,000]の範囲の整数。

回答例

C++
int solution(vector<int> &A) {
    int currentSum = 0;
    int bestSum = 0;
    for (auto it = A.begin() + 1; it < A.end(); it++) {
        int diff = *it - *(it - 1);
        currentSum = currentSum <= 0 ? diff : diff + currentSum;
        if (bestSum < currentSum) {
            bestSum = currentSum;
        }
    }
    return bestSum;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    return A.dropFirst().enumerated().map { index, value in
        value - A[index]
    }.reduce((0, 0)) { prev, diff in
        let (bestSum, prevSum) = prev
        let newSum = prevSum <= 0 ? diff : diff + prevSum
        return (max(bestSum, newSum), newSum)
    }.0
}

毎日の差分に対し最も高い和のスライスを探す。
xで終わる最高の和のスライスは、次のいずれか。

  • xの要素のみ。（xが[0..N-1]以内のとき。）
  • x-1で終わる最高の和のスライスとxの要素。（xが[1..N-1]以内のとき。）

配列Aを1回列挙。処理時間はNに比例。
使用するメモリの量は固定。

MaxSliceSum (painless)

正数N個の配列Aがあるとする。
0 <= P <= Q < Nを満たす正数のペア(P, Q)は、配列Aの スライス（slice） と呼ぶ。
スライス(P, Q)の 和（sum） は次の合計を指す：A[P] + A[P+1] + ... + A[Q]。

配列Aで作成可能なスライスのうち、最高の和を求める。

例
A = [3, 2, -6, 4, 0]
    -> 5

スライス(3, 4)の和は4。
スライス(2, 2)の和は−6。
スライス(0, 1)の和は5。
スライス(0, 1)の和を超えるスライスは存在しない。
  • Nの範囲は[1..1,000,000]とする。
  • 配列Aの要素は[−1,000,000..1,000,000]の範囲の整数とする。
  • 結果は[−2,147,483,648..2,147,483,647]の範囲の整数であることを保証する。

回答例

C++
#include <limits>

int solution(vector<int> &A) {
    int currentSum = 0;
    int bestSum = numeric_limits<int>::min();
    for (auto value: A) {
        currentSum = currentSum <= 0 ? value : value + currentSum;
        if (bestSum < currentSum) {
            bestSum = currentSum;
        }
    }
    return bestSum;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    return A.reduce((Int.min, 0)) { prev, value in
        let (bestSum, prevSum) = prev
        let newSum = prevSum <= 0 ? value : value + prevSum
        return (max(bestSum, newSum), newSum)
    }.0
}

最も高い和のスライスを探す。
xで終わる最高の和のスライスは、次のいずれか。

  • A[x]のみ。（xが[0..N-1]以内のとき。）
  • x-1で終わる最高の和のスライスとA[x]を含めたスライス。（xが[1..N-1]以内のとき。）

配列Aを1回列挙。処理時間はNに比例。
使用するメモリの量は固定。

MaxDoubleSliceSum (respectable)

整数N個の配列Aがあるとする。
0 <= X < Y < Z < N を満たすトリプレット(X, Y, Z)を ダブルスライス（double slice） と呼ぶ。
ダブルスライス(X, Y, Z)の 和（sum） は次の合計を指す：A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]。

配列Aで構成できるダブルスライスのうち、最高の和を求める。

例
A = [3, 2, 6, -1, 4, 5, -1, 2]
    -> 17

ダブルスライス(0, 3, 6)の和は2 + 6 + 4 + 5 = 17。
ダブルスライス(0, 3, 7)の和は2 + 6 + 4 + 5 − 1 = 16。
ダブルスライス(3, 4, 5)の和は0。
17を超える和のダブルスライスは存在しない。
  • Nの範囲は[3..100,000]とする。
  • 配列Aの要素は[−10,000..10,000]の範囲の整数とする。

回答例

C++
int solution(vector<int> &A) {
    vector<int> bestEnd;
    bestEnd.reserve(A.size());
    int currentBestEnd = 0;
    bestEnd.emplace_back(0);
    for (auto it = A.begin() + 1, end = A.end() - 2; it != end; it++) {
        currentBestEnd = max(0, *it + currentBestEnd);
        bestEnd.emplace_back(currentBestEnd);
    }

    int bestSum = 0;
    int currentBestStart = 0;
    auto bestEndIt = bestEnd.rbegin();
    for (auto it = A.rbegin() + 1, end = A.rend() - 1; it != end; it++, bestEndIt++) {
        int sum = currentBestStart + *bestEndIt;
        if (bestSum < sum) {
            bestSum = sum;
        }
        currentBestStart = max(0, *it + currentBestStart);
    }
   return bestSum;
}
Swift4
public func solution(_ A : inout [Int]) -> Int {
    var bestEnd = [0]
    for value in A.dropFirst().dropLast(2) {
        bestEnd.append(max(0, bestEnd.last! + value))
    }
    let bestEndLastIndex = bestEnd.count - 1
    return A.reversed().dropFirst().dropLast().enumerated().reduce((0, 0)) { prev, enumeration in
        let (bestSum, currentBestStart) = prev
        let (index, value) = enumeration
        let sum = currentBestStart + bestEnd[bestEndLastIndex - index]
        return (max(bestSum, sum), max(0, value + currentBestStart))
    }.0
}

xで終わる最高の和のスライスの和を配列bのb[x]に保存する。（xは[0..N-1]。）
yで始まる最高の和のスライスの和を配列cのc[y]に保存する。（yは[0..N-1]。）
ダブルスライス(_, z, _)で構成できる最高の和は、b[z-1] + c[z+1]となる。（zは[1..N-2]。）

xで終わる最高の和のスライスは、次のいずれか。

  • 空のスライス。
  • A[x]のみ。（xが[0..N-1]以内のとき。）
  • x-1で終わる最高の和のスライスとA[x]。（xが[1..N-1]以内のとき。）

yで始まる最高の和のスライスは、次のいずれか。

  • 空のスライス。
  • A[y]のみ。（yが[0..N-1]以内のとき。）
  • y+1で始まる最高の和のスライスとA[y]。（yが[0..N-2]以内のとき。）

空のスライスの和が0であるため、各スライスの最高の和は最低0が保証される。
したがって、x-1で終わる最高の和のスライスとA[x]はA[x]のみより和が高く、y+1で始まる最高の和のスライスとA[y]もA[y]のみより和が高い。

配列Aを2回列挙。処理時間はNに比例。
使用するメモリの量はNに比例。

Lesson 10: Prime and composite numbers

Reading material には、因数の網羅と、素数の判定について説明されている。

Nの因数を探す際、brute forceだと1..Nの範囲で各整数が因数かどうかを確認する流れになるが、
1..sqrt(N)の間で片方の因数だけを探せば、割り算のペアのもう片方はsqrt(N)..Nに入っているため、そのペアを同時にカウントできる。
したがって、time complexity sqrt(N) でNの因数を網羅できる。

CountFactors (painless)

正数Dと正数Nで N = D * M を満たす整数Mが存在するとき、DはNの 因数（factor） と呼ぶ。
このような正数Nの因数の数を求める。

例
N = 24
    -> 8

Nの因数は1, 2, 3, 4, 6, 8, 12, 24であるため。
  • Nの範囲は[1..2,147,483,647]とする。

回答例

C++
int solution(int N) {
    if (N == 1) {
        return 1;
    }
    int result = 2;
    long long number = 2;
    for (; number * number < N; number++) {
        if (N % number == 0) {
            result += 2;
        }
    }
    if (number * number == N) {
        result++;
    }
    return result;
}
Swift4
public func solution(_ N : Int) -> Int {
    guard N != 1 else { return 1 }
    var result = 2
    var number = 2
    while number * number < N {
        if N % number == 0 {
            result += 2
        }
        number += 1
    }
    if number * number == N {
        result += 1
    }
    return result
}

N = 1のときを除いて、どの整数もN = 1 * Nで1とNの2つの因数がある（初期値）。
N = x * yのとき、xとyは因数であるため、同時に2つの因数をカウントする。（xは]1..sqrt(N)[、yは]sqrt(N)..N[。）
N = z * zのとき、zは1つの因数としてカウント。

整数を1からsqrt(N)まで列挙。処理時間はsqrt(N)に比例。
使用するメモリの量は固定。

C++、掛け算を消す
#include <cmath>

int solution(int N) {
    if (N == 1) {
        return 1;
    }
    int result = 2;
    int endNumber = (int)sqrt((double)N);
    if (endNumber * endNumber < N) {
        endNumber++;
    }
    for (int number = endNumber - 1; number >= 2; number--) {
        if (N % number == 0) {
            result += 2;
        }
    }
    if (endNumber * endNumber == N) {
        result++;
    }
    return result;
}

ループ内の掛け算を消してみたが、特に意味はなかった。

Flags (respectable)

N個の整数を持つ配列Aがあるとする。
前後の要素より値が大きい要素を 頂点（peak） と呼ぶ。
正確には、次の条件を満たすインデックスPが頂点である：
A[P − 1] < A[P] と A[P] > A[P + 1] （0 < P < N − 1のとき）。

配列Aの要素は山の高さを表し、山を登って頂点に旗を立てていくとする。
次の条件を満たした上で、立てられる旗の最大数を求める：

  • 旗は頂点にしか立てられない。
  • 旗をK個持っていく場合、旗を立てる各頂点の距離はK以上でなければならない。（インデックスPとQの距離は| P - Q |である。）
A = [1, 5, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2]
    -> 3

頂点は４箇所にある：1, 3, 4, 10。
旗を2個持っていった場合、頂点1と5に立てられる。
旗を3個持っていった場合、頂点1と5と10に立てられる。
旗を4個持っていった場合、頂点1と5と10に立てられ、立てられる旗は3個となる。
この場合立てられる旗の最大数は3個となる。
  • Nの範囲は[1..400,000]とする。
  • 配列Aの要素は[0..1,000,000,000]の範囲の値とする。

回答例

C++
#include <cmath>

int validFlags(vector<int>& nextPeak, int flags) {
    int validCount = 0;
    for (int testIndex = 0; testIndex < nextPeak.size(); testIndex = testIndex + flags) {
        testIndex = nextPeak[testIndex];
        validCount++;
        if (validCount == flags) {
            return validCount;
        }
    }
    return validCount;
}

int solution(vector<int> &A) {
    vector<int> nextPeak;
    nextPeak.reserve(A.size());
    int peaksCount = 0;
    for (auto it = A.begin() + 1, end = A.end() - 1; it < end;) {
        if (*it > *(it - 1) && *it > *(it + 1)) {
            peaksCount++;
            int peakIndex = it - A.begin();
            for (int nextPeakIndex = nextPeak.size(); nextPeakIndex <= peakIndex; nextPeakIndex++) {
                nextPeak.emplace_back(peakIndex);
            }
            it += 2;
        } else {
            it ++;
        }
    }
    if (peaksCount <= 2) {
        return peaksCount;
    }
    int maxFlags = (int)sqrt((double)A.size()) + 1;
    int bestFlags = 2;
    for (int testFlags = maxFlags; testFlags > 2; testFlags --) {
        int validCount = validFlags(nextPeak, testFlags);
        if (bestFlags > validCount) {
            break;
        }
        bestFlags = validCount;
    }
    return bestFlags;
}

頂点を探し、配列Aの任意インデックスxからx以上の次の頂点のインデックスが固定時間で分かるようにする。

頂点の数が2以下の場合、全ての頂点に旗を立てられるため、頂点数が答えになる。（定義上、頂点の隣のインデックスに頂点は無い。）

条件を満たすため、立てられる旗の数がsqrt(N)を超えることはありえない。
答えは[3..sqrt(N)]に入るが、sqrt(N)に一番違い旗の数をbrute forceで探す。

頂点インデックス配列を作成するのために配列Aを1回列挙。
頂点インデックス配列の大きさはNに比例。
答えとなりえる旗の数をチェックする際、[3..sqrt(N)]の範囲で最大sqrt(N)回のチェックを行うが、1回のチェックでやることは、条件を見たす旗の数の確認。条件を見たす旗の数の確認は最大sqrt(N)の旗に対し固定時間の処理（頂点インデックスのアクセス）となる。
処理時間はNに比例、使用するメモリの量はNに比例。

MinPerimeterRectangle (painless)

長方形の面積を表す整数Nがあるとする。
長方形の辺の長さがAとBの 面積（area） は、A * Bであり、その長方形の 周長（perimeter） は、2 * (A + B)である。

面積がNの長方形のうち、最も小さい周長を求める。
長方形の辺の長さは整数であるとする。

例
N = 30
    -> 22

面積が30を満たす長方形：
(1, 30)の周長は62。
(2, 15)の周長は34。
(3, 10)の周長は26。
(5, 6)の周長は22。
したがって、22が最小の周長。
  • Nの範囲は[1..1,000,000,000]とする。

回答例

C++
#include <cmath>

int solution(int N) {
    for (int number = (int)sqrt((double)N) + 1; number > 0; number--) {
        if (N % number == 0) {
            return (number + (N / number)) * 2;
        }
    }
    return 0;
}

sqrt(N)に一番近い因数xとx/Nの長方形の周長を求める。

整数のチェック回数はsqrt(N)に比例。
処理時間はsqrt(N)に比例、使用するメモリの量は固定。

Peaks (respectable)

整数をN個含む配列Aがあるとする。

配列の中で、前後の要素より値が大きい要素を 頂点（peak） と呼ぶ。
正確には、次の条件を満たすインデックスPが頂点である：
A[P − 1] < A[P] と A[P] > A[P + 1] （0 < P < N − 1のとき）。

配列Aを、同じ大きさのブロック（block）に分割したいとする。
すなわち、次のように配列を分割できる整数Kを探すことになる。

  • A[0], A[1], ..., A[K − 1]
  • A[K], A[K + 1], ..., A[2K − 1]
  • ...
  • A[N − K], A[N − K + 1], ..., A[N − 1]

更に、各ブロックは頂点が最低1つ含まれることを必須とする。
ブロックの先頭と末端も頂点であることがありえることを注意したい（上記の例ではA[K - 1]やA[K]等）、ただし前後の要素が存在する場合のみである（隣のブロック含む）。

配列Aからこのような条件で分割できるブロックの最大数を求める。
配列Aがこのようなブロックに分割できない場合は0を返す。

例
A = [1 2 3 4 3 4 1 2 3 4 6 2]
    -> 3

3、5、10が頂点となる。
1ブロックに分割した場合：(1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2)：3頂点を含む。
2ブロックに分割した場合：(1, 2, 3, 4, 3, 4) と (1, 2, 3, 4, 6, 2)はそれぞれ頂点を含む。
3ブロックに分割した場合：(1, 2, 3, 4)と(3, 4, 1, 2)と(3, 4, 6, 2)はそれぞれ頂点を含む。 
4ブロックに分割した場合：(1, 2, 3)と(4, 3, 4)と(1, 2, 3)と(4, 6, 2)のうち、(1, 2, 3)には頂点が含まれない。
したがって、条件を満たす最大ブロック数は3である。
  • Nの範囲は[1..100,000]とする。
  • 配列Aの要素は[0..1,000,000,000]の範囲の整数とする。

回答例

C++
#include <cmath>
#include <stack>

bool allBlocksHavePeak(vector<int> &peaksPrefix, int blockSize, int arraySize) {
    for (auto it = peaksPrefix.begin(), end = it + arraySize; it != end;) {
        auto blockEnd = it + blockSize;
        if (*it == *blockEnd) {
            return false;
        }
        it = blockEnd;
    }
    return true;
}

int solution(vector<int> &A) {
    int arraySize = (int)A.size();
    vector<int> peaksPrefix;
    peaksPrefix.reserve(arraySize + 1);
    peaksPrefix.emplace_back(0);
    peaksPrefix.emplace_back(0);
    int peaksCount = 0;
    for (auto it = A.begin() + 1, end = A.end() - 1; it < end; it++) {
        if (*it > *(it - 1) && *it > *(it + 1)) {
            peaksCount++;
        }
        peaksPrefix.emplace_back(peaksCount);
    }
    if (peaksCount == 0) {
        return 0;
    }
    peaksPrefix.emplace_back(peaksCount);
    int maxBlockSize = (int)sqrt((double)arraySize);
    if (maxBlockSize * maxBlockSize < arraySize) {
        maxBlockSize++;
    }
    stack<int> otherBlockSizes;
    for (int blockSize = 2; blockSize <= maxBlockSize; blockSize++) {
        if (arraySize % blockSize != 0) {
            continue;
        }
        int blocksCount = arraySize / blockSize;
        if (allBlocksHavePeak(peaksPrefix, blockSize, arraySize)) {
            return blocksCount;
        }
        otherBlockSizes.emplace(blocksCount);
    }
    while (!otherBlockSizes.empty()) {
        int blockSize = otherBlockSizes.top();
        if (allBlocksHavePeak(peaksPrefix, blockSize, arraySize)) {
            return arraySize / blockSize;
        }
        otherBlockSizes.pop();
    }
    return 1;
}

任意の範囲での頂点の有無を固定時間で判定するため、頂点数のprefix sums配列を作成する。
頂点が1つも存在しない場合は、0の答えが確定する。
逆に1つでもあれば、最低1ブロック（配列全体のブロック）が保証される。
Nの因数でブロックを作成した場合、各ブロックに頂点が含まれるか、小さいブロックから確認していって、最大数を求める。

頂点数のprefix sumsを作るために配列Aを1回列挙。
頂点数のprefix sumsの大きさはNに比例。
Nの因数の数に比例する回数ループするが、頂点の存在チェックでN/Nの因数の数回prefix sumsをアクセス。
処理時間はNに比例、使用するメモリの量はNに比例。

Lesson 11: Sieve of Eratosthenes

CountNonDivisible (respectable)

（やる）

CountSemiprimes (respectable)

（やる）

攻略

個人的な攻略法。
練習問題でも適当にやると考慮漏れがあったり、落とし穴があったりして面白い。
各レッスンの"Reading material"に割と重要な説明が書いてあるので、読むべき。

答えを探す考察

これまで役に立ったアプローチ。

  • アルゴリズムではなく、計算で答えを出す。
  • 一時データを作ってから処理をする、処理を早める（配列やハッシュテーブル）。
  • 標準ライブラリを使う。
  • 後ろから処理する。前からと後ろからの処理を組み合わせる。
  • 前の部分の答えに+1要素の答えを再帰的に出して引き伸ばす。（min、max等。）
  • 紙とペンで考える。（メモ帳ではイメージが限界な問題がある。）

提出前のもう一捻り

余裕ぶっこいて提出したら、対応が抜けていてやり直した部分の考慮。

  • ちゃんと問題を読み直す。
  • 数値の範囲をしっかり確認する。
    • C++の場合、64ビット整数が必要ならlong long（又はlong）を使う等。
  • 自分のテストを書いて必要に応じてテストする。
    • 簡単なやつでもできる限り全てのフローをテストする。（答えが一定以上の場合は-1を返す等。）
    • 配列パラメータをテストする：
      • 空配列や小さすぎる配列（1要素、2要素の配列等）。
      • 先頭の要素、末尾の要素に関わるロジック。
    • 特殊な計算をテストする：
      • 特殊な値（0や1等）。
      • マイナスな値。
      • INT_MIN/INT_MAXでオーバーフローさせられないか。
    • その他イレギュラーなケースをテストする。
  • パフォーマンスを改善できないか確認する。
    • ループ内で無駄な処理をしていないか。（break忘れ等。）
    • 実は不要な一時データを作っていないか。
  • printして正しく動いているかデバッグする。
19
20
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
19
20

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?