あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder 第一回日本最強プログラマー学生選手権-予選- B - Kleene Inversion (Go)

irisruneです。随分Go言語にもお世話になっているので競プロ以外でも何かしら形にしてみたい気分です。

問題

atcoder.jp

制約条件に注目すると解き方が見えるかもしれません。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const MOD = 1000000007

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()

    aArray := make([]int, n)
    for i := range aArray {
        aArray[i] = nextInt()
    }

    ans := 0
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            switch {
            case aArray[i] > aArray[j]:
                ans += (k * (k + 1) / 2) % MOD
            case aArray[i] < aArray[j]:
                ans += ((k - 1) * k / 2) % MOD
            default:
                continue
            }
            ans %= MOD
        }
    }

    fmt.Println(ans)
}

制約条件N\leq2000に注目すると、計算量がO(N^2)となるアルゴリズムを考えればよいと推察できます。一方K\leq10^9に注目すると、計算量のオーダーにKを含まないことが推察できます(O(N\log K)という可能性もなくはないですが)。

今回は転倒数について考えるので、まずK=1の単純な場合で考えてみます。この場合(A_i,A_j)(1\leq i\lt j\leq N)の組全てについて大小関係を考えればよいので、計算量はO(N^2)となります。

次にKを任意の値に拡張します。各組(A_i,A_j)(1\leq i\lt j \leq N)の大小関係に注目すると、

  1. A_i \gt A_jのとき、A_{i+Ns} \gt A_{j+Nt}, i+Ns \lt j+Nt (0\leq s\leq t\leq K-1)が成り立ちます。
    1. 転倒数は\sum^K_1=K(K+1)/2と求められます。
  2. A_i \lt A_jのとき、A_{j+Nt} \gt A_{i+Ns+1}, j+Nt \lt i+Ns+1  (0\leq s\leq t\leq K-2)が成り立ちます。
    1. 転倒数は\sum^{K-1}_1=(K-1)K/2と求められます。
  3. A_i = A_jのとき、転倒数は0です。

という性質が示せます。あとは和を取ることで任意の値Kに対してもO(N^2)の計算量で全体の転倒数を求めることができます。

雑記

  • 前回の記事でAtCoder ProblemsのDifficultyに触れていましたが、単純に算出アルゴリズムが別物になっていたというのが真相でした。
    • 過去のコンテストについても比較的確からしい数値になっているようです。
  • Paiza問題を扱った過去記事について、Paizaのサイトリニューアルにより問題文へのリンクが切れてしまっています。そのうち直します。