はじめに

突然Swiftをやることになり、たった2日でマスターできるiPhoneアプリ開発集中講座のアプリ作成を進めながら、基礎文法とXcodeの使い方を勉強して1週間ほどたったので、この1週間で調べたことを残しておきます...！
何かひとつでも、これから始める人のヒントになればうれしい。

varとlet

• varが変数
• letが定数

代表的なデータ型

• Int 整数を扱うための型
• Float 単精度の浮動小数を扱うための型
• Double 倍精度の浮動小数を扱うための型
• String 文字列を扱うための型、文字列データはダブルクォート”で囲むこと
• Bool 論理値を扱うための型、値はtrueかfalseとなる

オプショナル型

通常の変数と異なり空の値（値が無い）状態を保持することができる変数
オプショナル型はnilの代入ができる、非オプショナル型はできない

• オプショナル型にするとnilが使えるようになる
• オプショナル型は？や!を使って表現する

アンラップ

オプショナル型を非オプショナル型と同様に扱うには「アンラップ」という処理が必要

• 強制的アンラップはオプショナル型の変数に最後に"!"をつけて強制的にアンラップ
• オプショナルバインディングはif文などの条件分岐を使ってオプショナル型の値がnilかどうかで処理を分ける
• オプショナルチェイニングはオプショナル型の変数の後ろに"?"をつけて、そのあと続けてプロパティにアクセスしたりメソッドを呼び出す

guard文

想定外の状況が発生した場合に、その処理から抜け出すための構文
if文でも同様の処理が書けるが、guard文はスコープから抜ける処理を書かないとエラーになるため、guardが出てくると「必ず処理を抜ける」とわかり、可読性があがる

型推論

swiftでは、変数や定数の宣言時にデータ型の指定が原則として必要だが、宣言と同時に値を代入する場合は型を明示しなくても、代入する値をswift側で判断して変数や定数にデータ型を自動設定してくれる

データ型を明示して変数または定数を宣言する

宣言時点で代入する値が決まっていればswiftの型推論によってデータ型を明言する必要はなかったが、決まっていない場合はデータ型をあらかじめ明言しておく必要がある

print関数で出力する際に文字列とIntを扱う

print 関数でコンソールに出力する際、文字列””の中で\（定数または変数名）とすることで、文字列の中に埋め込むことができる

swiftの条件分岐では条件文の（）は省略できる

書いても問題ないけれど、省略するのが一般的

delegate はデザインパターン

• delegateを使うメリットは、処理を任せる側は実際に処理をするのはどのクラスなのか、どんな処理をするのかということを意識しなくていいこと
• 違う処理がしたい場合、処理を任されるクラスだけを新しく作ればいい
• プロトコルや処理を任せる側のクラスはそのまま再利用し、まったく異なる処理を行うことができる
• デザインパターンを使うことで誰が見てもわかりやすく、使いやすいプログラムを作ることができる

プロトコル

• デリゲートとほぼ対になって言及されるswiftの機能「プロトコル」
• プロトコルはクラス・構造体・列挙型の「仕様書」と呼べるもの
• 問い合わせ先に対して、どのようなプロパティやメソッドを使って問い合わせを行うかという「取り決め」をプロトコルを使って定義する

弱参照・強参照

クラスのインスタンスは何も指定しなければ通常「強参照」と呼ばれる形で代入される

• ARC (メモリ管理システム) インスタンスのメンバを追跡して、参照が残っているかどうかを見ている
• weak (弱参照)　参照対象が自身よりも先にメモリが解放されるときに使う
• unowned (非所有参照)　参照対象が自身と同じかより後にメモリが解放されるときに使う

CocoaPods(ライブラリ管理)

アプリケーションで、外部ライブラリ(Pod)を利用する際に必要な依存性の解決を自動的に行ってくれるソフトウェア

おわりに

自分の記録用です。
シンプルなアプリを4つ作成しながらだったので、たぶん記録できてないものでもっとあります...
まだまだわからないことだらけなので、ここが間違ってる！もっとここを勉強して！などありましたら、ご指摘いただけるとうれしいです。

参考

https://blog.kuromusubi.com/develop/language/swift/20180525-lazy
https://capibara1969.com/421/
https://qiita.com/maiki055/items/b24378a3707bd35a31a8#%E3%82%A2%E3%83%B3%E3%83%A9%E3%83%83%E3%83%97%E3%81%AE%E7%A8%AE%E9%A1%9E
https://scior.hatenablog.com/entry/2018/12/24/132704

はじめに

特定の文字列に触れたことを検知したい時や色・フォントを変更したい時のメモです。今回はUILabelのカスタムクラスを作成する感じで実装しました。

TL;DR

PartiallyLinkLabel.swift

protocol PartiallyLinkLabelProtocol: class {
    func partiallyLinkLabelLinkTextDidTap()
}

class PartiallyLinkLabel: UILabel {
    private var partTextRang: NSRange?
    private weak var viewProtocol: PartiallyLinkLabelProtocol?

    @objc private func textDidTap(_ gesture: UITapGestureRecognizer) {
        if attributedTextDidTap(gesture) {
            viewProtocol?.partiallyLinkLabelLinkTextDidTap()
        }
    }

    func set(_ viewProtocol: PartiallyLinkLabelProtocol, defaultColor: UIColor, partColor: UIColor, text: String, partText: String) {
        self.isUserInteractionEnabled = true
        self.addGestureRecognizer(UITapGestureRecognizer(target: self, action: #selector(self.textDidTap(_:))))
        self.viewProtocol = viewProtocol
        let attrText = NSMutableAttributedString()
        let partRang = NSString(string: text).range(of: partText)
        let aboveText = text.prefix(partRang.location)
        let belowText = text.suffix(text.length - (partRang.location + partRang.length))
        let aboveAttributeString = NSAttributedString(string: String(aboveText), attributes: [.foregroundColor: defaultColor])
        let belowAttributeString = NSAttributedString(string: String(belowText), attributes: [.foregroundColor: defaultColor])
        let partAttributeString = NSAttributedString(string: partText, attributes: [.foregroundColor: partColor])
        // defaultの.foregroundColorは.darkGrayにしたいのでそれぞれ分割して追加
        attrText.append(aboveAttributeString)
        attrText.append(partAttributeString)
        attrText.append(belowAttributeString)
        self.partTextRang = partRang
        self.attributedText = attrText
    }

    private func attributedTextDidTap(_ gesture: UITapGestureRecognizer) -> Bool {
        guard let partRang = partTextRang, let attrText = self.attributedText else {
            return false
        }
        let layoutManager = NSLayoutManager()
        let textContainer = NSTextContainer(size: CGSize.zero)
        let textStorage = NSTextStorage(attributedString: attrText)
        let labelSize = self.bounds.size

        layoutManager.addTextContainer(textContainer)
        textStorage.addLayoutManager(layoutManager)

        textContainer.lineFragmentPadding = 0.0
        textContainer.lineBreakMode = self.lineBreakMode
        textContainer.maximumNumberOfLines = self.numberOfLines
        textContainer.size = labelSize

        let locationOfTouchInLabel = gesture.location(in: self)
        let textBoundingBox = layoutManager.usedRect(for: textContainer)
        let textContainerOffset = CGPoint(x: (labelSize.width - textBoundingBox.size.width) * 0.5, y: (labelSize.height - textBoundingBox.size.height) * 0.5)
        // NSLayoutManagerからcharacterIndexを取得する際にはtextが表示されているboundsが使用されるため、offset分マイナスして調整する
        let locationOfTouchInTextContainer = CGPoint(x: locationOfTouchInLabel.x - textContainerOffset.x, y: locationOfTouchInLabel.y - textContainerOffset.y)
        let indexOfCharacter = layoutManager.characterIndex(for: locationOfTouchInTextContainer, in: textContainer, fractionOfDistanceBetweenInsertionPoints: nil)

        return NSLocationInRange(indexOfCharacter, partRang)
    }
}

Usage

ViewController.swift

class ViewController: UIViewController {

    @IBOutlet private weak var termsOfServiceLabel: PartiallyLinkLabel!

    override func viewDidLoad() {
        super.viewDidLoad()
        termsOfServiceLabel.set(self, defaultColor: .darkGray, partColor: .red, text: "決済をしたと同時に利用規約に同意したとみなします", partJaText: "利用規約")
    }
}

extension ViewController: PartiallyLinkLabelProtocol {
    func partiallyLinkLabelLinkTextDidTap() {
        // TODO: `利用規約` tapped event.
    }
}

結果

上手く表示されました。利用規約をタップすることでProtocolMethodが呼び出され任意の処理を実行することができます。

注意点

なぜわざわざTouchを検出したCGPointからtextContainerのOffSet分値を小さくすると上手くいくのか疑問だったが、コメントに残した通りNSLayoutManagerからcharacterIndexを取得する際にはtextが表示されているbounds(余白を除く幅)が使用されるため、offset分マイナスして調整することでタップ位置が正しく検出することができる感じだった。

PartiallyLinkLabel.swift

   let locationOfTouchInLabel = gesture.location(in: self)
   let textBoundingBox = layoutManager.usedRect(for: textContainer)
   let textContainerOffset = CGPoint(x: (labelSize.width -    textBoundingBox.size.width) * 0.5, y: (labelSize.height -    textBoundingBox.size.height) * 0.5)
   // NSLayoutManagerからcharacterIndexを取得する際にはtextが表示されてい   るboundsが使用されるため、offset分マイナスして調整する
   let locationOfTouchInTextContainer = CGPoint(x:    locationOfTouchInLabel.x - textContainerOffset.x, y:    locationOfTouchInLabel.y - textContainerOffset.y)
   let indexOfCharacter = layoutManager.characterIndex(for:    locationOfTouchInTextContainer, in: textContainer,    fractionOfDistanceBetweenInsertionPoints: nil)

ほしかったもの

Swiftでニンテンドーアカウントにアクセスしてiksm_sessionを取得したかった。

splatnet2statinkでは実装されているのだが、そのコードをPHP向けに書き直した感じです。

ただ、これだけでは足りなくてNexus氏のflapg APIとfrozenpandaman氏のs2s APIが別途必要になります。

実装

PHPでイカのコードを書くだけ。

<?php
function urlsafe_b64encode($val) {
  $val = base64_encode($val);
  return str_replace(["/","+","="], ["_","-",""], $val);
}
$auth_state = urlsafe_b64encode(random_bytes(36));
$auth_code_verifier = urlsafe_b64encode(random_bytes(32));
$auth_cv_hash = hash("sha256", $auth_code_verifier);
$auth_code_challenge = urlsafe_b64encode(hex2bin($auth_cv_hash));

$base_url = "https://accounts/nintendo.com/connect/1.0.0/authorize?";
$base_url = "https://accounts.nintendo.com/connect/1.0.0/authorize?";

$param = array( 
    "state" => $auth_state,
    "redirect_uri" => "npf71b963c1b7b6d119://auth",
    "client_id" => "71b963c1b7b6d119",
    "scope" => "openid user user.birthday user.mii user.screenName",
    "response_type" => "session_token_code",
    "session_token_code_challenge" => $auth_code_challenge,
    "session_token_code_challenge_method" => "S256",
    "theme" => "login_form"
);
$auth_url = $base_url . http_build_query($param);
$response = array(
    "auth_code_verifier" => $auth_code_verifier,
    "auth_url" => $auth_url);

header('content-type: application/json; charset=utf-8');
echo(json_encode($response, JSON_UNESCAPED_SLASHES));
?>

リダイレクトURIがURLエンコードされてしまうので微妙にダサい感じになるがこれで動きます。

完成したもの

自分のリリースしたアプリでどうしてもそういう機能が欲しかったのでこういうのを完成させました。

AWS上のサーバなのでご利用は計画的に。

https://app.codility.com/programmers/

練習問題が複数あって面白い。
得意な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
}

最下位の桁を処理して次の桁に進む。
桁を一つずつ1回列挙。

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）を無くす。

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回列挙（コピー）。

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回列挙。

回答例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回列挙するが一時データが必要ない。

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回列挙。

回答例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回列挙。一時データの配列が要らない。

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回列挙。

Lesson 4: Counting Elements

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回列挙。

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回列挙。

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回列挙。

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回列挙。

Lesson 5: 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回列挙。

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回列挙するが、各クエリの計算は固定時間。

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回列挙。

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回列挙。

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つの値で構成したトリプレット。（負数×負数の対応。）

ソート時間以外は固定時間。

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

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

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

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回、残りの円を列挙。

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回列挙。

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回列挙。

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

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

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

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

Lesson 8: 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回列挙。

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回列挙。

Lesson 9: Maximum slice problem

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回列挙。

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回列挙。

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回列挙。

攻略

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

答えを探す考察

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

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

提出前のもう一捻り

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

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

はじめに

Swift触り始めて2日目
軽いポートフォリオ的なものを作りたいなと。
完成イメージはこんな感じ。

moreを押してさらに詳しい情報をみれたりする。（未実装）

早速やっていこう。

環境

macOS Mojave ver10.14.6
Xcode 11.3.1
iPhone 11 iOS 13 (simulator)

Projectの作成

iOS->Single View App

ProductNameを書いてOrganization Indentifierを書いてNext
Createをしたら、初期コードが出てきます。

実際にやってみよう！

Tutorial.swift

import SwiftUI

struct ContentView: View {
    var body: some View {
        Text("Hello, World!")
    }
}

struct ContentView_Previews: PreviewProvider {
    static var previews: some View {
        ContentView()
    }
}

ダブルクオートで囲まれた部分を変えればテキストが変えれます。

Tutorial.swift

struct ContentView: View {
    var body: some View {
        Text("Hello, World!")
            .font(.title)
    }
}

.font(.title)をつけることで上のTextに文字サイズの変更などを行えます。

要素を追加しよう！

このままだと、Textが1行しか表示されないので・・・

Tutorial.swift

struct ContentView: View {
    var body: some View {
        VStack {
            Text("Hello, World!")
                .font(.title)
            Text("System Engineer")
        }
    }
}

VStackを追加してTextも1行追加しました
このVStackはVertical Stackで囲われている要素を縦に配置するものです。
また別にHStackと言うものもありHorizontal Stack、横並びに配置するものもあります。

なぜVStack、HStackを使うのか・・・
それは、1番上のTextの要素しか表示されないのです・・・
って解釈してます。

途中経過

こんな感じ。
もうほぼ近い。

まとめ

とりあえずここまで
次は画像入れるところやります。

ステータスバーみてもらえばわかると思うんですが、もう早朝4時なんです。眠いです。
おやすみなさい。

はじめに

Swift触り始めて2日目
軽いポートフォリオ的なものを作りたいなと。
完成イメージはこんな感じ。

moreを押してさらに詳しい情報をみれたりする。（未実装）

早速やっていこう。

環境

macOS Mojave ver10.14.6
Xcode 11.3.1
iPhone 11 iOS 13 (simulator)

Projectの作成

iOS->Single View App

ProductNameを書いてOrganization Indentifierを書いてNext
Createをしたら、初期コードが出てきます。

実際にやってみよう！

Tutorial.swift

import SwiftUI

struct ContentView: View {
    var body: some View {
        Text("Hello, World!")
    }
}

struct ContentView_Previews: PreviewProvider {
    static var previews: some View {
        ContentView()
    }
}

ダブルクオートで囲まれた部分を変えればテキストが変えれます。

Tutorial.swift

struct ContentView: View {
    var body: some View {
        Text("Hello, World!")
            .font(.title)
    }
}

.font(.title)をつけることで上のTextに文字サイズの変更などを行えます。

要素を追加しよう！

このままだと、Textが1行しか表示されないので・・・

Tutorial.swift

struct ContentView: View {
    var body: some View {
        VStack {
            Text("Hello, World!")
                .font(.title)
            Text("System Engineer")
        }
    }
}

VStackを追加してTextも1行追加しました
このVStackはVertical Stackで囲われている要素を縦に配置するものです。
また別にHStackと言うものもありHorizontal Stack、横並びに配置するものもあります。

なぜVStack、HStackを使うのか・・・
それは、1番上のTextの要素しか表示されないのです・・・
って解釈してます。

途中経過

こんな感じ。
もうほぼ近い。

まとめ

とりあえずここまで
次は画像入れるところやります。

ステータスバーみてもらえばわかると思うんですが、もう早朝4時なんです。眠いです。
おやすみなさい。

前置き

この記事自体は2019年10月に書き終わっていたのですが、、、

DroidKaigi2020に応募したCFP
「Scadeを使って「Swift」で始めるAndroidアプリ開発」
が通ったため、だいぶ温めてからの公開になりました、、笑

残念ながら開催は見送られてしまいましたが、、、
開催週に登壇の前座資料として、元々この記事を公開予定だったので公開しています！
（登壇資料はまだ開催予定を信じて公開は致しませんmm）

内容

登壇内容ほど詳しくは載せていませんが、みなさんがSwiftを使ってScadeでアプリ開発できるように

- Scadeのライトな説明
- 環境設定方法
- 開発トラベルシューティング

周りを記載しています。

What is Scade ?

SwiftをベースにiOS/Android向けのアプリを開発できる統合開発環境です。

どんな物が作れる？

DroidKaigi2020のコピーアプリをScadeを使って作りました。

といっても、検索フィルターなど一部の画面・機能は未実装です。
（単純に自分のコミット不足で実装しきれなかった）

また、リリースしたいと考えていたので（結局してないけど笑）
申請のリジェクトリスクを恐れてデザインは少し変更しています。
デザイン自体はDroidKaigi2020のアプリをベースにしています。

アプリのリポジトリを用意してあるので、詳しくはそのReadmeを見れいただけると！

（一部動作はぬるっとしてたりします。特にAndroidは、、泣）

開発環境構築

Scade公式のMacへのインストール方法

公式サイトにあるものは、英語なのと古いので、改めて以下の手順で行うと良いかと。

1. インストール

多いですが、iOS/Android双方へアプリをビルドする必要があるため、以下を全てインストールします。

• Java 8 SDKのダウンロード(ミラー)
• Android NDKのダウンロード(ミラー)
• Android Studioのダウンロード
• Xcodeのダウンロード（Xcode11以降）
• Scadeのダウンロード

複数のJREがインストールされている場合は、指定してあげるための対応が必要です。
(上記の公式サイトを参照してください)

2. Androidでビルドできるようにする

① Android Studioを起動

プロジェクトを開くか or 空のプロジェクトを作成してください

② 対応バージョンを入れる

[AndroidStudio] > [Preferences] > [Android SDK]
と進み、Android 6.0 にチェックを入れてインストールします。

③ 必要なSDKをインストールする

いくつかはデフォルトでインストールされているが、以下はないのでインストールします。
- Google Play services
- NDK

④ シュミレータのインストール

Android Studioをインストールしただけでは、何もシュミレータが入っていないので、自分で入れる必要があります。例では、Pixelを選択していますが、好きな端末を選んでインストールしていただければ。

3. iOSでビルドできるようにする

(こちらは後で行うことになるので一旦飛ばしても大丈夫です)

Xcode周りでは特に設定は必要ないです。

ただ、証明書がないとビルドできません。
（回避方法があるかも？現状見つけていない）

Scadeのプロジェクト作成時にできるbuild.yamlに証明書を設定する部分があるので設定します。
（証明書ファイル名前は適当ですので、確実すきな名前にしてください）

とりあえず動かしたいという方は、証明書を作成する際にApple Developerでアプリ名をワイルドカードにすると良いでしょう。

4. Scadeのセットアップ

1. パスの設定をする

Scadeの設定画面から以下を設定します。

• Android SDK はUsers配下にあるので、各自のパスを指定
• Android NDK は最初にインストールしたものを任意の場所に設置して、その場所を各自が指定

Android SDKの場所はAndroid Studioの設定画面からパスを確認することができます。

5. 「HelloWorld」する

XcodeのGUIのように開発が可能です！

①新規プロジェクトの作成

②ラベルの設置

③ビルドする端末を選択

④HelloWorld!

設定は少し面倒ですが、起動してしまえばすぐに開発を始めることができます。

※初回ビルドは失敗するので２回ビルドすること（端末が起動前だとエラーになる。特にAndroid）
※同じ端末をマルチビルドできないため、１端末ごとで行いましょう

その他

開発環境トラブルシューティング

実際に出くわして解決したものを載せておきます。

1. Androidでビルドできない時

DLツールの許可が必要な場合

インストールしたNDK内のコンパイラがビルド最中に弾かれてしまう場合があります。
（外部MacOS Catalinaだと発生する模様）

その場合は一度キャンセルし、Mac本体のシステム環境設定 > セキュリティとプライバシーから許可を行ってください。
（「ゴミ箱に入れる」は絶対にしない でください。やってしまった場合は、NDKを再インストールして入れ替えてください）

ちなみに４つほど弾かれるので、許可→再ビルド というのを４回ほど行う必要があるので注意

サポートライブラリが読み込めない場合

普通にAndroidの開発をしていた場合でも発生するエラーですが、、
（Androidでのビルドが止まってしまう）

実際にScade上で発生するエラーは以下

プロジェクトをクリーンをして、以下のandroidディレクトリを削除し
（Library > Android > sdk > android）

Scadeでビルドし直すことで解決できます。
そうすることで、サポートライブラリが再インストールされます。
（ただし、数分時間がかかるので注意）

2.iOSでビルドできない時

Scadeのアップデートの影響

最新版のScadeにアップデートした際に、Xcodeを10系->11系にする必要があります。
（現状Scadev0.9.17以降はXcode11.x系でないとビルドできなくなった）

その際、プロジェクトファイルのbuild.yamlファイルが変わっているためにビルドできなくなります。
アップデートすべき項目をこちらです。

新規プロジェクトを作成し、その中にあるyamlファイルを参考に古いプロジェクトにも項目を追加すると良いでしょう。

3.ビルドが通らない時

コンパイルが通らない

Xcode/Android Studio同様に、Scadeではビルド高速化のために、一度ビルドしたものをキャッシュしています。
が、その部分がたまに壊れてしまいビルドできなくなることがあります。

プロジェクトをクリーンし、吐き出されている[products]配下をすべて削除して、再びビルドすると通ることが多いです。

インストールされない・起動しない

Androidでよく起こりますが、端末によってはインストールできないアーキテクチャがあるようなので、
x86, arm64などいずれかでビルドできないか色々試してみましょう。

また、XcodeやAndroid Studioでもあるあるですが、再起動やプロジェクトクリーンで起動することもあります笑

git管理

リポジトリが肥大化しないために、gitignoreに以下を追加します。
（書き出されたipa, apkが含まれないようにします）

.build/
.target/
products/
*.ipa
*.scadeapp
.DS_Store
CMakeLists.txt
fonts/

終わりに

「タイトルにSwiftってあるのに記事に１文字もSwiftコードねえじゃねえか！」

すみません、書き終わって気づきました笑
（登壇の前座資料なので、あまり触れるわけにもいかず、、）

実際にどんな感じに書いているのかは、作成したアプリのリポジトリをみていただくか、
公式サイトにあるサンプルコードリポジトリをみていただくのが良いかと！

iOSとAndroidで実装分けるために汚いコードも一部ありますが、、、
それも含めてご覧になっていただけると笑