AtCoder 第一回日本最強プログラマー学生選手権-予選- B - Kleene Inversion (Go)
irisruneです。随分Go言語にもお世話になっているので競プロ以外でも何かしら形にしてみたい気分です。
問題
制約条件に注目すると解き方が見えるかもしれません。
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) }
制約条件に注目すると、計算量がとなるアルゴリズムを考えればよいと推察できます。一方に注目すると、計算量のオーダーにを含まないことが推察できます(という可能性もなくはないですが)。
今回は転倒数について考えるので、まずの単純な場合で考えてみます。この場合の組全てについて大小関係を考えればよいので、計算量はとなります。
次にを任意の値に拡張します。各組の大小関係に注目すると、
- のとき、が成り立ちます。
- 転倒数はと求められます。
- のとき、が成り立ちます。
- 転倒数はと求められます。
- のとき、転倒数はです。
という性質が示せます。あとは和を取ることで任意の値に対してもの計算量で全体の転倒数を求めることができます。
雑記
- 前回の記事でAtCoder ProblemsのDifficultyに触れていましたが、単純に算出アルゴリズムが別物になっていたというのが真相でした。
- 過去のコンテストについても比較的確からしい数値になっているようです。
- Paiza問題を扱った過去記事について、Paizaのサイトリニューアルにより問題文へのリンクが切れてしまっています。そのうち直します。