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

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

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

競プロ AtCoder 第一回日本最強プログラマー学生選手権-予選- B問題 300点 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のサイトリニューアルにより問題文へのリンクが切れてしまっています。そのうち直します。

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

競プロ AtCoder 第一回日本最強プログラマー学生選手権-予選- A問題 200点 Go

irisruneです。残念なことに仮眠したらコンテスト時間に寝過ごしてしまったので不参加でした。

問題

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
}

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

    ans := 0
    for mth := 1; mth <= m; mth++ {
        for dth := 1; dth <= d; dth++ {
            switch {
            case dth/10 <= 1:
                continue
            case dth%10 <= 1:
                continue
            case (dth/10)*(dth%10) == mth:
                ans++
            default:
                continue
            }
        }
    }
    fmt.Println(ans)
}

制約条件上、全部で高々10^4通りしかないので愚直に全通り試してみることで解くことができます。満たすべき条件が少々複雑なので整理すると、

  1. dが2桁の整数
    1. dを10で割った商が0ならば1桁なので除外すればよい。
    2. dを10で割った商が10以上ならば3桁以上なので除外すればよいが、制約上あり得ないので無視できる。
  2. dの1の位が2以上
  3. dの10の位が2以上
    1. 条件1.1.と同時に確認できる。
  4. mがdの1の位と10の位との積

となります。上記の通り、条件1.については個別に確認する必要はなく2.～4.を確認すればよいので、条件式を3つ用意すれば条件を満たすことの判定を行うことができます。

計算量を減らす方法について（おまけ）

少しあっさりすぎたので、おまけとして計算量を減らすことを考えてみます。2通りアプローチがあり、これらは組み合わせることもできます。

制約条件をさらに制限する

満たすべき条件から、考慮する値の範囲を絞ることができます。

  1. 4\leq m\leq 81
    1. 条件を満たすmは合成数（1でも素数でない自然数）となる必要があるため、m\geq 4である。
    2. dが2桁の整数であるため、m\leq 81である。
  2. 22\leq d\leq 99
    1. dの10の位と1の位がそれぞれ2以上となる必要があるため、d\geq 22である。
    2. dが2桁の整数であるため、d\leq 99である。

与えられた制約条件上では以上の条件を追加しても定数倍最適化にしかなりませんが、例えば1\leq M\leq 10^9などという条件が設定された場合でも計算量が増大せずに済みます。

条件から候補を求める

月または日を定めると、候補となる月または日を絞ることができます。そのため、月または日の一方を全通り試してもう一方は候補となる値を取り得るかどうかチェックするという方式で解くことができます。

例えば月から日を求める場合、日の1の位として2から9までの値を考えることで候補となる日を絞り込むことができます。あとは与えられたDと候補日を比較することで答えを求めることができます。

この場合の計算量はO(M)となるため、特にDが大きい場合は（問題の制約上では高々10倍程度ですが）高速化が見込めます。

2つの手法を組み合わせる

制約条件を絞り込んだ上で月あるいは日のみ全通りチェックするということも可能です。

下記では月の範囲を絞りこんだ上で月から候補日を求めるという手法を用いています。日から候補月を求める手法の方が候補月が1つに定まるためかなり簡単な上に、計算量も削減できると思います。

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
}

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

    ans := 0
    for mth := 4; mth <= m; mth++ {
        if mth > 81 {
            break
        }
        for div := 2; div <= 9; div++ {
            if mth/div < 10 && mth/div > 1 && mth%div == 0 {
                if (mth/div)*10+div <= d {
                    ans++
                }
                if div*10+(mth/div) <= d {
                    ans++
                }
            }
        }
    }
    fmt.Println(ans / 2)
}

雑記

  • AtCoder ProblemsのDifficultyの高さに驚きましたが、新形式のABCがARCを内包するようになったのでARC（相当）のコンテストも難易度が上がるのは当然かもしれません。
    • （いつもの企業コンとは違うけれども）企業コンなので、最近のABCによくいるD（,E,F）問題だけ解いて1完という人がいなかったということもあり得ますね。
      • AGCにもいない気はしましたが、こちらはA問題の配点が空気なので影響がないのかもしれません。

AtCoder AGC 037 A - Dividing a String (Go)

競プロ AtCoder AGC037 A問題 300点 Go

irisruneです。ふとデザインを変えたいと思いましたが、ある程度まとまった時間を取らないと難しいですね。

問題

atcoder.jp

最多の分割を行うための方針は結構単純です。実は嘘解法と化していたことに後で気付きました。

package main

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

var sc *bufio.Scanner

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var s, t string
    fmt.Scan(&s, &t)

    structure := make(map[rune][]int)
    for r := 'a'; r <= 'z'; r++ {
        structure[r] = make([]int, 0)
    }

    for i, rs := range s {
        structure[rs] = append(structure[rs], i+1)
    }

    n := len(s)
    ans := 0
    for _, rt := range t {
        if len(structure[rt]) == 0 {
            ans = -1
            break
        }
        baseIndex := (ans % n) + 1
        var searchIndex int
        switch {
        case sort.SearchInts(structure[rt], baseIndex) == len(structure[rt]):
            searchIndex = n + structure[rt][0]
        default:
            searchIndex = structure[rt][sort.SearchInts(structure[rt], baseIndex)]
        }
        ans += searchIndex - baseIndex + 1
    }

    fmt.Println(ans)
}

まず連続する2つの部分文字列が一致しないという条件を無視して考えてみると、明らかに1文字ずつに分割するのが最多の分割となります。では前述の条件を満たす分割についてはどうなるかというと、aaa...という文字列では以下のような分割を行うことが考えられます。

a aa a aa a aa ...

よって1文字あるいは2文字の部分文字列に分割すればよいとわかります。ここから分割の最大数1を以下のアルゴリズムで求めることができます。

  1. 1文字目を基準点とする。
  2. 残りが1文字ならば当然分割をしない。
  3. 基準点と1文字先がそれぞれ違う文字ならば、その間で分割をして基準点を1文字進める。
  4. 基準点と1文字先が同じ文字ならば、
    1. 残りが3文字以上ならば、その間で分割して更に2文字先と3文字先の間でも分割をし、基準点を3文字進める。
    2. 残りが2文字ならば、分割をしない。
  5. 進めた基準点から再び2.～4.を行う。

このようにして解ける理由を2つの例を挙げて説明します。

1つ目の例はaaaaという文字列についてです。この文字列を頭から見ることを考えると、1文字目と2文字目が同じ文字であるため間で分割を行うかどうか選択することになります。ここで上記のアルゴリズムに反して分割を行わない場合、

aaa a

と分割するしかなくなります。これは明らかに、

a aa a

と更に分割することができ、結局1文字目と2文字目との間で分割を行うことが正しそうです。

2つ目の例はaaaaaという文字列についてです。これは上記のアルゴリズムが正しく成立しない例であり、実際に適用すると

a aa aa

となりますがこれは正しい分割ではありません。ただし、

a aaa a

と分割し直すことで条件を満たすようになり、しかも分割数も変わっていません。そのため、上記のアルゴリズムで求めた分割数をそのまま解とすることができます。嘘から出た真ですね。

上記コードでは逆に結合数を求めてから分割数を算出していますが、分割数をそのまま求めてもあまり変わらないと思います。

雑記

  • 明日のコンテストは（多分）比較的得意なARC形式なのでいい結果を残したいですね。

  1. 後述しますが、正しい分割を求めているわけではありません。↩

AtCoder ABC 138 E - Strings of Impurity (Go)

競プロ AtCoder ABC138 E問題 500点 Go

irisruneです。久々に比較的易しめなE問題だった気はします。

問題

atcoder.jp

発想力が占める比重がかなり大きい気はします。

package main

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

var sc *bufio.Scanner

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var s, t string
    fmt.Scan(&s, &t)

    structure := make(map[rune][]int)
    for r := 'a'; r <= 'z'; r++ {
        structure[r] = make([]int, 0)
    }

    for i, rs := range s {
        structure[rs] = append(structure[rs], i+1)
    }

    n := len(s)
    ans := 0
    for _, rt := range t {
        if len(structure[rt]) == 0 {
            ans = -1
            break
        }
        baseIndex := (ans % n) + 1
        var searchIndex int
        switch {
        case sort.SearchInts(structure[rt], baseIndex) == len(structure[rt]):
            searchIndex = n + structure[rt][0]
        default:
            searchIndex = structure[rt][sort.SearchInts(structure[rt], baseIndex)]
        }
        ans += searchIndex - baseIndex + 1
    }

    fmt.Println(ans)
}

まず考えるべきは、sを10^{100}連結する必要があるのかについてです。tがsを任意の個数連結した文字列の部分列となるためには、tを構成するすべての文字がsにそれぞれ1個以上含まれていることが必要十分条件です。よって、条件を満たすならばtがsを|t|個連結した文字列の部分列であることは明らかです。

以上よりsを高々|t|個連結するだけでよいのですが、これでも文字列長が10^{10}となってしまうため普通に照合しては間に合いません。そこで、aからzまでの各文字がsの何文字目に該当するかという情報を利用することを考えます。ここで各文字の位置情報をソートされた配列を用いて保持しておくと、基準となる位置より右に特定の文字が存在するか、また存在するなら何文字目かを二分探索を用いて調べることができます。つまり計算量は前処理を含めてO(|s|+|t|\log|s|)で抑えられることがわかります。

ここまでくればあとは実装するだけですが、最終的な出力となる値とsの探索基準位置に剰余の関係を使うなど少しややこしいのでWAを出しやすいと思います。自分の場合はtに同じ文字が2つ続く入力のテストができておらずWAを出していました（入力例2が該当しますが、出力が-1となるためテストケースとしては別物です）。

雑記

  • Goの二分探索アルゴリズムに範囲指定の引数がないのは少し面食らいましたが、スライスで簡単に計算コストも少なく範囲指定できるので必要ないんですね。

AtCoder ABC 138 D - Ki (Go)

競プロ AtCoder ABC138 D問題 400点 Go

irisruneです。休暇を過ごした人もそうでない人もまた心機一転していきましょう。

問題

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
}

type node struct {
    weight int
    adj    []int
    parent int
}

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

    tree := make([]node, n+1)
    for i := 0; i < n-1; i++ {
        a, b := nextInt(), nextInt()
        tree[a].adj = append(tree[a].adj, b)
        tree[b].adj = append(tree[b].adj, a)
    }

    for j := 0; j < q; j++ {
        p, x := nextInt(), nextInt()
        tree[p].weight += x
    }

    ans := make([]int, n+1)
    queue := make([]int, 0)
    queue = append(queue, 1)
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        ans[u] = ans[tree[u].parent] + tree[u].weight
        for _, v := range tree[u].adj {
            if v == tree[u].parent {
                continue
            }
            tree[v].parent = u
            queue = append(queue, v)
        }
    }

    for i := 1; i < n; i++ {
        fmt.Print(ans[i])
        fmt.Print(" ")
    }
    fmt.Println(ans[n])
}

木をどのように構築するかは様々な方法があると思いますが、今回は頂点を構造体で定義して隣接リストをもつ形を取りました。

まず愚直に解くことを考えてみると、各操作を行うたびに各頂点のカウンターに値を足すことになります。しかし、操作回数がQ回、各操作の対象となる頂点数がO(N)であることから、計算量がO(NQ)となってしまいます。

簡単に思い付く計算量削減の方法としては、各操作を基準となる頂点ごとにまとめてしまうことです。これにより操作にかかる計算量がO(Q)となり全体の計算量がO(N+Q)で抑えられるように見えます。

ここで重要なのが各操作をまとめたものを木に対してどのように反映させるかです。これまた愚直に実装すると各頂点1,2,\ldots,Nにまとめた操作の分量だけ、頂点を根とする部分木の各頂点に対してカウンターの値を増やすという形になりますが、これでは計算量がO(N^2+Q)となってしまいます。

タネを明かせば、各頂点についてその頂点を基準とする操作の分量とその親のカウンターの値を足すことでカウンターの値を求めることができます（頂点1については当然親のカウンターの値は0です）。

この方法でカウンターの値を求めると、計算量をO(N+Q)で抑えることができます。

雑記

  • コンテスト不参加で問題だけ解くのはレートに縛られないのもあってやはり気楽でした。
    • 単純に参加した時に限って難しいD・E問題が続いていたという所もあります。
  • 次回からはまた参加できるよう準備しておきたい所ですね。

AtCoder ABC 137 C - Green Bin (Go)

競プロ AtCoder ABC137 C問題 300点 Go

irisruneです。前回のコンテストは色々あり2完で-91（1292→1201）と大変冷えました。

問題

atcoder.jp

解き方自体は発想さえできればといったところですが、言語のソート仕様によっては実装が面倒になります。

実はこの提出コードはAC時のものではありません。どこに問題があるか探してみるのもいいですね。

package main

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

var sc *bufio.Scanner

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

type ByRune []rune

func (r ByRune) Len() int {
    return len(r)
}

func (r ByRune) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r ByRune) Less(i, j int) bool {
    return r[i] < r[j]
}

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

    strMap := make(map[string]int)
    for i := 0; i < n; i++ {
        var s string
        fmt.Scan(&s)
        rs := []rune(s)
        sort.Sort(ByRune(rs))
        sSorted := string(rs)
        _, ok := strMap[sSorted]
        if ok {
            strMap[sSorted]++
        } else {
            strMap[sSorted] = 1
        }
    }

    ans := 0
    for _, v := range strMap {
        ans += v * (v - 1) / 2
    }
    fmt.Println(ans)
}

2つの文字列の組がアナグラムの関係になっているかを判断するには文字種ごとの文字数を考えるのが直感的です。しかし、全ての文字列のペアに対してアナグラムの関係になっているかチェックすると計算量がO(N^2)になってしまいます。

そこで辞書型（あるいは連想配列）を用いることにより、アナグラムの関係になっている文字列のグループを作ることを考えます。最終的な答えは、各グループの要素数をM_jとおくと\sum M_j(M_j - 1)/2と求められます。

文字種ごとの文字数を考える場合でも、26桁の11進数に変換するなどの工夫をすれば上記の方法に落とし込むことができます。ただ、各文字列を文字単位でソートする方がスマートに見えると思います。なお、計算量は一般的にはソートする方が大きいですが、文字列長が10で固定のためソートする方が小さくなります。

ここまで来ればあとは実装するだけなのですが、Goのソート仕様が大きく足を引っ張ってしまいます。Goで構造体のリストをソートする際に散々苦しめられてきているのはご存知かもしれませんが、実は組み込み型についてもInt,Float64,String以外の型についてはソート関数が標準で実装されていません（正確には、ソートインタフェースへの変換関数が実装されていません）。

そのため、文字（Rune型）の配列を新たに型として定義し、定義した型についてソートインタフェースの実装を行ってからソートを行う必要があります。そもそもRune型の存在を知っていないとどうにもならないので文字列仕様とソート仕様のダブルパンチを受けている格好です。

ところで上記コードはAC時のものではないと述べましたが、なんと全てのケースについてWAが出てしまいます。D問題でTLEして後に引けなくなったところにC問題の全WAで心が折れてしまったのが大寒波の正体でした。

原因としてはsc.Scan()を一度実行してしまうと以降のfmt.Scan()で取得される文字列が全て空になってしまうというものです。そのため、nの取得もfmt.Scan()で行う（あるいは、sの取得をsc.Scan()→sc.Text()で行う）ようにすればACとなります。

バージョンの差異による問題か、手元で実行した時には出力結果が正常だったので焦りもあってコンテスト中に原因が突き止められませんでしたが、後でAtCoderのコードテストで試すと出力が0であったために気付くことができました。

雑記

  • 今回のようなケースを考えるとやはり手元の環境とAtCoder上の環境とで言語バージョンは揃えた方がいいのですが、Go周りの（公式）ツールが正常にインストールされないという問題があるのが厳しいです。
    • 言語アップデートでAtCoder側がバージョンアップしてくれればあまり考えることもないのですが、なかなかアップデートが実施されないですね。

AtCoder Tenka1 Programmer Contest C - Align (Go)

競プロ AtCoder Tenka1 Programmer Contest 2018 C問題 400点 Go

irisruneです。お盆休みのある人もいたり学生さんは夏休みだったりしますが、よい休暇を過ごせるといいですね。

問題

atcoder.jp

なんとなくでも解法が見えそうな問題ですが、証明が難しかったり落とし穴があったりします。

package main

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

var sc *bufio.Scanner

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

func intAbs(a int) int {
    if a > 0 {
        return a
    }
    return -a
}

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

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

    ans1 := 0
    sort.Sort(sort.IntSlice(aArray))
    aSlice := aArray[:]
    aLeft, aRight := aSlice[0], aSlice[0]
    aSlice = aSlice[1:]
    for {
        if len(aSlice) == 0 {
            break
        }
        ans1 += intAbs(aLeft - aSlice[len(aSlice)-1])
        aLeft = aSlice[len(aSlice)-1]
        aSlice = aSlice[:len(aSlice)-1]
        if len(aSlice) == 0 {
            break
        }
        ans1 += intAbs(aRight - aSlice[len(aSlice)-1])
        aRight = aSlice[len(aSlice)-1]
        aSlice = aSlice[:len(aSlice)-1]

        if len(aSlice) == 0 {
            break
        }
        ans1 += intAbs(aLeft - aSlice[0])
        aLeft = aSlice[0]
        aSlice = aSlice[1:]
        if len(aSlice) == 0 {
            break
        }
        ans1 += intAbs(aRight - aSlice[0])
        aRight = aSlice[0]
        aSlice = aSlice[1:]
    }

    ans2 := 0
    sort.Sort(sort.Reverse(sort.IntSlice(aArray)))
    aSlice = aArray[:]
    aLeft, aRight = aSlice[0], aSlice[0]
    aSlice = aSlice[1:]
    for {
        if len(aSlice) == 0 {
            break
        }
        ans2 += intAbs(aLeft - aSlice[len(aSlice)-1])
        aLeft = aSlice[len(aSlice)-1]
        aSlice = aSlice[:len(aSlice)-1]
        if len(aSlice) == 0 {
            break
        }
        ans2 += intAbs(aRight - aSlice[len(aSlice)-1])
        aRight = aSlice[len(aSlice)-1]
        aSlice = aSlice[:len(aSlice)-1]

        if len(aSlice) == 0 {
            break
        }
        ans2 += intAbs(aLeft - aSlice[0])
        aLeft = aSlice[0]
        aSlice = aSlice[1:]
        if len(aSlice) == 0 {
            break
        }
        ans2 += intAbs(aRight - aSlice[0])
        aRight = aSlice[0]
        aSlice = aSlice[1:]
    }

    switch {
    case ans1 > ans2:
        fmt.Println(ans1)
    default:
        fmt.Println(ans2)
    }
}

直感的に考えると、一列に並べた時に中央に一番小さな要素が、その両隣に二番目までに大きな要素が、その両隣に三番目までに小さな要素が…という形で並べるとよさそうに思えます。与えられた入力例で考えると、

2 8 1 6 3

4 1 9 1 5 3

5 1 5

という並び順になります。なお、入力例2のようにNが偶数の場合は最後に残った要素を左右どちらにつけるかで結果が変わってしまうので、より大きな（小さな）値を左側か右側どちらかに優先的に付けるようにするとよいです。

この考え方は厳密に考えるとそれほど間違ってはおらず、公式解説の考え方を借りれば左右端の要素が与えられた整数群の中央値付近であればよかったりします。

ただし一つだけ落とし穴があり、例えば入力例3を少し変えたケースで

5 1 1

と出力してしまうと明らかに誤った結果となります。要するに、一番小さな要素を中央に置くケースと一番大きな要素を中央に置く（その両隣に小さい要素、大きい要素、…と置く）ケースとで結果が異なるわけです。実際には入力例2では結果が同じとなるため、Nが偶数の場合は気にしなくていいのかもしれません。

以上を踏まえて、2通りの整数の並べ方を試して結果が大きい方を出力するという形で解くことができます。

余談ですが、上記コードではGoのスライスの性質を活用しています。スライス上で範囲の切り出しを行っても元の配列は変わらないので、同じ配列の実体を参照しながら範囲の切り出しと復元を（実現しているかのように）実装できるわけですね。aArrayという名前で宣言しているのが既にスライスなのはご愛敬です。

雑記

  • 実はコンテスト参加当時解けなかった問題でした。
    • 代わりにD問題が解けてしまったので試合に勝って勝負に負けたというフレーズがぴったりでした。

AtCoder ABC 136 E - Max GCD (Go)

競プロ AtCoder ABC136 E問題 500点 Go

irisruneです。問題の解説など試行錯誤していますが、アドバイスや感想などコメントを貰えると嬉しいです。

問題

atcoder.jp

あることに気付かないとどうにも方針が立てられないので、かなりパズル要素が強い問題だと思います。

package main

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

var sc *bufio.Scanner

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

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

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

    var div []int
    for i := 1; i*i <= aSum; i++ {
        if aSum%i == 0 {
            div = append(div, i)
            if i != aSum/i {
                div = append(div, aSum/i)
            }
        }
    }
    sort.Sort(sort.Reverse(sort.IntSlice(div)))

    for _, d := range div {
        mod := make([]int, n)
        for i, a := range aArray {
            mod[i] = a % d
        }
        sort.Sort(sort.IntSlice(mod))
        modSum := 0
        for _, m := range mod {
            modSum += m
        }
        if modSum == 0 {
            fmt.Println(d)
            return
        }
        modDiff := 0
        for i := n - 1; modSum > modDiff; i-- {
            modSum -= mod[i]
            modDiff += d - mod[i]
        }
        if modSum == modDiff && modSum <= k {
            fmt.Println(d)
            return
        }
    }
}

何回操作を行ってもA_iの和は不変であること、そして答えとなる値はA_iの和の約数しかあり得ないということに気付くことがスタートラインです。（Kを無限大とおいた上では）十分条件であることは簡単に証明できますが、必要条件であることを証明するのは少々骨が折れそうです。公式解説でも証明されていないので今回は証明なしで進めていきます。

A_iの和の約数に答えの候補を絞りこんだところで、実際に答えとなる値を求める方法について考えます。求めるゴールとしてはA_iが全て答えの倍数になるよう操作を行うことを考えることになります。

ここでKを無限大とおいた場合、すべての答えの候補に対してこのような操作は必ず行うことができます。というのも、A_iのうち1つを除いて全て0になるよう操作を行えば、除いた1つの値はA_iの和となり、すべてのA_iの和の約数は条件を満たすことになるからです。そういうわけで、実際には操作回数がK以下であるかどうかをチェックすればよいことになります（上記コードでは操作が行えるか自体もチェックしていますが）。

ではどのようにチェックすればよいかというと、答えの候補の値でA_iそれぞれを割った剰余に注目し、剰余が小さい方から一定の個数の和を操作回数とします。操作回数に含めなかった分については、答えの候補の値から剰余を引いた値の和を負の操作回数とし、2つの操作回数の絶対値が一致する値を真の操作回数として求めます。あとは真の操作回数がK以下であれば答えとして成立するということになります（出力するのは最大値のみということに注意）。

公式解説では累積和などを用いればよいとありますが、おそらく両方向の累積和を計算する必要がありやや複雑化するため今回は尺取り法で求めました。計算量については変わらず、A_i\leq10^6なのでO(N\sqrt{10^6N}\log N)となります（定数が入るのはオーダー表記としておかしいですが、無視できない値なので大目に見てください）。

余談ですが、1回目の提出では約数の列挙にO(10^6N)かけていたためTLEを連発してしまい、テストケースが妙に多かったのもあってジャッジに10分かかりました。コンテスト中だったらテロ行為ですね。

雑記

  • IPAの試験申し込み締め切り日まであと1週間ですね。
    • 受験予定の人は申し込みを忘れて-1次試験に落ちないようにしましょう。
    • 当日会場に辿り着くことが0次試験とはよく言われますよね。

AtCoder ABC 136 D - Gathering Children (Go)

競プロ AtCoder ABC136 D問題 400点 Go

irisruneです。日曜開催は予定を合わせるのが難しいです。

問題

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
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var s string
    fmt.Scan(&s)
    rs := []rune(s)
    n := len(rs)

    children := make([]int, n)

    cntR := 0
    for i := 0; i < n; i++ {
        switch {
        case rs[i] == 'R':
            cntR++
        case rs[i] == 'L':
            children[i] += cntR / 2
            children[i-1] += (cntR + 1) / 2
            cntR = 0
        }
    }

    cntL := 0
    for i := n - 1; i >= 0; i-- {
        switch {
        case rs[i] == 'L':
            cntL++
        case rs[i] == 'R':
            children[i] += cntL / 2
            children[i+1] += (cntL + 1) / 2
            cntL = 0
        }
    }

    for i := 0; i < n-1; i++ {
        fmt.Print(children[i])
        fmt.Print(" ")
    }
    fmt.Println(children[n-1])
}

この問題のポイントとしては、一定回数以上の操作を行うと2つの状態を交互に遷移するということです。具体的には、"RL"という部分文字列の出現する2つのマスで子どもの入れ替わりが起こり続け、それ以外のマスには子供がいないという形になります。

そのため、最終状態である10^{100}回の移動を行った後の状態は、交互に遷移する2つの状態のうち偶数回の移動を行ったときの状態として表すことができます。

あとはそれをどう表現するかですが、2つの状態を交互に遷移するまで愚直に操作をシミュレートするという方法が一つ考えられます。しかし1回の操作に計算量がO(N)かかるとすると行うべき操作の回数は最悪でO(N)のため全体でO(N^2)となり到底間に合いません。

動的計画法を用いてシミュレートすれば全体でO(N\log N)に抑えられるらしいですが、そちらの方法は公式解説が詳しいです。今回は文字列を解析して最終状態を求める方法を取ります。

"RL"という部分文字列に着目するならば、文字列全体を"RR...RL...LL"という部分文字列に分割して考えても問題ありません。この場合初期状態で"R"のマスにいる子供については、"RL"からの距離が偶数のマスにいる子供は"R"のマス、奇数のマスにいる子供は"L"のマスに最終状態でいることになります（"RL"の"R"にいる子供は距離0とみなします）。同様のことが"L"のマスにいる子供についてもいえるので、計算量O(N)で最終状態を求めることができます。

なお、上記コードについては左端から右方向に"L"の連続する個数を数えて"R"が見つかった時に最終状態を更新し、右端から左方向に"R"の連続する個数を数えて"L"が見つかった時に最終状態を更新するという実装で、コードを単純化しています。左端が"R"、右端が"L"であることが制約条件で与えられているためその辺りのチェックが必要ないのは楽ですね。

雑記

  • テンプレートだけ残っているいつもの標準入力受け取り部分ですが、前回前々回で触れたように長大文字列に対応していないので今回使っていません。
    • 長大文字列に対応した速い入力方法もあるようですが、横着してfmt.Scanを使っています。
  • 来週は夏季休暇予定のため、1回更新するかしないかくらいになると思います。

AtCoder AGC 002 B - Box and Ball (Go)

競プロ AtCoder AGC002 B問題 400点 Go

irisruneです。久々の過去問回です。

問題

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
}

type box struct {
    balls int
    red   int
}

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

    boxes := make([]box, n+1)
    for i := range boxes {
        boxes[i].balls = 1
    }
    boxes[1].red = 1

    for j := 0; j < m; j++ {
        x, y := nextInt(), nextInt()
        boxes[y].balls++
        if boxes[x].red == 1 {
            boxes[y].red = 1
        }
        boxes[x].balls--
        if boxes[x].balls == 0 {
            boxes[x].red = 0
        }
    }

    ans := 0
    for _, b := range boxes[1:] {
        ans += b.red
    }
    fmt.Println(ans)
}

各箱についてボールが何個あるか、赤いボールが入っている可能性があるかを管理しておきます。この状態で操作を行ったとき、以下のことがいえます。

  1. ボールを入れた箱のボールの数は1個増える。
  2. ボールを取り出した箱に赤いボールが入っている可能性があった場合、ボールを入れた箱のボールに赤いボールが入っている可能性がある。
  3. ボールを取り出した箱のボールの数は1個減る。
  4. ボールを取り出した箱のボールの数が0個になる場合、ボールを取り出した箱に赤いボールが入っている可能性はない。

以上を踏まえて、各箱のボールの数を1個、箱1のみ赤いボールが入っている可能性があるという初期状態から操作をシミュレートすることで解くことができます。ただし、上記2.の処理の前に4.の処理を行うなどすると結果が狂う可能性があるため気を付けましょう。

雑記

  • 前回の問題（ABC135D）ですが無事ACできました。
    • 前にも引っかかった入力方法による文字列長の上限によって、長大文字列を途中で打ち切って入力していたのが原因です。

AtCoder ABC 135 D - Digits Parade ※解説AC未遂 (Go)

競プロ AtCoder ABC135 D問題 400点 Go

irisruneです。今回は解説ACすらできていないという困った状況です。

問題

atcoder.jp

全探索は途方もない組み合わせ数になり、10進数に対する13で割った剰余なので右何桁かを見てある程度決まるということもないという、かなりアプローチに困る問題です。

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
const DIV = 13
const BASE = 10

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    rs := append([]rune{'0'}, []rune(sc.Text())...)
    n := len(rs) - 1

    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, DIV)
    }
    dp[0][0] = 1

    for i := 1; i <= n; i++ {
        var digit int
        switch {
        case rs[i] == '?':
            digit = -1
        default:
            digit = int(rs[i] - '0')
        }

        for j := 0; j < BASE; j++ {
            if digit != -1 && digit != j {
                continue
            }
            for k := 0; k < DIV; k++ {
                dp[i][(k*BASE+j)%DIV] = (dp[i][(k*BASE+j)%DIV] + dp[i-1][k]) % MOD
            }
        }
    }
    fmt.Println(dp[n][5])
}

ほぼ公式解説のコードをGoに移植しただけなのであまり言えることはなかったりします。そもそもこのコードは8個ほどWAが出ているので移植しきれていないということなんですよね…

方針としては、上i桁を13で割ったときの余りを用いて上i+1桁を13で割った余りを求めることができることを利用して、桁DP（のようなこと）を行うというものです。これは、剰余の性質より(10\times A + B) \mod M \equiv (10\times A \mod M) + (B \mod M)となることから明らかです。

あとはDPテーブルから解がi導き出せるはずなのですが…なぜWAが出るのかがわからないのが現状です。

雑記

  • WAが出ている問題の共通項としては実行時間が3msで計算量が多くはないということなのですが、逆にそれくらいしか手掛かりがないので何も掴めていない状態です。

AtCoder ABC 135 C - City Savers (Go)

競プロ AtCoder ABC135 C問題 300点 Go

irisruneです。ABC135参加はしましたが…D問題以降が解けずNoSub撤退をすることになりました。

問題

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
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

    aArray := make([]int, n+1)
    for i := 0; i < n+1; i++ {
        aArray[i] = nextInt()
    }
    bArray := make([]int, n+1)
    for i := 0; i < n; i++ {
        bArray[i] = nextInt()
    }
    // bArray[n] = 0

    ans := 0
    for i := n; i > 0; i-- {
        ans += minInt(aArray[i], bArray[i])
        aArray[i] = maxInt(0, aArray[i]-bArray[i])
        ans += minInt(aArray[i], bArray[i-1])
        // aArray[i] = maxInt(0, aArray[i] - bArray[i - 1])
        bArray[i-1] = maxInt(0, bArray[i-1]-aArray[i])
    }
    ans += minInt(aArray[0], bArray[0])
    // aArray[0] = maxInt(0, aArray[0] - bArray[0])
    fmt.Println(ans)
}

今回注目したポイントは、N+1番目の街を襲っているモンスターを倒すことができるのはN番目の勇者のみという点です。ここからN+1,N,\ldots,1番目の街の順にN,N-1,\ldots,1番目の勇者が全力でモンスターを倒す手順を考えるとこの問題を解くことができます。

以上の解法でも特に問題なく解くことができるのですが、問題の設定条件をよく見ると1番目の街を襲っているモンスターを倒すことができるのも1番目の勇者のみのため、実際には1,2,\ldots,N,N+1番目の街の順に考えるだけで解くことができます。

雑記

  • 4完（1000点）以上の見込みがなければ撤退という方針で臨んだわけですが、D問題の解法が思いつかなかったのでE問題に取り組んだら更なる絶望に叩き落された気分でした。
    • サンプルケースが弱かったらE問題を提出してたかもしれないですね、それでも緑色まで落ちることはなかったでしょうが…
    • 3完（600点）で水パフォがあり得るのは久々だったのではないでしょうか。

AtCoder ABC 134 E - Sequence Decomposing (Python)

競プロ AtCoder ABC134 E問題 500点 Python

irisruneです。最近晴れることが多くなりましたが、週末を狙って台風が来るのは辛いですね。

問題

atcoder.jp

どのようなアプローチで解けばよいかが思いつきにくい問題だと思います。

import sys
import bisect
import collections


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    la = [int(input()) for _ in range(n)]
    result = collections.deque()
    for a in la:
        idx = bisect.bisect_left(result, a)
        if idx == 0:
            result.appendleft(a)
        else:
            result[idx - 1] = a
    print(len(result))


main()

公式解説では広義単調減少部分列の最大の長さを用いていたようですが（流し読みなので違うかもしれません）、今回の解法ではその真逆で狭義単調増加部分列の最少の個数を用います。

まず問題を読み替えると、数列Aを狭義単調増加部分列に分解したときの最少となる個数を求めればよいことになります。これを求めるアルゴリズムは、

  1. 部分列の末尾（つまり部分列の最大値）のソート済みリストを用意する。
  2. 以下をi=1,2,\ldots,Nについて繰り返す。
  3. 1.のリストにA_iより小さい要素が存在するかを二分探索を用いてチェックする。
  4. 存在するならば、その中で最大の要素をA_iに置き換える。
  5. 存在しないならば、リストの先頭に追加する。

このように示すことができ、最終的にリストの要素数が出力すべき値となります。

計算量についてですが、愚直に実装すると最悪計算量はO(N^2)となります。理由としては、通常のリストの先頭に要素を追加する際にはリストの要素数分の計算量が必要になるためです。

そこで上記コードではdequeを用いることで要素の追加に必要な計算量をO(1)に抑えています…が、要素の更新にかかる最悪計算量が要素数（の半分）となるため、結局O(N^2)となってしまうことに後で気付きました。

実際には実行時間が410msと余裕で間に合っているので、厳密に解析すれば計算量はO(N\log N)に抑えられているのかもしれません。例えば要素の更新回数が多い場合は要素の追加が少ないため要素数が少なく、計算量はそれほど大きくならないといった推測ができます。

雑記

  • 通常のリストに対する末尾への要素の追加が計算量O(1)であることを用いれば、上記の解法でも計算量をO(N\log N)に明確に抑えることができます。
    • 例えば、降順のリストに対する二分探索を実装する、A_iの符号をすべて反転させるといった方法が考えられます。

AtCoder ABC 134 D - Preparing Boxes (Python)

競プロ AtCoder ABC134 D問題 400点 Python

irisruneです。とりあえずABC134のD,Eはどうにかなりました。

問題

atcoder.jp

計算量の見積りが大変難しい問題です。また、逆から解くというアプローチが求められます。

import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    bits = [int(e) for e in input().split()]
    ans = set()
    for i in reversed(range(n)):
        for j in range(i + (i + 1), n, i + 1):
            bits[i] ^= bits[j]
        if bits[i] == 1:
            ans.add(i + 1)
    print(len(ans))
    print(*ans)


main()

まず1番目の箱から順にボールが入っているか判定することを考えてみます。例えば、a_i(i\geq1)の排他的論理和を計算するなどして、1番目の箱にボールが入っているかどうかを判定できるか考えてみます。すると、

3
1 0 1

という入力では1番目の箱にボールは入らないですが（3番目のみ入る）、

4
1 0 0 1

という入力では1番目の箱にボールが入ることになります（1,2,4番目に入る）。他には、

5
1 0 0 0 1

という入力では1番目の箱にボールは入らず（5番目のみ入る）、

6
1 0 0 0 0 1

という入力でも1番目の箱にボールは入りません（2,3,6番目に入る）。以上から、これらの場合分けをa_iからそのまま行うのはおそらく不可能と推測できます。

つまり、1番目の箱にボールが入っているかどうかは、1の倍数の書かれた箱（つまり2番目以降すべての箱）にボールが入っているかどうかがわからないと判定できないといえるでしょう。

2番目以降の箱についても同様に考えると、結局N番目の箱から逆順にボールが入っているかどうかを判定するアプローチを取るのがよさそうです。

あとは、i番目の箱にボールが入っているかどうかの判定をiの倍数が書かれた箱にボールが入っているかチェックしながら行うことで愚直に解くことができます。その計算量はO(N/1+N/2+\ldots+N/N)となり高速には見えませんが、

$$ \begin{align} & N/1+N/2+N/3+N/4+N/5+N/6+N/7+\ldots+N/N \\ \leq & N/1+N/2+N/2+N/4+N/4+N/4+N/4+\ldots+(N/2^{\lfloor\log_2N\rfloor}) \\ \leq & N+N+N+\ldots+N \\ = & N\lfloor\log_2N\rfloor \end{align} $$

と計算することができるため結局計算量はO(N\log N)で表せ、十分高速であることがわかります。

ちなみに、上記コードではボールが入るかどうかのフラグ管理をa_iを書き換えることで行っているためアルゴリズムが読み取りにくくなっていると思います。途中計算とは別に出力用にボールが入る箱のセットを用意していたのはいいのですが、途中計算用のリストも別に作った方がよかったですね。

雑記

  • 計算量に真面目に向き合った結果、前回よりも数学要素が強くなった気がします。

AtCoder AGC 036 A - Triangle (python)

競プロ AtCoder AGC036 A問題 400点 Python

irisruneです。Rustはきちんと勉強してから使わないと厳しい言語だと認識したので、しばらく温めることにします。

問題

atcoder.jp

あまりにも数学要素が強い問題ですが、アルゴリズム面でも少々癖があります（というか癖を出してしまいました）。

import sys
LIM = 1000000000


def input():
    return sys.stdin.readline().rstrip()


def main():
    s = int(input())

    x1 = 0 if s == LIM * LIM else 1
    y1 = 0
    x2 = min((s // LIM) + 1, LIM)
    y2 = s % LIM
    x3 = 0
    y3 = LIM
    print(x1, y1, x2, y2, x3, y3)


main()

何はともあれ三角形の面積を求める公式を使わないことには始まりません。座標点でもベクトルでも何でもいいので調べてきて、式変形を駆使してX_1=Y_1=0とおいたときに|X_2Y_3-Y_2X_3|=Sとなることを導き出しましょう。コンテスト当時の検索キーワードは間違いなく大変なことになっていたでしょう。

あとはこの式からX_2,Y_2,X_3,Y_3を求めるだけですが、ここも割と詰まりがちな部分だと思います。

自分が解いた道筋としては、はじめ2のべき乗を用いてビット演算で解こうとしていましたが、制約条件として0\leq X,Y\leq 10^9が設定されていたため、2^{30}=1073741824>10^9を扱うことができず解くことができませんでした。-10^9\leq X,Y\leq 10^9だと勘違いしていたんですね。

そこで、10^9で割ったときの商と剰余に分割して解こうとしましたが、絶対値の中身が和ではなく差であるため、無理やり和の形にしようとした結果上記コードのように少しややこしくなってしまいました。

具体的な方策としては、

  • S=10^{18}のとき、10^9で割った剰余は0となる。
    • そのため、X_1=X_3=0とおくことができる。
  • S\lt10^{18}のとき、10^9で割った商は10^9より小さくなる。
    • このとき、X'_2=X_2-1でX_2を置き換えると、-1\leq X_2\leq 10^9-1である。
    • そのため、X_1=1とおくことでX'_3=-1でX_3を置き換えることができる。
  • あとは10^9で割ったときの商と剰余をX_2,Y_2に、10^9をY_3に代入すればよい。

という形でした。商と剰余の和の形で計算することにこだわった結果、X_1=0という前提を崩したり3項演算子を用いたりと解説に困る形になってしまいましたね。

雑記

  • 今週（先週）はABCもAGCも問題が厳しめな気がします。
  • そろそろまたコンテストに参加したいですね。言語はGoの予定です。