AtCoder Beginner Contest 278 A～Dのメモ

AtCoder Beginner Contest 278に参加したので記録を残しておきます。
https://atcoder.jp/contests/abc278

A - Shift

問題文の通りの操作を実際に行えばいいです。

fun main() {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }.toMutableList()

    for(i in 0 until k) {
        a.removeAt(0)
        a.add(0)
    }
    println(a.joinToString(" "))
}

removeAtに渡している0は添字としての0、addに渡している0は値としての0なので混乱しそうですが。
MutableListのremoveAtはたぶん削除した分を埋めるようにずれる処理が発生するので$O(N)$かかると思いますが、制約が小さいので問題ありません。

B - Misjudge the Time

日付操作なので標準ライブラリに任せるべきではと思いつつ、どのライブラリをどう使えばいいのかパッと思い浮かばなかったので、サクッと整数の操作でやってしまえと思って実装しました。
その結果、あれこれバグらせて時間を無駄にしました。しかも問題文の解釈が甘くてWAを出しました。おバカです。

import java.util.Collections

fun main() {
    var (h, m) = readLine()!!.split(" ").map { it.toInt() }

    while (true) {
        val clock = toClock(h, m)
        if(mayBeConfuse(clock)) {
            println("$h $m")
            return
        }

        m++
        if(m == 60) {
            h++
            m = 0
        }
        if(h == 24) {
            h = 0
        }
    }
}

fun toClock(h: Int, m: Int): List<Char> {
    val sh = h.toString().padStart(2, '0')
    val sm = m.toString().padStart(2, '0')

    return sh.toList() + sm.toList()
}

fun mayBeConfuse(clock: List<Char>): Boolean {
    val copyClock = clock.toMutableList()
    Collections.swap(copyClock, 1, 2)

    if(copyClock[0].minus('0') !in 0..2) {
        return false
    }

    if(copyClock[0].minus('0') == 2) {
        if(copyClock[1].minus('0') !in 0..3) {
            return false
        }
    }

    if(copyClock[2].minus('0') !in 0..5) {
        return false
    }

    return true
}

基本的な考え方としては、時計を表す配列を作って実際に入れ替えて、入れ替え後が日付としてあり得る値かどうかを判定します。それをHとMを増やしながら全部調べます。配列は二次元にする必要が特にないので一次元配列です。

Hが23を超えたら一巡して0に戻す必要がありますが、それを見落としていてWAをもらいました。

C - FF

各操作を定数時間くらいで行う必要があります。

単純にフォローしているかどうかのフラグを配列で持てばいいと思って、二次元配列でバケットを実装しました。可変長配列で追加したり削除したりだと間に合わないので、フラグを全部falseで初期化しておいて添字で操作をすれば定数時間で操作できます。
しかし、Nが大きい場合にREになりました。たぶんメモリ不足です。まあ、そりゃそうか…

なので必要が生じた分だけフラグを持つように連想配列に書き換えて提出したのが以下です。

import java.io.PrintWriter

fun main() {
    val (n, q) = readLine()!!.split(" ").map { it.toInt() }
    val br = System.`in`.bufferedReader()

    val table = mutableMapOf<Int, MutableMap<Int, Boolean>>()

    val out = PrintWriter(System.out)
    repeat(q) {
        val (t, a, b) = br.readLine()!!.split(" ").map { it.toInt() }
        if(!table.containsKey(a)) {
            table[a] = mutableMapOf()
        }
        if(!table.containsKey(b)) {
            table[b] = mutableMapOf()
        }
        when (t) {
            1 -> {
                table[a]!![b] = true
            }
            2 -> {
                table[a]!![b] = false
            }
            3 -> {
                if(table[a]?.get(b) != null && table[a]?.get(b)!! && table[b]?.get(a) != null && table[b]?.get(a)!!) {
                    out.println("Yes")
                } else {
                    out.println("No")
                }
            }
        }
    }
    out.flush()
}

これで一応通ったのですが、そもそもフラグとかじゃなくてフォローしている人をSetで保持すればよくない？って思いました…
真っ先にフラグを持つことを連想してしまって、それに囚われていました。

Setを使うように書き換えたのが以下です。だいぶマシなコードになりました。

import java.io.PrintWriter

fun main() {
    val (n, q) = readLine()!!.split(" ").map { it.toInt() }
    val br = System.`in`.bufferedReader()

    val table = mutableMapOf<Int, MutableSet<Int>>()

    val out = PrintWriter(System.out)
    repeat(q) {
        val (t, a, b) = br.readLine()!!.split(" ").map { it.toInt() }
        if(!table.containsKey(a)) {
            table[a] = mutableSetOf()
        }
        if(!table.containsKey(b)) {
            table[b] = mutableSetOf()
        }
        when (t) {
            1 -> {
                table[a]!!.add(b)
            }
            2 -> {
                table[a]!!.remove(b)
            }
            3 -> {
                if(table[a]!!.contains(b) && table[b]!!.contains(a)) {
                    out.println("Yes")
                } else {
                    out.println("No")
                }
            }
        }
    }
    out.flush()
}

計算量の考慮が必要っちゃ必要だけど、標準ライブラリにある優れたデータ構造を使うだけでした。
ハッシュテーブルは偉大です。

D - All Assign Point Add

普段はC問題が解ければ満足なのですが、今回はグダりつつもCを解いた時点でそれなりに時間が残っていたのでDも見てみることに。

これもCと同じようなクエリを処理する問題です。やはり各処理を定数時間くらいで処理する必要があります。
普通に操作を実行すると、1の全要素に代入が線形時間かかりそうなのでダメです。
3の出力の時点で正しければそれでいいので、1と2の時は記録だけしておいて、3の時に計算すればよさそうです。

1の代入する値は全要素で共通なので、単一の数値として保持します。
若干面倒なのは2で、特定の要素にだけ加算しますので、どの要素に対していくつ加算するのかを連想配列とかで持つ必要があります。
また、1が実行されると2の加算が上書きされて無意味になりますので、1が実行されたら連想配列をクリアする必要があります。

3が実行されたら、1で保持した値と2で保持した値を加算して出力します。ただ、3を実行する前に1や2が実行されていない可能性もあるので、それに対する考慮も必要です。
1が実行されていなければ、「1で保持した値」ではなくAで保持している元の値に加算します。
2が実行されていなければ何も加算しなければいいです。

import java.io.PrintWriter

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toLong() }
    val q = readLine()!!.toInt()

    val br = System.`in`.bufferedReader()

    val out = PrintWriter(System.out)

    var x1 = -1L
    val x2 = mutableMapOf<Int, Long>()
    var updated = false
    repeat(q) {
        val query = br.readLine()!!.split(" ").map { it.toInt() }
        if(query[0] == 1) {
            updated = true
            x1 = query[1].toLong()
            x2.clear()
        } else if(query[0] == 2) {
            val i = query[1] - 1
            val x = query[2]

            if(!x2.containsKey(i)) {
                x2[i] = 0L
            }

            x2[i] = x2[i]!! + x.toLong()
        } else if(query[0] == 3) {
            val i = query[1] - 1

            if(updated) {
                out.println(x1 + (x2[i] ?: 0L))
            } else {
                out.println(a[i] + (x2[i] ?: 0L))
            }
        }
    }

    out.flush()
}

1が一度でも実行されたかどうかをupdatedというフラグで管理していますが、x1について入力としてあり得ない値（-1）で初期化しているので、それを元に判定すればフラグはなくてもよかったですかね。

いずれの操作も定数時間でできるのでちゃんと通りました。
ハッシュテーブルは偉大です。

感想

たぶん普段よりは難しくなかったのだとは思いますが、本番中にD問題が解けたのと、4完は初めてでした。やっぱり解けると嬉しいです。