B - Interactive Sorting

言語テスト202001の方 L - Interactive Sorting

標準出力で質問し、答えが標準入力で返ってくるインタラクティブ問題。初めて取り組みましたが楽しかったです。解くのにめちゃくちゃ時間かかりました。

問題文

最初の N 個の大文字でラベルの付いた N 個のボールがあります。どの二つのボールの重さも異なります。

あなたは Q 回クエリを質問することができます。各クエリでは、二つのボールの重さを比べることができます。

ボールを軽い順にソートしてください。

制約

(N, Q) は　(26, 1000), (26, 100), (5, 7) のいずれか

補足

ラベルはA~Zの文字です。N=5なら A, B, C, D, E のボールがあるということです。

それぞれのボールがどれくらいの重さなのかは不明です。標準出力(print関数)によるクエリで尋ねることで二つのボールの重さの大小が判明します。

例えばAとBの重さの関係を知りたいとき、クエリとして以下の形式で標準出力します。

? A B

これでAのボールの方が重かったら

がクエリの応えとして標準入力(readLine関数)で得られるようになります。

標準出力→標準入力→標準出力・・・というやり取りが発生するタイプの問題なので、インタラクティブ問題ということです。

最終的な結果は以下の形式で出力します。ボールの重さを C < A < B とします。

! CAB

解答

クエリ関数

まずはクエリの関数を紹介します。問題を解いているときに、クエリの処理は分けたほうが楽ということに気づいたので作りました。

import Foudation

func lt(_ l: String, _ r: String) -> Bool {
    print("?", l, r)
    fflush(stdout)
    return readLine()! == "<"
}

関数名はless thanの略です。

この問題は標準出力のたびにflushすることを求めているので、クエリのたびにflushします。そのための関数、fflush関数はFoundationをインポートすることで使えるようになります。

クエリ後、標準入力でクエリの結果を得られるので、readLine()!で結果を得ます。結果は"<"か">"です。この関数は標準入力がless thanを示す"<"かどうかを返します。

ソートアルゴリズム

この問題の最初の難所は、最大26個のボールを100回以内のクエリでソートすることです。

クイックソートは最悪計算量が$ O(N^2) $なので間に合わない可能性があります。また、SwiftのArray.sort(by:)の計算量ですが、公式ドキュメントは以下のように記載していますが最悪計算量は不明です。

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements for which areInIncreasingOrder does not establish an order.

Complexity: O(n log n), where n is the length of the collection.

実装も見てみましたが、よくわかりませんでした。

不安なのでマージソートを実装することにします。

ちなみにArray.sorted(by:)で実装するとWAになりました。

以下マージソートについてです。

マージソートは分割統治法のアルゴリズムで、部分部分で解決していくアルゴリズムの一種です。

疑似動的言語で概要を書くと以下のようになります。

func mergeSort(array) {
    // 要素が一つ以下のときのソートは自明なので返す。
    if array.count <= 1 {
        return array
    }

    // arrayを左半分、右半分にわけ、それぞれでマージソートする。
    mid = array.count / 2
    left = array[0..<mid]
    right = array[mid..<array.count]
    sortedLeft = mergeSort(left)
    sortedRight = mergeSort(right)

    // 二つをマージする
    return merge(sortedLeft, sortedRight)
}

例: N=10のマージソート

要素数を10とします。（N=10)

① [4, 8, 9, 6, 2, 3, 5, 1, 7, 0]

これを半分にわけ、それぞれでマージソートします。

② [4, 8, 9, 6, 2] [3, 5, 1, 7, 0]

③ [2, 4, 6, 8, 9] [0, 1, 3, 5, 7]

二つをマージします。マージのアルゴリズムはWikipediaがわかりやすいです。(https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8)

④ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

手順③でなぜ唐突にマージソートされているのでしょうか。

それは、N=5のマージソートだからです。N=5のマージソートは以下の過程を経て、ソートされることが保証されます。

N=5のマージソートでは、N=3とN=2のマージソートを行い、それらをマージします。

N=3のときはN=2とN=1のマージソートを行い、それらをマージします。

N=2のときはN=1とN=1のマージソートを行い、それらをマージします。

N=1ときは自明なのでそのまま返します。

この過程は数学的帰納法のような感じです。

以下、Swiftでの実装です。

func mergeSort(_ array: [String]) -> [String] {
    // 基底部
    guard array.count > 1 else { return array }
 
    let mid = array.count / 2
 
    let sortedL = mergeSort(Array(array[..<mid]))
    let sortedR = mergeSort(Array(array[mid...]))
 
    return merge(sortedL, sortedR)
}
 
func merge(_ sortedL: [String], _ sortedR: [String]) -> [String] {
    var container = [String]()
    var l = 0
    var r = 0
 
    // 左右の配列をマージ
    while l < sortedL.count && r < sortedR.count {
        if lt(sortedL[l], sortedR[r]) {
            container.append(sortedL[l])
            l += 1
        } else {
            container.append(sortedR[r])
            r += 1
        }
    }
 
    if l < sortedL.count {
        container += sortedL[l...]
    }
 
    if r < sortedR.count {
        container += sortedR[r...]
    }
 
    return container
}

N = 5, Q = 7のとき

次の難所は、N = 5, Q = 7のときです。これはマージソートではギリギリ間に合いません。

マージソートだと最大何回比較することになるのか見てみます。


	[A, B]					[C, D, E]
[A]		[B]		[C,D]			[E]
			[C]		[D]

A, Bの比較(1回目)
C, Dの比較(2回目)
[C, D], Eの比較(最大4回目)(C < E && D < E のときなど)
[A, B], [C, D, E]の比較(最大8回目)(A < C && C < B && D < B && E < B のときなど)

この問題はもはや論理パズルです。

以下解答です。

5つのボールを、

(x1, x2)
(y1, y2)
e

という3つのグループに分けます。

また、x1 < x2, y1 < y2, x1 < y1 とします。(☆)

この時点で、x1 < y1 < y2は成立しています。しかし、x2 < y1, x2 < y2とは限りません。

なので[x1, y1, y2]という配列から x2 と e の場所を特定すればOKです。

これまでの比較回数を確認します。(☆)の段階で、比較は3回行っています。

x1 < x2, y1 < y2, x1 < y1

残り4回で、x2 と e の場所を特定します。

それぞれ2回ずつの比較で特定できたら良さそうです。

まず、e の場所を特定します。これは簡単です。

[x1, y1, y2]から、二分探索で、e の場所を特定できます。比較回数は2回です。

次に、x2 の場所を特定します。

e の場所は以下パターンのいずれかです。

[e, x1, y1, y2]
[x1, e, y1, y2]
[x1, y1, e, y2]
[x1, y1, y2, e]

x1 < x2なので、x2 の場所を特定するときは、上記パターンからx1以前の要素を省いたようなパターンと捉えてよいです。

[y1, y2]
[e, y1, y2]
[y1, e, y2]
[y1, y2, e]

これらはいずれも、e を特定するパターンと同じで、二分探索で x2 の場所を特定できます。比較回数は最大2回です。

これでクエリ7回以内に5つのボールをソートできました。

以下実装です。

func n5() -> [String] {
    var (x1, x2) = ("A", "B")
    if lt(x2, x1) {
        (x1, x2) = (x2, x1)
    }
    // x1 < x2
 
    var (y1, y2) = ("C", "D")
    if lt(y2, y1) {
        (y1, y2) = (y2, y1)
    }
    // y1 < y2
 
    if lt(y1, x1) {
        (x1, x2, y1, y2) = (y1, y2, x1, x2)
    }
    // x1 < y1
    // → x1 < x2, y1 < y2,  x1 < y1 < y2
    // x2 < y1,  x2 < y2とは限らない
    
    var sorted = [x1, y1, y2]
 
    // e の二分探索。比較は2回
    let e = "E"
    var l = -1
    var r = 3
    while r - l > 1 {
        let mid = (r + l) / 2
        if lt(e, sorted[mid]) {
            r = mid
        } else {
            l = mid
        }
    }
    sorted.insert(e, at: r)
 
    // x2 の二分探索。 x1 < x2 なので探索は [1, 3] の範囲でOK。比較は2回
    l = 0
    r = 4
    while r - l > 1 {
        let mid = (r + l) / 2
        if lt(x2, sorted[mid]) {
            r = mid
        } else {
            l = mid
        }
    }
    sorted.insert(x2, at: r)
 
    return sorted
}

後は呼び出すだけです。

func readInt() -> [Int] {
    return readLine()!.split(separator: " ").map{Int($0)!}
}

func main() {
    let line = readInt()
    let N = line[0]
 
    let a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".prefix(N).map { String($0) }
 
    let sorted = N == 5 ? n5() : mergeSort(a)
    print("!", sorted.joined(separator: ""))
}

main()

いや、むずいです。

全体のソース

import Foundation

func compare(_ l: String, _ r: String) -> String {
    print("?", l, r)
    fflush(stdout)
    return readLine()!
}

func mergeSort(_ array: [String]) -> [String] {
    // 基底部
    guard array.count > 1 else { return array }
 
    let mid = array.count / 2
 
    let sortedL = mergeSort(Array(array[..<mid]))
    let sortedR = mergeSort(Array(array[mid...]))
 
    return merge(sortedL, sortedR)
}
 
func merge(_ sortedL: [String], _ sortedR: [String]) -> [String] {
    var container = [String]()
    var l = 0
    var r = 0
 
    // 左右の配列をマージ
    while l < sortedL.count && r < sortedR.count {
        if lt(sortedL[l], sortedR[r]) {
            container.append(sortedL[l])
            l += 1
        } else {
            container.append(sortedR[r])
            r += 1
        }
    }
 
    if l < sortedL.count {
        container += sortedL[l...]
    }
 
    if r < sortedR.count {
        container += sortedR[r...]
    }
 
    return container
}

func n5() -> [String] {
    var (x1, x2) = ("A", "B")
    if lt(x2, x1) {
        (x1, x2) = (x2, x1)
    }
    // x1 < x2
 
    var (y1, y2) = ("C", "D")
    if lt(y2, y1) {
        (y1, y2) = (y2, y1)
    }
    // y1 < y2
 
    if lt(y1, x1) {
        (x1, x2, y1, y2) = (y1, y2, x1, x2)
    }
    // x1 < y1
    // → x1 < x2, y1 < y2,  x1 < y1 < y2
    // x2 < y1,  x2 < y2とは限らない
    
    var sorted = [x1, y1, y2]
 
    // e の二分探索。比較は2回
    let e = "E"
    var l = -1
    var r = 3
    while r - l > 1 {
        let mid = (r + l) / 2
        if lt(e, sorted[mid]) {
            r = mid
        } else {
            l = mid
        }
    }
    sorted.insert(e, at: r)
 
    // x2 の二分探索。 x1 < x2 なので探索は [1, 3] の範囲でOK。比較は2回
    l = 0
    r = 4
    while r - l > 1 {
        let mid = (r + l) / 2
        if lt(x2, sorted[mid]) {
            r = mid
        } else {
            l = mid
        }
    }
    sorted.insert(x2, at: r)
 
    return sorted
}

func readInt() -> [Int] {
    return readLine()!.split(separator: " ").map{Int($0)!}
}

func main() {
    let line = readInt()
    let N = line[0]
 
    let a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".prefix(N).map { String($0) }
 
    let sorted = N == 5 ? n5() : mergeSort(a)
    print("!", sorted.joined(separator: ""))
}

main()