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

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

AGC031 A Colorful Subsequence をKotlinで

irisruneです。皆さんAGC031はどうでしたか?自分は冷えました。

結局コンテストでもKotlinを使うことにしました。今回は1完だったのでA問題について。

atcoder.jp

とりあえず200点ではないですね…300点で少し難しいくらいですかね? なお3WAでした、0WAでも冷えてますが。

fun main(args: Array<String>){
    val len = readLine()!!.toInt()
    val s = readLine()!!
    val lc = mutableListOf<Char>()
    for(i in 0..(len - 1)){
        lc.add(s[i])
    }
    lc.sort()
    var ret = 1L
    var i = 0
    while(i < len){
        val c = lc[i]
        var cnt = 1L
        while(++i < len){
            if(lc[i] != c) break
            cnt++
        }
        ret = (ret * (cnt + 1L)) % 1000000007L
    }
    println(ret - 1)
}

解説にもある通り、各文字種について出てくる文字数をカウントすれば解くことができます。 本来は2^N-1通りになるのが制約条件によって変形して(\text{文字数}+1)^\text{文字種数}-1通りになるわけですね。

ということは例えば、ababaとaabbbのように文字列の順序を変えてしまっても答えは同じになります。 そんなわけで今回は文字列を文字の配列に分解してソートしてから文字数をカウントすることにしました。

一応このコードでも解けるのですが色々な意味でよいアルゴリズムではないと思います。理由は大きく2つあって、

  • 計算量がO(N\log N)かかってしまう。N\leq10^5程度なのでこれでも通るが制約次第では厳しくなる。
    • 一応、N\leq10^7までなら26回走査するよりは速い。それ以上だと26回走査してもダメそう。
  • 文字(の配)列を走査しながら文字種ごとの文字数をカウントするのでインデックスの管理が難しい。
    • 3WAの最大の原因。
      • 10^9+7で割った余りに慣れていなくて、WA出た原因がこの辺にあると勘違いしてたのも敗因。

多分、アルゴリズムとしてよい順に並べると

  • 1回走査しながら文字種をインデックスにしたdictionaryなりmapなりで文字数を管理する。
  • 26回走査してアルファベット26文字の文字数を調べる。
  • 文字列をソートして頭から走査しつつ文字数を調べる(このコード)。

こんな感じになると思うんですよね。それでも解ければいいって主張しても3WAなのが悲しいですね。

アルゴリズムについてはこの辺にしておいて、今回のコードレビューは…

  • コードの簡略化を意識しすぎてインデックスの管理がわかりにくい。

このくらいでしょうか。やっぱりアルゴリズムがよくない

雑記

  • 今回はA問題早解きでもパフォ1400行かないのでB問題を解く必要があったようです。(自信ない人は出ない/提出しないので)AGCは厳しいですね。

  • C問題は順列の意味を履き違えて解けると勘違いしてましたが解けませんでした。重複ありだったら簡単すぎますね…