Leverage Copy

メモの公開場所

Codeforces Round No.609 Div.2 参加記録 (A〜D解答)

青になれました!やったね!

f:id:maguroguma:20191222030152p:plain

思ったより長い戦いだった。。

Codeforcesの青はAtCoderの水色」ぐらいの言説を見た気がするので、 「まぁ青ぐらいなら楽勝だろう」と思ったのですが、想像の3倍ぐらいは難しかったです。

多分青を維持するのは今の自分にはきつくて、 Codeforcesの1600はAtCoderの1400(水色の真ん中)ぐらいなんだろうなぁと感じています。

とはいえ、ミスは減ってきて実装力も向上しているとは思うので、 今後もしばらくはこの調子で頑張りたいところです。

A. Equation

問題のURL

解答

式変形すると a = n + b であるため、小さい方である b が決まれば a も自然と決まる。 そして、 a, b がともに合成数になるようにする。

2 以外の偶数はすべて合成数であることを踏まえると、

  1. n が偶数ならば、 b を適当な 2 以上の偶数とすれば n + b も当然 2 以上の偶数となる。
  2. n が奇数ならば、 b を適当な合成数である奇数とすれば n + b2 以上の偶数となる。

であり、 a, b を選択できる。

var n int

func main() {
    n = ReadInt()

    if n%2 == 0 {
        b := 4
        a := n + b
        fmt.Println(a, b)
    } else {
        b := 9
        a := n + b
        fmt.Println(a, b)
    }
}

こんな問題に9分もかかってしまいました。

というより、公式Editorialを見ると、「9*n, 8*n でOK」とのこと、たしかに。

こどふぉのDiv2のA問題って、 O(1) 算数をしないといけなかったり、真面目に全探索しないといけなかったりで、 なかなか難しいです。

簡単と思える日が来てほしい。

B. Modulo Equality

問題のURL

解答

A, B それぞれについて、登場する値のカウントをメモしておく。

答えが x のとき、すべての A[i] に対して、 (AにおけるA[i]の個数) == (Bにおける(b = (A[i] + x) % m)の個数) となっている必要がある。

よって、このような x としてあり得るものをすべて列挙し、 それが条件を満たすか確かめれば良い。 ただし、求められている x は条件を満たす最小のものであるため、見つけるたびに小さい方で更新する。

x としてありうるものは、ある適当な A の値(以下のコード中では A[0] としている)を取り出し、 これが B のどの要素に遷移するのか?を考えることで列挙できる。

また、各 x に対して、すべての A の要素の遷移先の個数が、 A の遷移前の個数と一致するかをチェックすれば良い。

以上より、トータルの計算量は O(n^2) となり、十分高速である。

var n, m int
var A, B []int

func main() {
    n, m = ReadInt2()
    A = ReadIntSlice(n)
    B = ReadIntSlice(n)

    amemo, bmemo := make(map[int]int), make(map[int]int)
    for i := 0; i < n; i++ {
        amemo[A[i]]++
        bmemo[B[i]]++
    }

    ans := -1
    aval, anum := A[0], amemo[A[0]]
    for bval, bnum := range bmemo {
        if anum != bnum {
            continue
        }

        var x int
        if bval > aval {
            x = bval - aval
        } else {
            x = bval + m - aval
        }

        isOK := true
        for av, an := range amemo {
            bv := (av + x) % m
            bn := bmemo[bv]
            if an == bn {
                continue
            } else {
                isOK = false
                break
            }
        }

        if isOK {
            if ans == -1 {
                ans = x
            } else {
                ChMin(&ans, x)
            }
        }
    }

    if ans == m {
        ans = 0
    }

    fmt.Println(ans)
}

A[i], B[i] の範囲が 10^9 なので固定長配列ではなく辞書を使う必要があるわけですが、 あまり慣れていない操作だったので時間がかかってしまいました。

そろそろこどふぉも100問弱ぐらいACしているはずですが、まだまだ足りてないなぁと感じます。

C. Long Beautiful Integer

問題のURL

解答

自由が効くのは最初の k 桁までであり、以降の桁は k 桁までの設定に従属する。

できるだけ小さいBeautifulな数値を作ろうとすると、 貪欲に上の桁から A の桁をコピーする必要があるため、まずはそのように桁を埋めていく。

このようにして出来る数値が A 以上であるならば、それが答えとなる。

もし A 未満となってしまう場合は、自由が効く桁の一番下の桁、すなわち k 桁目から微調整することを考える。

k 桁目までは A のコピーになっているため、できるだけ下の方の桁で +1 できれば良い (必ず A よりも大きくなる)。 ただし、注目桁が 9 である場合は繰り上がりを考える必要がある。 その場合は、 9 の桁を 0 にした後、上の桁に移動してその桁の数字を +1 することを再考する。

1桁でも変更ができたらその時点で終了し、出来上がった数を出力すれば良い。

k 桁目までを変更する際は、下の方の桁も合わせて修正する必要があることには注意する。

var n, k int
var A []rune

func main() {
    n, k = ReadInt2()
    A = ReadRuneSlice()

    isBeau := true
    for i := 0; i < n; i++ {
        if i+k < n {
            if A[i] != A[i+k] {
                isBeau = false
                break
            }
        } else {
            break
        }
    }
    if isBeau {
        fmt.Println(len(A))
        fmt.Println(string(A))
        return
    }

    B := make([]rune, n)
    for i := 0; i < n; i++ {
        B[i] = 'x'
    }

    // iは起点
    for i := 0; i < k; i++ {
        digit := A[i]

        // jは飛び飛び
        for j := i; j < n; j += k {
            B[j] = digit
        }
    }

    isSmall := false
    for i := 0; i < n; i++ {
        if A[i] == B[i] {
            continue
        } else if A[i] < B[i] {
            break
        } else {
            isSmall = true
            break
        }
    }
    if !isSmall {
        fmt.Println(len(B))
        fmt.Println(string(B))
        return
    }

    // 大きくなるように正しく調整する
    for i := k - 1; i >= 0; i-- {
        if B[i] == '9' {
            // iからk飛びで0に更新
            for j := i; j < n; j += k {
                B[j] = '0'
            }
        } else {
            // iからk飛びで更新
            for j := i; j < n; j += k {
                B[j]++
            }
            break
        }
    }

    fmt.Println(len(B))
    fmt.Println(string(B))
}

桁DPでよくやる考え方の基本、という感じがしました。

多分、最初の部分の「A がすでにBeautifulかどうか?」の判定は要らないと思います。

桁数を出力するのを忘れて1WA、 isSmall の判定部分でバグっており2WAしてしまい、 もったいないことをしてしまいました。

実装がちょっと長くなってくるとこういったミスが増えてくるので、 なにか対策を考えます。

D. Domino for Young

問題のURL

解答

わからなかったため、公式Editorialの手法をなぞりました。

与えられたヤング図形市松模様(チェッカーフラグ)のように塗ります。

その時の黒と白の数を数えて、小さい方が答えです。

小さい方の色を仮に黒とすると、黒は隣接する白とで1つのドミノによって専有され、 また、すべての未使用の黒は未使用の白とペアにすることができるため、とのこと。

賢い(けど、上の説明はちょっと大雑把すぎるかもしれないです)。

var n int
var A []int64
var b, w int64

func main() {
    n = ReadInt()
    A = ReadInt64Slice(n)

    b, w = 0, 0
    for i := 0; i < n; i++ {
        l := A[i]
        if i%2 == 0 {
            // Bから塗り始める
            b += (l + (2 - 1)) / 2
            w += l / 2
        } else {
            // Wから塗り始める
            w += (l + (2 - 1)) / 2
            b += l / 2
        }
    }

    fmt.Println(Min(b, w))
}

青になれて嬉しい気持ちはありますが、目標はまだまだ上に持てているので、 引き続き頑張っていく所存です。

Educational Codeforces Round No.78 参加記録 (A〜C解答)

いつもの自分だったらBの算数で詰まって終了だったので、 成長を喜びたいところ。

A. Shuffle Hashing

問題のURL

解答

ハッシュ文字列からパスワード分の長さの分だけ文字列を切り出して調べる、というのを全探索すれば良い。

切り出した部分とパスワードが一致するかどうかの判定は、文字配列をソートして 文字列として一致するかどうかを調べるのが簡単(だと思う)。

var t int
var P, H []rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        P, H = ReadRuneSlice(), ReadRuneSlice()

        solve()
    }
}

func solve() {
    if len(P) > len(H) {
        fmt.Println("NO")
        return
    }

    pL := RuneList{}
    for i := 0; i < len(P); i++ {
        pL = append(pL, P[i])
    }
    sort.Sort(pL)

    plen := len(P)
    for i := 0; i < len(H); i++ {
        if i+plen > len(H) {
            break
        }

        tmp := H[i : i+plen]
        hL := RuneList{}
        for j := 0; j < len(tmp); j++ {
            hL = append(hL, tmp[j])
        }
        sort.Sort(hL)

        if string(pL) == string(hL) {
            fmt.Println("YES")
            return
        }
    }

    fmt.Println("NO")
}

type RuneList []rune

func (a RuneList) Len() int           { return len(a) }
func (a RuneList) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a RuneList) Less(i, j int) bool { return a[i] < a[j] }

ハッシュからパスワードを切り出す全探索の部分がコーディングに時間かかりすぎてしまっていたので、 ちょっと良くないですね。 どうしよう。

B. A and B

問題のURL

解答

2つの数 a, b を等しくするためには、最終的に2数の差 diff = abs(a-b) を埋める必要がある。

必要な操作回数を k 回としたときに、2つの数に加える数値の総和は k*(k+1)/2 である。 よって、この総和を2つの数に分割して、その2つの数の差が diff とすることができるのかを考える。

総和は好きなように分割できる一方で、分割した2つの数の差の偶奇は1種類のみである。

例: sum == 6 のとき (0, 6), (1, 5), (2, 4), (3, 3) が分割の全パターンで、2つの数の差はすべて偶数となる。

以上から、 k を小さいところから全探索して、 diff%2 == sum%2 && diff <= sum を満たすものを見つければ良い。

総和の形から1テストケースあたりの計算量は O(Sqrt(Max(a, b))) なので間に合う。

var t int
var a, b int64

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        a, b = ReadInt64_2()

        solve()
    }
}

func solve() {
    diff := AbsInt(a - b)

    if diff == 0 {
        fmt.Println(0)
        return
    }

    for k := int64(1); ; k++ {
        sum := k * (k + 1) / 2

        if diff%2 == sum%2 && diff <= sum {
            fmt.Println(k)
            return
        }
    }
}

総和は好きなように分割できる一方で、分割した2つの数の差の偶奇は1種類のみである。

これって自明ですかね? 私は紙に色々書いているうちに「それはそうだ」と納得できる、ぐらいなんですが。

C. Berry Jam

問題のURL

解答

以下の図に示すように、いちごとブルーベリーそれぞれを 1, -1 に変換する(RはいちごでBはブルーベリー)。

f:id:maguroguma:20191221150527j:plain
与えられた情報のエンコーディング

ここで、与えられた配列の真ん中で分割する。 扱いやすくするため、食べられる順番に従うように、左側については元の配列の内側から並ぶように、配列を構築する。

この2つの配列に対して、累積和を考える。 このようにすると、問題は「左の累積和から1つ、右の累積和から1つ数を選んで、全体の合計と等しくなるようにせよ」 と読み替えることができる。 また、答えは左のインデックス、右のインデックスの和が小さいほど望ましい。

このように考えると、それぞれの配列についてある累積和を取るインデックスは、その最小のもののみに興味があるといえる (同じ数の累積和というのは、食べ残ったRとBの数の差が同じであり、等価であると言えるから(DPっぽい考え方))。

以下の実装では、それぞれの累積和に対する最小のインデックスを、左右の配列分それぞれ辞書で用意した (負数もまとめて入れたかったため)。

あとは、あり得る和のパターンの全探索を、左配列基準および右配列基準で2スキャンして、ベストなものを見つける。

var t int
var n int
var A []int

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        n = ReadInt()
        A = ReadIntSlice(2 * n)

        solve()
    }
}

func solve() {
    E := make([]int, len(A))
    for i := 0; i < len(A); i++ {
        if A[i] == 2 {
            E[i] = -1
        } else {
            E[i] = 1
        }
    }
    sum := Sum(E...)

    if sum == 0 {
        fmt.Println(0)
        return
    }

    if sum < 0 {
        for i := 0; i < len(E); i++ {
            E[i] = -E[i]
        }
    }
    sum = Sum(E...)

    R, L := []int{}, []int{}
    for i := n - 1; i >= 0; i-- {
        L = append(L, E[i])
    }
    for i := 1; i < n; i++ {
        L[i] += L[i-1]
    }
    for i := n; i < 2*n; i++ {
        R = append(R, E[i])
    }
    for i := 1; i < n; i++ {
        R[i] += R[i-1]
    }

    leftMemo, rightMemo := make(map[int]int), make(map[int]int)
    leftMemo[0], rightMemo[0] = -1, -1
    for i := 0; i < n; i++ {
        a := L[i]
        if _, ok := leftMemo[a]; ok {
            continue
        } else {
            leftMemo[a] = i
        }
    }
    for i := 0; i < n; i++ {
        a := R[i]
        if _, ok := rightMemo[a]; ok {
            continue
        } else {
            rightMemo[a] = i
        }
    }

    ans := INF_BIT30
    for lv := 0; lv <= sum; lv++ {
        rv := sum - lv
        lidx, lok := leftMemo[lv]
        ridx, rok := rightMemo[rv]
        if lok && rok {
            ChMin(&ans, lidx+ridx+2)
        }
    }
    for rv := 0; rv <= sum; rv++ {
        lv := sum - rv
        lidx, lok := leftMemo[lv]
        ridx, rok := rightMemo[rv]
        if lok && rok {
            ChMin(&ans, lidx+ridx+2)
        }
    }
    fmt.Println(ans)
}

コンテスト後に時間を使って自分で考えた方法ですが、良い解法なのかはわかりません。 正直変換手数も多くてなんかまどろっこしい気がします。 editorialが公開された上で、模範解答が面白ければ、そちらも追記するかもしれません。


今回はなんとかイーブンに持ち込めました。

なんとか粘って今年の残りあと3回のこどふぉで青に持ち込みたいところです。

Codeforces Round No.608 (Div.2) 参加記録 (A〜C解答)

※Dはちょっと難しそうなので手を付けるのは当分先になりそうですが、 Eがシンプルな見た目で面白そうだったため、近々追記するかもしれません。

A. Suits

問題のURL

解答

2つのセットでジャケットが共通しており、ほかは独立している。 セットに組み込まれるアイテムはすべて1つずつであるため、 ジャケットはできるだけ高いセットで先に使ってしまい、 作れなくなったら、他方の安い方をできる限り作れば良い。

var a, b, c, d, e, f int

func main() {
    a, b, c, d = ReadInt4()
    e, f = ReadInt2()

    bc := Min(b, c)

    ans := 0
    if e > f {
        // aの方を使う
        m := Min(a, d)
        ans += e * m
        d -= m
        if d > 0 {
            mm := Min(bc, d)
            ans += f * mm
        }
    } else {
        // bcの方を使う
        m := Min(bc, d)
        ans += f * m
        d -= m
        if d > 0 {
            mm := Min(a, d)
            ans += e * mm
        }
    }

    fmt.Println(ans)
}

これもDiv.2のAの中では大分簡単な方な気がします。

B. Blocks

問題のURL

解答

初期の個数が偶数のものを反転させれば良い。

なぜなら、2つのブロックを反転させるとき、反転させて個数をゼロにしたい方の色のブロックの個数は、

  1. 2個減る
  2. 変わらない(1個減って1個増える)

のいずれかであることから、依然として偶数のままとなる。

最終的に選んだ色を0個にしなければならないことを考えると、 初期の個数が偶数の方しか選ぶことが出来ない。

具体的な反転回数については、左から愚直に選んだ色を反転させるようにすればよく、 高々 n 回で十分である。

var n int
var S []rune

func main() {
    n = ReadInt()
    S = ReadRuneSlice()

    // 最初から全部いっしょならOK
    memo := make(map[rune]int)
    memo['B'] = 0
    memo['W'] = 0
    for i := 0; i < n; i++ {
        memo[S[i]]++
    }
    if memo['B'] == n || memo['W'] == n {
        fmt.Println(0)
        return
    }

    // BもWも奇数なら無理
    if memo['B']%2 == 1 && memo['W']%2 == 1 {
        fmt.Println(-1)
        return
    }

    answers := []int{}
    if memo['B']%2 == 0 {
        // BをWにする
        for i := 0; i < n-1; i++ {
            if S[i] == 'B' {
                answers = append(answers, i+1)
                S[i] = 'W'
                S[i+1] = rev(S[i+1])
            }
        }
    } else {
        // WをBにする
        for i := 0; i < n-1; i++ {
            if S[i] == 'W' {
                answers = append(answers, i+1)
                S[i] = 'B'
                S[i+1] = rev(S[i+1])
            }
        }
    }

    fmt.Println(len(answers))
    fmt.Println(PrintIntsLine(answers...))
}

func rev(r rune) rune {
    if r == 'B' {
        return 'W'
    } else {
        return 'B'
    }
}

結構似たような問題は解いた気がするのに、かなり時間がかかってしまいました。

精進不足。

C. Shawarma Tent

問題のURL

解答

よくよく考えると、学校の1マス左・右・下・上のいずれかにテントを配置するのが最適です。

それぞれに配置した場合の、買い食いを行う可能性のある生徒の数を数え、 最大となるものを選べばよいです。

var n int
var sx, sy int
var X, Y []int

func main() {
    n = ReadInt()
    sx, sy = ReadInt2()

    X, Y = make([]int, n), make([]int, n)
    for i := 0; i < n; i++ {
        x, y := ReadInt2()
        X[i], Y[i] = x, y
    }

    l, r, u, d := 0, 0, 0, 0
    for i := 0; i < n; i++ {
        x, y := X[i], Y[i]

        if x <= sx-1 {
            l++
        }
        if x >= sx+1 {
            r++
        }
        if y <= sy-1 {
            d++
        }
        if y >= sy+1 {
            u++
        }
    }

    maxi := Max(l, r, u, d)
    fmt.Println(maxi)
    if l == maxi {
        fmt.Println(sx-1, sy)
    } else if r == maxi {
        fmt.Println(sx+1, sy)
    } else if d == maxi {
        fmt.Println(sx, sy-1)
    } else {
        fmt.Println(sx, sy+1)
    }
}

コンテスト中に通した解法では、片方の軸を学校に合わせれば良いということしか気づけず、 素直に区間で一番重なりが多い部分を求めるべく、家の位置のソート・ランレングス圧縮・累積和とかいう、 闇の深いコードを書いてしまいました(なぜ通ったのか)。

問題文がいかついと複雑に考えてしまうような気がするので、もうちょっと冷静に問題を俯瞰したいところです。

Codeforces Round No.607 (Div.2) 参加記録 (A〜D解答)

A. Suffix Three

問題のURL

解答

よくよく見ると末尾の2文字だけを見れば判定できるので、そこだけを見れば良い。

var t int
var S []rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        S = ReadRuneSlice()

        solve()
    }
}

func solve() {
    n := len(S)
    str := S[n-2:]
    if string(str) == "po" {
        fmt.Println("FILIPINO")
    } else if string(str) == "su" {
        fmt.Println("JAPANESE")
    } else {
        fmt.Println("KOREAN")
    }
}

ここまで簡単なAはDiv.3でも見たことがないので新鮮でした。

B. Azamon Web Services

問題のURL

解答

1回までの入れ替えを許可されている文字列 S について、辞書順最小のものを求める。 それが C よりも辞書順で小さければ、それを出力すれば良い。 それが C よりも辞書順で大きいのならば、impossibleである。

O(n^2) が許される制約なので、愚直に考える。

できるだけ小さい文字をできるだけ前方に配置するのが良いので、 探索開始位置を先頭から末尾に1ずつ移動させていき、チェック位置の文字よりも小さいものが、 末尾までに存在すればそれと入れ替えるようにする。

ただし、最小のものが複数ある場合は、できる限り後の物を選ぶ必要があることに注意する。

var t int
var S, C []rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        S = ReadRuneSlice()
        C = ReadRuneSlice()

        solve()
    }
}

const impossible = "---"

func solve() {
    n := len(S)
    lidx, ridx := -1, -1
    for i := 0; i < n; i++ {
        midx, minc := 5005, rune(100)
        // できるだけ後方から最小の文字を見つける
        for j := n - 1; j >= i+1; j-- {
            if minc > S[j] {
                midx, minc = j, S[j]
            }
        }

        if minc < S[i] {
            lidx, ridx = i, midx
            break
        }
    }

    if lidx == -1 && ridx == -1 {
        if string(S) < string(C) {
            fmt.Println(string(S))
        } else {
            fmt.Println(impossible)
        }
        return
    }

    S[lidx], S[ridx] = S[ridx], S[lidx]

    if string(S) < string(C) {
        fmt.Println(string(S))
    } else {
        fmt.Println(impossible)
    }
}

最初、最小のものを前から選ぶようなコードを書いてしまい、pretest2でWAしてしまって頭を抱えてしまいました。

何気なく WAWA という文字列を考えてたら(某プロゲーマーが浮かんだのかWAに怯えたのかは不明) 間違いに気づけたので良かったですが、 偶然以外何者でもないので、もう少し簡単なものでもいいから文字列問題に取り組むべきだなぁと思いました。

C. Cut and Paste

問題のURL

解答

x の値が初期状態の S の長さ以下であるときは素直にシミュレーションができる。

なぜなら、カットのあとすぐ行われるペーストは、切り出したものを少なくとも1回はペーストすることになるため、 x 文字目までは連続部分文字列が変わらず、長さだけに集中すれば良いからである。

ここで、 x の制約が 10^6 までであることを踏まえると、 S の長さが x に達するまでは文字列連結が必要だが、それ以降は不要となる。

後は実装を頑張るだけである。

var t int
var x int64
var S []rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        x = ReadInt64()
        S = ReadRuneSlice()

        solve()
    }
}

var ans int64
var clip int64

func solve() {
    ans = int64(len(S))
    clip = 0

    for i := int64(0); i < x; i++ {
        c := int64(S[i] - '0')
        cut := S[i+1:]

        clip = NegativeMod(ans-(i+1), MOD)
        clip %= MOD
        ans += (c - 1) * (clip)
        ans %= MOD

        // 長さが十分だったらそれ以上は連結しない
        if int64(len(S)) < x {
            // 最大c-1回分追加で連結する
        OUTER:
            for j := int64(0); j < c-1; j++ {
                for k := 0; k < len(cut); k++ {
                    S = append(S, cut[k])

                    // x以上になったら連結しない
                    if int64(len(S)) >= x {
                        break OUTER
                    }
                }
            }
        }
    }

    fmt.Println(ans)
}

// NegativeMod can calculate a right residual whether value is positive or negative.
func NegativeMod(val, m int64) int64 {
    res := val % m
    if res < 0 {
        res += m
    }
    return res
}

添字が読みづらくて題意を把握するのに時間がかかってしまいました。

最近活用し始めましたが、Goのラベル付きfor文は競技プログラミングでは結構便利ですね (実開発では闇雲に使うと怒られそうですが)。

D. Beingawesomeism

問題のURL

解答

問題文がえげつないが、要はサンプル等で示された動きで A で塗りつぶしたい、ということ。

以下の図のように、1マスでも A が存在すればせいぜい4回の動作で塗りつぶしが可能となることを踏まえる。

f:id:maguroguma:20191218014546j:plain
必要な移動回数のイメージの素

少ない回数ほど条件は厳しいと考えられるので、 0, 1, 2, 3, 4回それぞれを図示して考えていく。

f:id:maguroguma:20191218014621j:plain
主要な場合分け

まず、図示していないが、全てが P の場合はimpossibleである。 また、すべてが A の場合は当然0回である。

次に、1回で済む場合を考えると、これは端っこの列もしくは行がすべて A のときである。 反対側へ向かう1回の移動で塗りつぶしが可能となる。

次に、2回で済む場合は、四隅のいずれかが A である場合と、 ある行もしくはある列についてすべてが A の場合である。 図に示す矢印の方向に移動を行えば、塗りつぶしが可能であることがわかる。

最後に、四隅を除いた端っこの行もしくは列に A が1文字でも存在すれば、3回の移動で済む。

いずれにも当てはまらない場合は、はじめの図に示したような4回の移動が必要となる。

var t int
var r, c int
var S [][]rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        r, c = ReadInt2()
        S = [][]rune{}
        for i := 0; i < r; i++ {
            row := ReadRuneSlice()
            S = append(S, row)
        }

        solve()
    }
}

func solve() {
    anum := 0
    for i := 0; i < r; i++ {
        for j := 0; j < c; j++ {
            if S[i][j] == 'A' {
                anum++
            }
        }
    }
    if anum == 0 {
        fmt.Println("MORTAL")
        return
    }
    if anum == r*c {
        fmt.Println(0)
        return
    }

    if subRow(0) || subRow(r-1) || subCol(0) || subCol(c-1) {
        fmt.Println(1)
        return
    }

    b := false
    for i := 1; i < r-1; i++ {
        b = b || subRow(i)
    }
    for i := 1; i < c-1; i++ {
        b = b || subCol(i)
    }
    if b {
        fmt.Println(2)
        return
    }
    if S[0][0] == 'A' || S[0][c-1] == 'A' || S[r-1][0] == 'A' || S[r-1][c-1] == 'A' {
        fmt.Println(2)
        return
    }

    b = false
    for i := 1; i < c-1; i++ {
        b = b || (S[0][i] == 'A')
        b = b || (S[r-1][i] == 'A')
    }
    for i := 1; i < r-1; i++ {
        b = b || (S[i][0] == 'A')
        b = b || (S[i][c-1] == 'A')
    }
    if b {
        fmt.Println(3)
        return
    }

    fmt.Println(4)
}

func subRow(rowId int) bool {
    for i := 0; i < c; i++ {
        if S[rowId][i] != 'A' {
            return false
        }
    }
    return true
}

func subCol(colId int) bool {
    for i := 0; i < r; i++ {
        if S[i][colId] != 'A' {
            return false
        }
    }
    return true
}

pretestが弱くてなかなかの地獄だったようですが、 コンテスト外とはいえ1発で通ったので良かったです(残業後だったので通らなかったらやはり地獄だった)。

Cを解き終わった時点で満身創痍だったのでコンテスト中は触れられませんでしたが、 やっておくべきでした。

Codeforces Round No.605 (Div.3) 参加記録 (A〜E解答)

A. Three Friends

問題のURL

問題の概要

数直線上に3人がそれぞれ座標 a, b, c にいる。 それぞれは、自身の座標を +1, -1, 0 変位させることができる。

ここで、総合距離を |a-b| + |a-c| + |b-c| とする。

ありうる総合距離の最小値を求めよ、という問題。

解答

まず、一般性を失わずに a <= b <= c となるようにする。

この状態では、総合距離は (b-a) + (c-b) + (c-a) = 2*(c-a) と表すことができる。 よって、移動後もこの関係が保たれているのであれば b はないものとして考えることができる。

よって、 a, c の位置関係に注意しながら、それぞれを右に動かすか、左に動かすか判断すれば良い。

オーバーフローには注意する。

var q int
var a, b, c int64

func main() {
    q = ReadInt()

    for tc := 0; tc < q; tc++ {
        a, b, c = ReadInt64_3()

        solve()
    }
}

func solve() {
    A := LongInt{a, b, c}
    sort.Sort(A)

    aa, _, cc := A[0], A[1], A[2]
    if aa < cc {
        aa++
    }
    if aa < cc {
        cc--
    }
    ans := 2 * (cc - aa)

    fmt.Println(ans)
}

// AbsInt is integer version of math.Abs
func AbsInt(a int64) int64 {
    if a < 0 {
        return -a
    }
    return a
}

type LongInt []int64

func (a LongInt) Len() int           { return len(a) }
func (a LongInt) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a LongInt) Less(i, j int) bool { return a[i] < a[j] }

。。こんな考え込まなくても、素直に全探索するべきですね(27通りしか無いので)。

通ってみればなんてことはないですが、こういった算数はpretestではびびりながら出しているので、 提出に14分かかっています。

今回のコンテストで一番反省すべき点だと思います。

B. Snow Walking Robot

問題のURL

問題の概要

L, R, U, D の命令を与えると、それぞれ左、右、上、下に1マス進むロボットがある。

ただし、このロボットは一度通ったマスを通ると壊れてしまう。

ロボットを壊さずに、自分の家から出発させて、命令の最後には自分の家に戻ってくるようにしたい。

今、命令列が与えられるので、この列のいくつかの命令を消去することで、上記の操作を成立させたい。

最大で何個の命令を残すことができるか、またその時の命令列を出力せよ、という問題。

解答

基本的には、上下と左右に分けて考えて、例えば UU..URR..RDD..DLL..L のように 長方形を描くように移動させることを考えればよい。

このように移動させるためには、上への移動回数と下への移動回数が釣り合う必要があるため、 それぞれのカウントの最小値を採用すれば良い。 左右に関しても一緒である。

ただし、上下の移動ができない場合、あるいは左右の移動ができない場合は、 長方形ではなく線分となってしまい、同じ道を通ってしまうことをケアする必要がある。

この場合はコーナーケースとして別に扱う。

var q int
var S []rune

func main() {
    q = ReadInt()

    for tc := 0; tc < q; tc++ {
        S = ReadRuneSlice()

        solve()
    }
}

func solve() {
    memo := make(map[rune]int)
    memo['L'], memo['R'], memo['U'], memo['D'] = 0, 0, 0, 0

    for _, r := range S {
        memo[r]++
    }

    lrTime := Min(memo['R'], memo['L'])
    udTime := Min(memo['U'], memo['D'])

    if lrTime == 0 && udTime == 0 {
        fmt.Println(0)
        fmt.Println("")
        return
    }

    if lrTime == 0 {
        // UDを1回ずつ
        fmt.Println(2)
        fmt.Println("UD")
        return
    }

    if udTime == 0 {
        // LRを1回ずつ
        fmt.Println(2)
        fmt.Println("LR")
        return
    }

    fmt.Println(lrTime*2 + udTime*2)
    answers := []rune{}
    for i := 0; i < lrTime; i++ {
        answers = append(answers, 'R')
    }
    for i := 0; i < udTime; i++ {
        answers = append(answers, 'D')
    }
    for i := 0; i < lrTime; i++ {
        answers = append(answers, 'L')
    }
    for i := 0; i < udTime; i++ {
        answers = append(answers, 'U')
    }
    fmt.Println(string(answers))
}

C. Yet Another Broken Keyboard

問題のURL

問題の概要

ある長さが n の文字列が与えられたため、タイピングの練習のため、この文字列のすべての連続部分文字列をタイプしようとした。

しかし、いくつかのキーが壊れているため、いくつかの連続部分文字列は不完全な状態で出力されてしまった。

n*(n+1)/2 個の全連続部分文字列のうち、正しくタイピングできたものはいくつか求めよ、という問題。

解答

まず、与えられた文字列に対して、壊れているキーのインデックスに目印をつける。

左から文字列をスキャンしたとき、今見ている文字を右端とする部分文字列でタイピングできるものの数は、 以下の図に示すように、タイプ出来ない文字から数えた文字の長さ分だけである。

f:id:maguroguma:20191217002107j:plain
タイピングできる連続部分文字列の数

タイプ不可の文字に出会うたびにカウンターをリセットすることで、これらの数値はすべて記録できるため、 最後に総和を計算すれば良い。

オーバーフローには注意する。

var n, k int
var S []rune
var Avail []rune

func main() {
    n, k = ReadInt2()
    S = ReadRuneSlice()
    for i := 0; i < k; i++ {
        tmp := ReadRuneSlice()
        Avail = append(Avail, tmp[0])
    }

    memo := make([]int, n)
    for i := 0; i < n; i++ {
        if !isAvail(S[i]) {
            memo[i] = -1
        }
    }

    cur := int64(0)
    sums := make([]int64, n)
    for i := 0; i < n; i++ {
        if memo[i] == -1 {
            // アウトなのでリセット
            cur = 0
        } else {
            // 継続
            cur++
        }
        sums[i] = cur
    }

    ans := int64(0)
    for i := 0; i < n; i++ {
        ans += sums[i]
    }
    fmt.Println(ans)
}

func isAvail(r rune) bool {
    for i := 0; i < len(Avail); i++ {
        if Avail[i] == r {
            return true
        }
    }
    return false
}

。。こんなにめんどくさいことしなくても、タイプ不可能のものとそうでないものを2値化して、 ランレングス圧縮したものを使ったほうが簡単でした。

そこそこ時間をロスしてしまったので、これも結構な失敗でした。

D. Remove One Element

問題のURL

問題の概要

長さ n の整数配列 A が与えられる。

この整数配列の好きな要素を1個削除するか、もしくはそのままでも良い。

この状態の配列に対し、狭義単調増加である連続部分列を考える。

ありうる最も長い連続部分列の長さを求めよ、という問題。

解答

配列 A の要素に関して、消す要素を全探索することを考える。 すなわち、ある要素を削除したとき、影響を受けるのはその前後だけであり、 その際に作られる連続部分列がより大きいものとなるのなら更新していく、ということを考える。

まずは、もとの配列に対して、その要素が属する連続部分列の長さを計算する。

更に、数列間の階差を計算しておく。

以下の図に示すように、ある要素を削除したとき、新たに比較すべき階差は元の階差の和で表される。

f:id:maguroguma:20191217002131j:plain
ある要素を削除した場合に考慮すべき階差

よって、階差の和が正となる場合にのみ、削除される要素の前後の連続部分列の長さを足し合わせる形で、新たに出来上がる連続部分列の長さを計算する。

var n int
var A []int

func main() {
    n = ReadInt()
    A = ReadIntSlice(n)

    // 階差
    diff := []int{} // len(diff) == n-1
    for i := 1; i < n; i++ {
        diff = append(diff, A[i]-A[i-1])
    }

    // 自身が含まれる増加列の長さ
    L := make([]int, n)
    for i := 0; i < n; i++ {
        if i == 0 {
            L[i] = 1
            continue
        }

        if A[i] > A[i-1] {
            L[i] = L[i-1] + 1
        } else {
            L[i] = 1
        }
    }
    cur, l := 0, 0
    for i := n - 1; i >= 0; i-- {
        if cur == 0 {
            cur, l = L[i], L[i]
        }
        L[i] = l
        cur--
    }

    ans := 0
    // 何もしない場合の最大値で初期化
    for i := 0; i < n; i++ {
        ChMax(&ans, L[i])
    }

    // すべて試す
    for i := 1; i < len(diff); i++ {
        if diff[i] > 0 && diff[i-1] > 0 {
            continue
        }
        if diff[i] <= 0 && diff[i-1] <= 0 {
            continue
        }

        if diff[i]+diff[i-1] > 0 {
            // この場合のみ意味がある
            ChMax(&ans, L[i-1]+L[i+1]-1)
        }
    }
    fmt.Println(ans)
}

// ChMax accepts a pointer of integer and a target value.
// If target value is LARGER than the first argument,
// then the first argument will be updated by the second argument.
func ChMax(updatedValue *int, target int) bool {
    if *updatedValue < target {
        *updatedValue = target
        return true
    }
    return false
}

本番では階差数列のみをうまく扱って答えを出そうとしたらぐちゃぐちゃになってしまい、 結果バグったコードによりpretestで撃沈してしまいました。 また、そうでなくとも、階差のインデックスと元の配列のインデックスの調整で身長になる必要があり、あまりいい実装が出来ませんでした(というかよくよく見るといろいろな部分が省ける)。

まずは、もとの配列に対して、その要素が属する連続部分列の長さを計算する。

この部分も結構面倒なのですが、「Union Findを使って増加列を同じグループとし、 それぞれが属するグループのサイズを見れば良い」という方法を くるさんにご教示いただきました。

あまりUnion Findを活用できていなかったと思うので、これからはもう少し視野を広げてみようと思います (というよりは問題にたくさん触れるべきなのですが)。

DPによる別解

こちらも同じくくるさんの解法を参考にしました。

dp1[i]: i番目の数値が属する連続部分列に関して、何個目かを記録する

dp2[i]: i番目以前の数値を1つ削除したときの、i番目の数値が属する連続部分列に関して、何個目かの最大値を記録する

以下のコードに示すように、 dp2 -> dp1 のような遷移がないため、正しく動作します。

var n int
var A []int

var dp1, dp2 [200000 + 5]int

func main() {
    n = ReadInt()
    A = ReadIntSlice(n)

    for i := 0; i < n; i++ {
        dp1[i] = 1
    }

    for i := 0; i < n; i++ {
        if i-1 >= 0 && A[i] > A[i-1] {
            ChMax(&dp1[i], dp1[i-1]+1)
            ChMax(&dp2[i], dp2[i-1]+1)
        }
        if i-2 >= 0 && A[i] > A[i-2] {
            ChMax(&dp2[i], dp1[i-2]+1)
        }
    }

    ans := 0
    for i := 0; i < n; i++ {
        ChMax(&ans, dp1[i])
        ChMax(&ans, dp2[i])
    }
    fmt.Println(ans)
}

なんと呼ぶべきかはわからないですが、 こういった片方向の遷移を行うものは過去のABCあたりでも解いたことがあるような気がします。

いずれにせよ、頻出パターンの1つではあると思うので、定着させていきたいところです。

E. Nearest Opposite Parity

問題のURL

問題の概要

長さ n の整数配列 A が与えられる。

ある位置 i からは、1回の移動で i - A[i] もしくは i + A[i] へと移動できる。

ある開始位置から移動をはじめて、開始位置の A[i] とは偶奇が反対のところへたどり着くためには、 最小で何回の移動が必要か、すべての位置に関して答えよ。

また、到達不可能であるならば -1 を出力せよ、という問題。

解答

公式Editorialをなぞったものです。

まず、ある位置 i から j まで移動できるとき、これを逆向きに考えて j -> i とエッジを張ります。

このようにして出来上がるグラフの辺の数は、最大でも 2*n であるため、全探索が間に合います。

そこで、偶数の要素をスタート地点とした多点BFSを考え、到達位置へのステップ数を記録します。 探索が完了したら、奇数の要素のステップ数を確認すれば、それが答えとなっています。

今度はこれを偶数と奇数を入れ替えて行うことで、すべての位置について答えを求めることが出来ます。

var n int
var A []int

var G [200000 + 5][]int
var answers []int

func main() {
    n = ReadInt()
    A = ReadIntSlice(n)

    for i := 0; i < n; i++ {
        lid, rid := i-A[i], i+A[i]
        if lid >= 0 {
            G[lid] = append(G[lid], i)
        }
        if rid < n {
            G[rid] = append(G[rid], i)
        }
    }

    oddIdxs, evenIdxs := []int{}, []int{}
    for i := 0; i < n; i++ {
        if A[i]%2 == 0 {
            evenIdxs = append(evenIdxs, i)
        } else {
            oddIdxs = append(oddIdxs, i)
        }
    }

    answers = make([]int, n)
    for i := 0; i < n; i++ {
        answers[i] = -1
    }

    bfs(oddIdxs, evenIdxs)
    bfs(evenIdxs, oddIdxs)

    fmt.Println(PrintIntsLine(answers...))
}

func bfs(starts, ends []int) {
    dist := make([]int, n)
    for i := 0; i < n; i++ {
        dist[i] = INF_BIT30
    }

    queue := []int{}
    for _, sidx := range starts {
        dist[sidx] = 0
        queue = append(queue, sidx)
    }

    for len(queue) > 0 {
        cid := queue[0]
        queue = queue[1:]

        for _, nid := range G[cid] {
            if dist[nid] == INF_BIT30 {
                dist[nid] = dist[cid] + 1
                queue = append(queue, nid)
            }
        }
    }

    for _, eidx := range ends {
        if dist[eidx] != INF_BIT30 {
            answers[eidx] = dist[eidx]
        }
    }
}

ICPC形式?のため、Dが解けずにコンテスト中は見ることすらできませんでしたが、 復習の際にDFSから考え始めたので論外でした。

Dijkstraしかり、「最短経路」が効かれているのだからBFSを検討しないと土俵にも立てていませんでした。

また、別に逆向きのグラフじゃなくても順方向のグラフで同じことをすればいけるのでは?とか考えましたが、 探索済みの箇所で衝突してしまうため無理でした。

確かAtCoderうほょじごという問題が、 想定解法がこれと似たようなコンセプトだったような気がします(違ったらすみません)。 「逆から考える」っていう典型と見るべきなのでしょうか?


そろそろ過去に解けなかった問題もとき直したいところなのですが、時間が。。

ランレングス符号化で易問をさらに楽にする(緑ぐらいまでの人向け)

TL;DR

  • AtCoder緑か自分(1300)程度までの人向けです。
  • ランレングス符号化を使いやすい形で用意しておくと、意外と高頻度で便利に使えるよという話。
  • 10月以降のコンテストの問題で役立ったものを、活用事例として紹介します。

きっかけ

AGC039のA問題が60分ぐらい使ってもWAが取れずに、Bへ向かうも解けず、初めての太陽をやらかしてしまいました。

atcoder.jp

それなりにレートも落ちてしまっただけに、復習して確実に経験値にしようと、A問題から復習に力を入れました。

人によって好みはわかれるかもしれませんが、このA問題がランレングス符号化を行うと見通しがよくなるもので、 このタイミングでようやくスニペットをこしらえることになりました (アルゴリズムの存在は知っていても、必要性を感じなかったので用意していなかった)。

すると、以降のコンテストでやたらと使用頻度が高くなり、 無駄に用意しているスニペット集の中でもかなり目立つものになってきました。

なので、自分程度までの人だったら同じように利用できるのではないかと思い、本記事を書くことにしました。

アルゴリズム

色々とバリエーションはありますが、 本記事ではwikipediaの該当ページで 一番最初に説明されている、最も基本的なものを指しています。

AAAAABBBBBBBBBAAA という文字列を 5A9B3A というように符号化するもので、 「連長圧縮」という日本語の通り直感的なものです。

AtCoderユーザは皆さん優秀なので、アルゴリズムの名前は知らなくても自然と使ってた、という人も多そうです。

メインの焦点は文字列だと思いますが、競技プログラミングでよく登場する整数配列についても、 しばしば便利に使えます。

実装例

言語はGolangですが、アルゴリズム自体はシンプルなので、他言語を使っている方も読む分にはほとんど問題ないかと思います。

ポイントとしては、 「文字とカウントを分離して別々の配列として出力する」 ことぐらいです (もっと便利なシグニチャがあったら教えていただきたいです)。

RunLengthDecoding(RunLengthEncoding(S)) == S となるように復号関数も一応用意していますが、 特に使ったことはありません。

// RunLengthEncoding returns encoded slice of an input.
func RunLengthEncoding(S []rune) ([]rune, []int) {
    runes := []rune{}
    lengths := []int{}

    l := 0
    for i := 0; i < len(S); i++ {
        // 1文字目の場合保持
        if i == 0 {
            l = 1
            continue
        }

        if S[i-1] == S[i] {
            // 直前の文字と一致していればインクリメント
            l++
        } else {
            // 不一致のタイミングで追加し、長さをリセットする
            runes = append(runes, S[i-1])
            lengths = append(lengths, l)
            l = 1
        }
    }
    runes = append(runes, S[len(S)-1])
    lengths = append(lengths, l)

    return runes, lengths
}

// RunLengthDecoding decodes RLE results.
func RunLengthDecoding(S []rune, L []int) []rune {
    if len(S) != len(L) {
        panic("S, L are not RunLengthEncoding results")
    }

    res := []rune{}

    for i := 0; i < len(S); i++ {
        for j := 0; j < L[i]; j++ {
            res = append(res, S[i])
        }
    }

    return res
}

C++などだったらジェネリクスを使うのが妥当かと思います。

Golangではジェネリクスがないので、自分の場合、この手の問題ではスニペットで必要な型をその時々に指定しています ( interface{} だといちいち型アサーションするのが面倒)。

github.com

実際のところ、Golangも全然詳しくないので、もっといい方法があれば是非教えていただきたいです。

活用事例

ここからは、実際に活用できた問題と具体的な活用方法について書いていきます。

ABC143 C. Slimes

問題のURL

まさにランレングス符号化そのものです。

スニペット呼び出して、関数に放り込んで、出力のいずれかの配列の長さを提示して終わりです。

他の解き方でも簡単に解けるとは思いますが、バグの心配もなく貼るだけで終わるならばそれが一番だと思います。

var n int
var S []rune

func main() {
    n = ReadInt()
    S = ReadRuneSlice()

    comp, _ := RunLengthEncoding(S)
    fmt.Println(len(comp))
}

Educational Codeforces Round 75 A. Broken Keyboard

問題URL

問題を要約すると、おおよそ以下のような感じです。

26文字のキーボードについていくつかの壊れたキーがあるので、故障していないキーだけを列挙する問題。

壊れたキーを叩くと、その文字について確実に2回タイプされてしまう、というのをヒントに解く。

「確実に故障していない」と断定できるのは、連続で奇数回タイプされた文字だけなので、 それを見つけるために文字列をfor文でスキャンしてカウントを取る、という方法でも簡単に解けます。

しかしながら、フルフィードバックではないCodeforcesではとにかくバグの出る余地をなくしたいので、 実績のあるスニペットを持ち出せると多少は安心できます。

var t int
var S []rune

type DirRange []rune

func (a DirRange) Len() int           { return len(a) }
func (a DirRange) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a DirRange) Less(i, j int) bool { return a[i] < a[j] }

func main() {
    t = ReadInt()

    for i := 0; i < t; i++ {
        S = ReadRuneSlice()
        memo := make(map[rune]int)

        SS, L := RunLengthEncoding(S)
        for i := 0; i < len(L); i++ {
            if L[i]%2 == 1 {
                memo[SS[i]] = 1
            }
        }

        answers := DirRange{}
        for key := range memo {
            answers = append(answers, key)
        }

        sort.Sort(answers)
        fmt.Println(string(answers))
    }
}

Codefources Round 604 A. Beautiful String

問題のURL

問題を要約すると、おおよそ以下のような感じです。

a, b, c, ? の4文字からなる文字列が与えられる。

? の部分を a, b, c のいずれかに置き換えて、同じ文字が連続しないように文字列を構築せよ、という問題。

この問題も、やること自体は非常に簡単かつすぐに思いつくもので、 「文字列をスキャンして前後の文字と違うものを素直に選び続ければ良い」というだけです。

「最初から2つ以上連続する a, b, c が存在するとアウト」という部分を先に処理しておくと、 後半の構築に集中することが出来、バグらせる確率が多少減らせます。

文字列をスキャンして前後を見る、としても良いんですが、 先頭と末尾は処理が変わったり、、とか考えるのも面倒で、ランレングス符号化したものを見ると簡単です。 (結局構築時にそれは考える必要があるんですが)。

var t int
var S []rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        S = ReadRuneSlice()

        solve()
    }
}

func solve() {
    // 1文字のケース
    if len(S) == 1 && S[0] != '?' {
        fmt.Println(string(S))
        return
    }
    if len(S) == 1 && S[0] == '?' {
        fmt.Println("a")
        return
    }

    // 以降は2文字以上

    // 可能かどうか
    pressed, nums := RunLengthEncoding(S)
    for i := 0; i < len(pressed); i++ {
        r := pressed[i]
        cnt := nums[i]

        if r != '?' && cnt > 1 {
            fmt.Println(-1)
            return
        }
    }

  // 後は素直に構築するだけ
}

Codefources Round 600 Div.2 A. Single Push

問題のURL

問題を要約すると、おおよそ以下のような感じです。

与えられた配列 A に対して、1度だけ任意の連続区間に対してある正の整数加算することが許される。 操作は行わなくても良い。

これによって、もう一方の与えられた配列 B に等しくすることができるか?

これを達成するためには、 すべての要素に関して diff[i] = B[i] - A[i] を計算しておき、 この diff 配列が [0, ..., 0, k, ..., k, 0, ..., 0], k >= 0 のような形になっていればよい、 というのは割と簡単にわかると思います。

しかしながら、これをバグらせずに判定するのは、 いくつかの場合分けが必要だったり、それなりに神経を使うような気がします。

そこで、 整数配列に対するランレングス符号化 を考えます。

圧縮後の配列に対して、

  1. 負の整数が検出されたらアウト
  2. 正の整数が2つ以上検出されたらアウト
  3. そうでないならセーフ

のように判定すればよい、というふうな実装方針が立ちます。

前後の 0 埋めがないケースの場合分けなどが不要となり、それなりに実装の負荷は小さくなっているのではないでしょうか。

var t int
var n int
var A, B []int

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        n = ReadInt()
        A, B = ReadIntSlice(n), ReadIntSlice(n)

        solve()
    }
}

func solve() {
    diff := make([]int, n)
    for i := 0; i < n; i++ {
        diff[i] = B[i] - A[i]
    }

    pressed, _ := RunLengthEncoding(diff)

    positive := 0
    for i := 0; i < len(pressed); i++ {
        if pressed[i] < 0 {
            fmt.Println("NO")
            return
        }

        if pressed[i] > 0 {
            positive++
        }
    }

    if positive == 0 || positive == 1 {
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}

Codeforces Round 604 C. Beautiful Regional Contest

問題のURL

問題を要約すると、おおよそ以下のような感じです。

あるプログラミングコンテストにおいて、 n 人の解答問題数が配列で与えられるので、 それぞれの人に金・銀・銅メダルを授与することを考える。

以下の条件を満たすように、それぞれのメダルの数を求める問題。

  1. それぞれのメダルの数は正の整数である。
  2. 金メダルの数は、銀・銅メダルよりも大きい必要がある。ただし、銀メダルと銅メダルの数量関係は不問である。
  3. 金メダルを受賞する参加者は、銀メダルを受賞する参加者よりも多くの問題を解いていなければならない。
  4. 銀メダルを...、銅メダルを...。
  5. 銅メダルを...、メダルを受賞していない参加者よりも多くの問題を解いていなければならない。
  6. 3つのメダルの合計個数は、 Floor(n/2) 以下である必要がある。

考えるポイントが多いだけに、ここでも前処理として整数配列に対するランレングス符号化を行っておくと、 問題の本質部分に集中できて楽です。

条件3, 4, 5を踏まえると、メダルの種類の境界において、 問題の正解数に1以上の差がある必要がある、すなわち、正解数が異なっている必要があるとわかります。

なので、各メダルの枚数を加算するにあたっては、ランレングス符号化を行った後の長さが使えます。

var t int
var n int
var P []int

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        n = ReadInt()
        P = ReadIntSlice(n)

        solve()
    }
}

func solve() {
    g, s, b := 0, 0, 0
    limit := n / 2

    _, counts := RunLengthEncoding(P)
    // 圧縮後に最低長さ3は必要
    if len(counts) < 3 {
        fmt.Println(0, 0, 0)
        return
    }

    // gを決める
    g += counts[0]

    // sを決める、伸ばす
    idx := 1
    for idx < len(counts) {
        // gを超えたらbreak
        if s > g {
            break
        }

        s += counts[idx]
        idx++
    }

    // bを決める、伸ばす
    for idx < len(counts) {
        // gを超えたらbreak
        if b > g {
            break
        }

        b += counts[idx]
        idx++
    }

    if g == 0 || s == 0 || b == 0 {
        fmt.Println(0, 0, 0)
        return
    }
    if s <= g || b <= g {
        fmt.Println(0, 0, 0)
        return
    }
    sum := g + s + b
    if sum > limit {
        fmt.Println(0, 0, 0)
        return
    }

    // bをできるだけ伸ばす
    for idx < len(counts) {
        // 足した結果がlimitを超えるなら足さないでbreak
        if sum+counts[idx] > limit {
            break
        }

        b += counts[idx]
        sum += counts[idx]
        idx++
    }

    fmt.Println(g, s, b)
}

まとめ

ランレングス圧縮を用意しておくと、簡単な問題がさらに楽になったり、 多かれ少なかれバグの心配が減ったりと、結構便利だよ、ということを伝えるための内容でした。

正直見返してみると、若干過剰適合というか、「金槌を手にして多くの問題が釘に見えている」という状態に落ちているような気もします。

とはいえ、それで損した感じはなく、少なくとも毒にはなっていないだろうということで、今回このように紹介してみました。

また、問題例のほとんどがCodeforcesである通り、最近こどふぉにも積極的に参加していますので、 近いレベル帯のフレンド(ライバル)募集中です (知っている人がみんな紫以上でDiv1に行っちゃったり、Div2一緒に出ても大差つけられてしまって悲しい)。

codeforces.com

Codeforces Round No.604 (Div.2) 参加記録(A〜D解答)

今回もランレングス符号化が活躍してくれた。

A. Beautiful String

問題のURL

問題の概要

a, b, c, ? の4文字からなる文字列が与えられる。

? の部分を a, b, c のいずれかに置き換えて、同じ文字が連続しないように文字列を構築せよ、という問題。

解答

基本的には、文字列を舐めて前後の文字と違うものを素直に選び続ければ良い。 効率的な実装を心がけたい。

面倒なコーナーケースは潰しておきたいと思ったので、まずは1文字だけの場合を処理する。

2文字以上の場合も、まずは構築不可能な場合、すなわち、最初から連続する部分が存在しないかをチェックする。 このチェックにはランレングス符号化が便利。 a, b, c のいずれかが2文字以上続いていたらアウトと判定すれば良い。

それらのチェックが終わったら後は純粋に構築していくだけなので、バグに気をつけながら適宜関数に切り分けたりしてコーディングしていく。

var t int
var S []rune

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        S = ReadRuneSlice()

        solve()
    }
}

func solve() {
    // 1文字のケース
    if len(S) == 1 && S[0] != '?' {
        fmt.Println(string(S))
        return
    }
    if len(S) == 1 && S[0] == '?' {
        fmt.Println("a")
        return
    }

    // 以降は2文字以上

    // 可能かどうか
    pressed, nums := RunLengthEncoding(S)
    for i := 0; i < len(pressed); i++ {
        r := pressed[i]
        cnt := nums[i]

        if r != '?' && cnt > 1 {
            fmt.Println(-1)
            return
        }
    }

    for i := 0; i < len(S); i++ {
        // 決まっていたらパス
        if S[i] != '?' {
            continue
        }

        if i == 0 {
            // 次を見る
            next := S[i+1]
            S[i] = sub(next)
        } else if i == len(S)-1 {
            // 前を見る
            before := S[i-1]
            S[i] = sub(before)
        } else {
            // 前後を見る
            next, before := S[i+1], S[i-1]
            S[i] = subsub(next, before)
        }
    }

    fmt.Println(string(S))
}

// rはa, b, c, ?のいずれかで、r以外のa, b, cのいずれかを返す
// ?だったらaを返す
func sub(r rune) rune {
    if r == 'a' {
        return 'b'
    } else if r == 'b' {
        return 'c'
    } else if r == 'c' {
        return 'a'
    } else {
        return 'a'
    }
}

func subsub(r, s rune) rune {
    memo := make(map[rune]bool)
    memo[r] = true
    memo[s] = true

    isA := memo['a']
    isB := memo['b']
    isC := memo['c']

    if !isA {
        return 'a'
    } else if !isB {
        return 'b'
    } else if !isC {
        return 'c'
    }

    return 'a'
}

// RunLengthEncoding returns encoded slice of an input.
func RunLengthEncoding(S []rune) ([]rune, []int) {
    runes := []rune{}
    lengths := []int{}

    l := 0
    for i := 0; i < len(S); i++ {
        // 1文字目の場合保持
        if i == 0 {
            l = 1
            continue
        }

        if S[i-1] == S[i] {
            // 直前の文字と一致していればインクリメント
            l++
        } else {
            // 不一致のタイミングで追加し、長さをリセットする
            runes = append(runes, S[i-1])
            lengths = append(lengths, l)
            l = 1
        }
    }
    runes = append(runes, S[len(S)-1])
    lengths = append(lengths, l)

    return runes, lengths
}

Aから20分くらいかかって幸先が良くないですが、特別詰まったわけではないと思い込みつつ先に進みました。

B. Beautiful Numbers

問題のURL

問題の概要

1, 2, .., n までの順列が配列の形で与えられる。

ここから長さ m の連続する部分列を切り出したとき、 1, 2, .., m の順列になっているかを、 すべての m について判定する問題。

解答

O(n^2) は許されない制約であるため、全探索的な愚直な解法は認められない。

元の順列の 1, 2, .., m の要素の位置を pos[1], pos[2], .., pos[m] とする。 ここで max(pos[i]) - min(pos[i]) + 1 (1 <= i <= m) によって、 1, 2, .., m の要素を含む連続部分配列のうち、 長さが最小のものの長さが手に入る。

この長さが m であれば m の順列をなす連続部分列が取得できるし、 m より大きくなってしまうならば、不純物が混じってしまうため、目的の連続部分列は取得できない(必要十分条件になっている)。

よって、上述の max, min を都度更新していけばすべての m について高速に判定できる。

計算量は全体で O(n)

var t int
var n int
var P []int

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        n = ReadInt()
        P = ReadIntSlice(n)

        solve()
    }
}

func solve() {
    pos := make([]int, n+1)
    for i := 0; i < n; i++ {
        p := P[i]
        pos[p] = i
    }

    answers := make([]rune, n)

    l, r := pos[1], pos[1]
    answers[0] = '1'
    for i := 2; i <= n; i++ {
        ChMin(&l, pos[i])
        ChMax(&r, pos[i])

        dist := r - l + 1
        if dist == i {
            answers[i-1] = '1'
        } else {
            answers[i-1] = '0'
        }
    }

    fmt.Println(string(answers))
}

// ChMin accepts a pointer of integer and a target value.
// If target value is SMALLER than the first argument,
// then the first argument will be updated by the second argument.
func ChMin(updatedValue *int, target int) bool {
    if *updatedValue > target {
        *updatedValue = target
        return true
    }
    return false
}

// ChMax accepts a pointer of integer and a target value.
// If target value is LARGER than the first argument,
// then the first argument will be updated by the second argument.
func ChMax(updatedValue *int, target int) bool {
    if *updatedValue < target {
        *updatedValue = target
        return true
    }
    return false
}

C. Beautiful Regional Contest

問題のURL

問題の概要

あるプログラミングコンテストにおいて、 n 人の解答問題数が配列で与えられるので、 それぞれの人に金・銀・銅メダルを授与することを考える。

以下の条件を満たすように、それぞれのメダルの数を求める問題。

  1. それぞれのメダルの数は正の整数である。
  2. 金メダルの数は、銀・銅メダルよりも大きい必要がある。ただし、銀メダルと銅メダルの数量関係は不問である。
  3. 金メダルを受賞する参加者は、銀メダルを受賞する参加者よりも多くの問題を解いていなければならない。
  4. 銀メダルを...、銅メダルを...。
  5. 銅メダルを...、メダルを受賞していない参加者よりも多くの問題を解いていなければならない。
  6. 3つのメダルの合計個数は、 Floor(n/2) 以下である必要がある。

解答

満たすべき条件が多いが、素直にそれらを満たすように貪欲的に解を構築していく方針で考える。

条件を整理していく。

条件3, 4, 5より、メダルの種類の境界(メダルを授与されない参加者は透明のメダルでももらうと思っておく)において、 問題の正解数に1以上の差がある必要がある、すなわち、正解数が異なっている必要がある。

よって、ここでもランレングス符号化を施しておくと見通しが良くなる。 以降は、ランレングス符号化が行われている前提で話をすすめる。

(※当然ながら、正答数が多いひとを差し置いて、それより正答数が小さい人にメダルを授与することはできないことに注意する。)

条件1より、符号化後に要素数が3以上である必要があるため、そうでない場合は不可能として終了する。

条件2より、金メダルの受賞者は少ないほうが良いため、正解数が最大の人のみとする。

ここからは、銀メダルと銅メダルの受賞者数を、条件2, 6に気をつけながら増やしていけば良い。 銀メダルについては、金メダルの数より大きくなりさえすればよい。 銅メダルについても、まずは金メダルの数よりは大きくし、まだ条件6に対して余裕があるのであれば、 さらに追加していけば良い。

var t int
var n int
var P []int

func main() {
    t = ReadInt()

    for tc := 0; tc < t; tc++ {
        n = ReadInt()
        P = ReadIntSlice(n)

        solve()
    }
}

func solve() {
    g, s, b := 0, 0, 0
    limit := n / 2

    _, counts := RunLengthEncoding(P)
    // 圧縮後に最低長さ3は必要
    if len(counts) < 3 {
        fmt.Println(0, 0, 0)
        return
    }

    // gを決める
    g += counts[0]

    // sを決める、伸ばす
    idx := 1
    for idx < len(counts) {
        // gを超えたらbreak
        if s > g {
            break
        }

        s += counts[idx]
        idx++
    }

    // bを決める、伸ばす
    for idx < len(counts) {
        // gを超えたらbreak
        if b > g {
            break
        }

        b += counts[idx]
        idx++
    }

    if g == 0 || s == 0 || b == 0 {
        fmt.Println(0, 0, 0)
        return
    }
    if s <= g || b <= g {
        fmt.Println(0, 0, 0)
        return
    }
    sum := g + s + b
    if sum > limit {
        fmt.Println(0, 0, 0)
        return
    }

    // bをできるだけ伸ばす
    for idx < len(counts) {
        // 足した結果がlimitを超えるなら足さないでbreak
        if sum+counts[idx] > limit {
            break
        }

        b += counts[idx]
        sum += counts[idx]
        idx++
    }

    fmt.Println(g, s, b)
}

// RunLengthEncoding returns encoded slice of an input.
func RunLengthEncoding(S []int) ([]int, []int) {
    runes := []int{}
    lengths := []int{}

    l := 0
    for i := 0; i < len(S); i++ {
        // 1文字目の場合保持
        if i == 0 {
            l = 1
            continue
        }

        if S[i-1] == S[i] {
            // 直前の文字と一致していればインクリメント
            l++
        } else {
            // 不一致のタイミングで追加し、長さをリセットする
            runes = append(runes, S[i-1])
            lengths = append(lengths, l)
            l = 1
        }
    }
    runes = append(runes, S[len(S)-1])
    lengths = append(lengths, l)

    return runes, lengths
}

D. Beautiful Sequence

問題のURL

問題の概要

0, 1, 2, 3 の数字がそれぞれ a, b, c, d 個与えられるので、 これらをすべて使い切って1列に並べる。

出来上がった数列に関して、隣り合う数字の差をすべて 1 とすることができるか判定し、 可能ならば具体的に構築せよ、という問題。

解答

判定だけなら結構簡単かもしれないが、構築も要求されるとすごく難しい。

(以下はeditorialそのままです。)

まず、作るべき数列に関して、偶数は 0, 0, .., 0, 2, 2, .., 2 と並べるのが最適となる。 こうすることで、 3 を置くことができる箇所を最大化できる一方で、 1 はどの間でも置くことができる。

※この時点で少し難しい気がする。 構築可能なときに必要な 1 の数が変わっておらず、かつ 3 を受け入れる箇所を最大化出来ているから最適、と読めば良い?

この後は、まず 32 の間に並べて、隙間の数が足りないならば端に置く、 続いて 1 を残っている隙間に入れて、足りなければやはり端に置く、とすれば良い。

しかし、具体的に条件分岐させて一発での構築を目指すと、かなり複雑になると思う(というより私は諦めました)。

editorialの実装例では、以下のように開始する数に関して全探索を行うような賢い実装を行っている。

var A map[int]int

func main() {
    a, b, c, d := ReadInt4()
    total := a + b + c + d

    for i := 0; i < 4; i++ {
        A = make(map[int]int)
        A[0], A[1], A[2], A[3] = a, b, c, d
        answers := []int{}

        if A[i] > 0 {
            last := i
            answers = append(answers, last)
            A[last]--
            for {
                if A[last-1] > 0 {
                    A[last-1]--
                    answers = append(answers, last-1)
                    last--
                } else if A[last+1] > 0 {
                    A[last+1]--
                    answers = append(answers, last+1)
                    last++
                } else {
                    break
                }
            }

            if len(answers) == total {
                fmt.Println("YES")
                fmt.Println(PrintIntsLine(answers...))
                return
            }
        }
    }

    fmt.Println("NO")
}

配列ではなく辞書を使うことで last-1 の負数判定をなくしたりと、きれいな実装の参考になりました。


AtCoder緑ぐらいの人たちでランレングス符号化を用意していない人が居たら、ぜひ用意してみていただきたいです。 意外と便利なので。