AtCoder B,C問題をKotlinで解こう - ABC249

当記事ではAtCoder、ABCのB問題ならびにC問題（時々D問題も）のKotlinでの解法を超初心者向けに詳細に解説します。

B - Perfect String

やりたいこと

入力される文字列に対して以下を判定しよう。

• 文字列中に英小文字が現れているかどうか。
• 文字列中に英大文字が含まれているかどうか。
• 文字列中に同じ文字が含まれていないかどうか。

入力値の取得

    val s = readLine()!!

英小文字が含まれているかどうかの判定

文字列中に英小文字が含まれているかどうかを判定する方法は複数ある。ここでは CharRange を使ってみよう。
数値は(0..10) や　(0 until list.size) のような記法で範囲として扱うことができる。ある数値がこの範囲内に入るかどうかを判定したり、整数の場合はfor文で処理したり、Listへ変換することもできる。文字の範囲も同じように扱える。

    // 整数の範囲(IntRange)
    val rng = (1..10)

    // 「1 2 3 4 5 6 7 8 9 10」が出力される
    println(rng.joinToString(" "))

    // 「true」が出力される
    println(3 in rng)

    // 文字の範囲(CharRange)
    val rngc = ('a'..'z')

    // 「a b c d e f g h i j k l m n o p q r s t u v w x y z」が出力される
    println(rngc.joinToString(" "))

    // 「false」が出力される
    println('B' in rngc)

これを使用して文字列中に英小文字が含まれているかどうかを判定しよう。

    if (s.all { it !in 'a'..'z' }) {
        // 文字列sに英小文字が含まれていない
    }

'a'..'z'の部分を'A'..'Z'に置き換えれば、文字列中に英大文字が含まれているかどうかの判定ができる。

    if (s.all { it !in 'A'..'Z' }) {
        // 文字列sに英大文字が含まれていない
    }

文字列中に同じ文字が含まれていないかの判定

文字列をSet<Char>に変換することで、重複が排除される。
文字列中に 同じ文字が含まれていない ならば、文字列の長さとSetに変換した後の要素数は一致する。

    if (s.length != s.toSet().size) {
        // 文字列sに同じ文字列が含まれている
    }

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val s = readLine()!!

    println(if (isPerfect(s)) "Yes" else "No")
}

fun isPerfect(s: String): Boolean {
    if (s.all { it !in 'a'..'z' }) {
        // 文字列sに英小文字が含まれていない
        return false
    }
    if (s.all { it !in 'A'..'Z' }) {
        // 文字列sに英大文字が含まれていない
        return false
    }
    if (s.length != s.toSet().size) {
        // 文字列sに同じ文字列が含まれている
        return false
    }
    return true
}

C - Just K

やりたいこと

Nの最大値が15と少ない。文字列を選ぶ個数は自由なので組み合わせは最大 2^15 = 32768 とやはり多くはない。全ての組み合わせに対して、以下の処理を行おう。

• 'a'から'z'の文字について、組み合わせ中いくつの文字列に出現するかカウントする。
• 最大値を更新する。

全ての組み合わせ

どの文字列が選択されているか、状態は文字列一つにつき、選択されている(on) と 選択されていない(off) の2値、それらが最大15個となる。最大15個の状態を 一つの整数 に保持しよう。

ビットフラグ

各文字列について、0~14のインデックス値を設定する。インデックスを元にフラグ値を設定しよう。

インデックス	フラグ値（整数）	フラグ値（16進数）	フラグ値（2進数）
0	1	0x0001	0000 0000 0000 0001
1	2	0x0002	0000 0000 0000 0010
2	4	0x0004	0000 0000 0000 0100
3	8	0x0008	0000 0000 0000 1000
4	16	0x0010	0000 0000 0001 0000
5	32	0x0020	0000 0000 0010 0000
6	64	0x0040	0000 0000 0100 0000
7	128	0x0080	0000 0000 1000 0000
8	256	0x0100	0000 0001 0000 0000
9	512	0x0200	0000 0010 0000 0000
10	1024	0x0400	0000 0100 0000 0000
11	2048	0x0800	0000 1000 0000 0000
12	4096	0x1000	0001 0000 0000 0000
13	8192	0x2000	0010 0000 0000 0000
14	16384	0x4000	0100 0000 0000 0000
15	32768	0x8000	1000 0000 0000 0000

フラグ値の保持

onになっているフラグの値を組み合わせて整数で保持しよう。
仮に1,2,3のフラグがonになっている場合は以下のフラグ値が格納される

2+4+8 = 14 // (0x000C)(0000 0000 0000 1110)

0,3,5のフラグがonになっている場合は以下のフラグ値が格納される。
1+8+32 = 41 // (0x0029)(0000 0000 0010 1001)
こうすることで 0(全てoff)(0x0000 ,0000 0000 0000 0000）から65535(全てon)(0xFFFF, 1111 1111 1111 1111)まで全てのon/off状態を一つの整数に保持できる。

インデックスをフラグ値に変換

インデックスとフラグ値が以下のような関係になっているならば

インデックス	フラグ値
0	0000 0000 0000 0001
1	0000 0000 0000 0010
2	0000 0000 0000 0100
:	:

以下の方法でインデックス(idx)をフラグ値に変換できる。

    // インデック(idx)をフラグ値に変換する
    val flagValue = 1 shl idx

フラグがonになっているかどうかの判定

フラグがonになっているかどうかの判定は and 演算子を使用しよう。

    // (1,2,3)のフラグがONである場合のフラグ値
    val flag = listOf(1, 2, 3).map { 1 shl it }.sum()

    // 0x0002 + 0x0004 + 0x0008 = 0x000C で 14 が出力される
    println(flag)

    val f01 = 1 shl 1 // 1 の フラグ値 0x0002
    val f04 = 1 shl 4 // 4 の フラグ値 0x0010

    // 1のフラグがONになっているので true が出力される
    println(flag and f01 != 0)

    // 4のフラグがONになっっていないので false が出力される
    println(flag and f04 != 0)

これらを使って実装していこう。

ビットフラグに関しては以下の記事が分かりやすくまとまっていますので、併せて参照することをお勧めします。
ビットをどう使うかよく判らない人へ

入力値の取得

    // 入力値の取得
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val s = (1..n).map { readLine()!! }

全てが選択された（onになっている）フラグ値の取得

    // フラグが全てonになった場合のフラグ値
    val fullFlag = (0 until n).map { 1 shl it }.sum()

2進数で1~n-1桁目が1になっている状態は、さらに1を足すとn桁目が1となり、それ以外の桁は0となります。従って以下のように書くこともできます。今回は分かりやすさ重視で0~n-1のインデックスをフラグ値に変換し合計して実装しましたが、下記の方がスマートな実装です。

    // フラグが全てonになった場合のフラグ値
    val fullFlag = (1 shl n) - 1

0~fullFlagでループを回せば、全ての組み合わせに対する処理が可能になる。

    // フラaグが全てonになった場合のフラグ値
    val fullFlag = (0 until n).map { 1 shl it }.sum()

    // 全ての組み合わせに対する処理
    for (i in 0..fullFlag) {
        //:TODO 文字列リストの内、選ばれたもの（フラグがONになっているもの）を抽出
        //:TODO すべての英文字のうち、選ばれた文字列リスト中に出現する個数がk個のものをカウント
        //:TODO 最大値の更新
    }

フラグがONになっているものの抽出

文字列リストsの内、選ばれたもの（フラグがONになっているもの）を抽出しよう。
文字列リストsの各要素のインデックスをフラグに変換して、iに含まれるかどうかで判定しよう。

    // 全ての組み合わせに対する処理
    for (i in 0..fullFlag) {
        // 文字列リストの内、選ばれたもの（フラグがonになっているものを）抽出する
        val selected = s.indices.filter { i and (1 shl it) != 0 }.map { s[it] }

        //:TODO すべての英文字のうち、選ばれた文字列中に出現する個数がk個のものをカウント
        //:TODO 最大値の更新
    }

全ての英小文字に対するカウント

すべての英小文字のうち、選ばれた文字列中に出現する個数がk個のものをカウントしよう。
すべての英小文字に対する処理はB - Perfect String 英小文字が含まれているかどうかの判定に登場する CharRange を使おう。

    // 選ばれた文字列中、文字が出現する個数＝K個のものの最大値
    var maxCount = 0

    // 全ての組み合わせに対する処理
    for (i in 0..fullFlag) {

        // 文字列リストの内、選ばれたもの（フラグがonになっているものを）抽出する
        val selected = s.indices.filter { i and (1 shl it) != 0 }.map { s[it] }
 

       // 全ての英小文字のうち、選ばれた文字列中に出現する個数がk個のものをカウント
        val count = ('a'..'z').count { chr -> selected.count { chr in it } == k }
        // 最大値の更新
        maxCount = Math.max(maxCount, count)
    }

サンプルコード

main.kt

fun main(args: Array<String>) {

    // 入力値の取得
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val s = (1..n).map { readLine()!! }

    // フラグが全てonになった場合のフラグ値
    val fullFlag = (0 until n).map { 1 shl it }.sum()

    // 選ばれた文字列中、文字が出現する個数＝K個のものの最大値
    var maxCount = 0

    // 全ての組み合わせに対する処理
    for (i in 0..fullFlag) {

        // 文字列リストの内、選ばれたもの（フラグがonになっているものを）抽出する
        val selected = s.indices.filter { i and (1 shl it) != 0 }.map { s[it] }
        // 全ての英小文字のうち、選ばれた文字列中に出現する個数がk個のものをカウント
        val count = ('a'..'z').count { chr -> selected.count { chr in it } == k }
        // 最大値の更新
        maxCount = Math.max(maxCount, count)
    }

    println(maxCount)
}