Leverage Copy

メモの公開場所

Educational Codeforces Round No.74参加記録(A~D解答)

Cで本当にしょうもないミスをしてしまった。。

A. Prime Subtraction

問題URL

問題

2つの整数 x, y が与えられる。 x > y であることが保証されている。

好きな素数 p を選んで、その素数を何回でも x から引くことが出来る。

そのようにして、 xy と等しくなるように出来るか答えよ。

t 個の独立したテストケースに対して答えよ。

制約: 1 <= t <= 1000, 1 <= y < x <= 10^18

解答

x から適当な回数素数 p を引いて y にする、という部分をそのまま数式にすると、

x - n*p = y <=> p = (x-y)/n

x-y を適当な x-y の約数(1でもよい)で割った商を何かしらの素数にできるか?と考える。

x-y素因数分解したときを考えると、適当な素数が残るような約数を選択できることがわかるので、 x-y が2以上であればOK。 1のときは、そのような n = 1 とするしかないため、適当な素数が選べない。

var t int

func main() {
    t = ReadInt()

    for i := 0; i < t; i++ {
        x, y := ReadInt64_2()

        if x-y >= 2 {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
    }
}

B. Kill 'Em All

問題URL

問題

※とても問題が長いので、適宜意訳。

Ivanはとあるゲームの最終ステージに苦労しており、全てのモンスターを倒すために手助けを必要としている。

ステージはとても長い廊下(無限に伸びる数直線でモデル化できる)からなっている。 廊下は x = 0 で2つの部分に分けられる。

右側は、 n 体のモンスターが存在し、位置は座標 X[i] で表される。

左側は、罠で埋め尽くされており、モンスターが負の座標に位置までやってきた途端、罠によってモンスターは死ぬ。

Ivanの武器はフェニックスロッドによる爆破であり、選択した爆破位置 c によって、モンスターたちは以下のような反応をする。 モンスターの座標を y とする。

  • c = y ならば、モンスターは爆殺される。
  • y < c ならば、モンスターは左に r 押し出される(モンスターの位置は y - r となる)。
  • y > c ならば、モンスターは右に r 押し出される(モンスターの位置は y + r となる)。

Ivanは、できるだけ少ない爆破回数でモンスターを全滅させたい。

q 個の各クエリについて、最小の必要爆破回数を答えよ。

制約:

  • 1 <= q <= 10^5
  • 1 <= n, r <= 10^5
  • 1 <= X[i] <= 10^5
  • クエリに渡って n の合計は 10^5 を超えない。

解答

できる限り X[i] の大きいモンスターから爆殺していく貪欲法で良い。 これは以下の理由から正しいと言える。

まず、モンスターを直接攻撃しない、という戦略は損しかしない。 問題の設定上、モンスターを爆風で右に吹き飛ばすのは無意味であり、 モンスターを直接攻撃しないのであれば、無限遠の正の座標を爆破して、すべてのモンスターを左に寄せるほうがマシである。

また、そのようにするならば、一番右に存在するモンスターを直接狙う方が明らかに得である。

実装は、爆破回数を覚えておくことで、都度チェックしているモンスターの現在位置が計算できるので、 一度罠にかかったらbreakすればよい(自分の解答では横着をしていてbreakしていない)。

var q int

func main() {
    q = ReadInt()

    for i := 0; i < q; i++ {
        n, r := ReadInt2()
        X := ReadIntSlice(n)
        memo := make(map[int]int)
        for _, x := range X {
            memo[x] = 1
        }
        XX := []int{}
        for k := range memo {
            XX = append(XX, k)
        }

        sort.Sort(sort.IntSlice(XX))
        nn := len(XX)
        fmt.Println(XX)

        // m は中央を意味する何らかの値
        isOK := func(m int) bool {
            // 後ろのモンスターから爆殺
            cnt := 0
            for j := nn - 1; j >= 0; j-- {
                // j番目に殺すモンスターの座標
                xx := XX[j] - cnt*r

                if xx > 0 {
                    // 爆殺する
                    cnt++
                }
            }

            if cnt <= m {
                return true
            }
            return false
        }

        ng, ok := 0, len(X)
        for int(math.Abs(float64(ok-ng))) > 1 {
            mid := (ok + ng) / 2
            if isOK(mid) {
                ok = mid
            } else {
                ng = mid
            }
        }
        fmt.Println(ok)
    }
}

実際のところ、コンテスト中は貪欲法の正しさがあまりはっきりと認識できなかったため、二分探索のコードを書いて爆破回数の境界値を探ってしまいました (ほとんど書き終わってから結局意味がないことに気づきました)。 とはいえ、計算量的には間に合うだろうと思って、書き直してバグを生むことのほうが懸念されたので、このまま提出しました(system test終了後、460msecとなっていました)。

問題文が長くて読むのが大変、かつコンテスト中は致命的な部分(爆風による吹き飛び方の部分)にタイポがあったため、かなりストレスでした。

C. Standard Free2play

問題URL

問題

※適宜意訳

高さ h の崖を下るゲームがある。 1 ~ h の各整数位置 x に動く足場が存在する。

足場は、崖の中に隠れているか、崖から露出して飛び出しているかの2つの状態がある。 初期状態では n 個の位置 P[1], ..., P[n] の足場が露出して飛び出している状態である。 キャラクターの初期位置は h であるため、 h の足場は初期状態で飛び出ている。

キャラクターは、 x の足場に居るときにレバーを引くことができ、レバーを引くと x, x-1 の2つの足場の状態が変化する。 キャラクターが立っている x の足場は崖に引っ込むため、キャラクターは落下することになる。

キャラクターはとても華奢であるため、安全に着地できるのは段差2以下の落下までである。 それ以上の落差で落下すると死亡してしまう。

状況によっては、安全に下に降りることができなくなってしまうが、いつでも購入可能な魔法のクリスタルを購入することで、 好きな足場1つの状態を変化させることができる。 クリスタルは使うと消滅する。

安全に地面 0 に着地するために、必要なクリスタルの最小個数はいくつか答えよ。

制約:

  • 1 <= q <= 100
  • 1 <= h <= 10^9, 1 <= n <= 2*10^5
  • h = p[1] > p[2] > ... > p[n] >= 1
  • 各クエリに渡った n の合計は 2*10^5 を超えない。

解答

今現在キャラクターが存在する足場は露出しており、その1つ下の足場が露出しているか、隠れているかの2つの場合がある。

  1. 1つ下が露出している場合、キャラクターは落差2以上落下する
  2. 1つ下が隠れている場合、キャラクターは落差1落下する(現在の足場が隠れると同時に、1つ下の足場が露出するため、1つ下に落下・着地する)

1のケースにあたった場合、2つ下の足場が露出していれば、無事に着地できるが、そうでない場合は3以上の落差で落下し死亡してしまう。 よってこれを回避するためにクリスタルを使う必要があるが、例えば、2つ下の足場をクリスタルによって露出させることで、落下死を防げる。

これを、足場を配列に見立てて素直にシミュレーションすることを考えたが、 h の範囲が大きいのと、 工夫をしたとしてもとても複雑でバグりやすいコードになりそうだったため、これは避けた。

結局の所、露出している足場が連続している部分に注目すればよいとわかる。

図のように、露出した足場の連続する部分の個数が、キャラクターが現在立っている足場を含めて奇数個ならば無事に降りれる。 そうでなければ、クリスタルで連続部の1つ下を、クリスタルで露出させる必要がある。

f:id:maguroguma:20191012151259j:plain
足場の下り方、クリスタルの使い所

よって、例えばサンプルの3番目のクエリだと、以下の図のように、2箇所クリスタルで露出させる必要がある。

f:id:maguroguma:20191012151338j:plain
サンプルのクエリ3の例

以上から、与えられた足場の列の連続部分に着目すれば、シミュレーションを簡略化でき、答えが求められる。 実装に際しては、いくつか注意すべき点がある。

  • 最初の列だけは若干足場の数のカウントに注意する必要がある(立っている足場が途中経過によらずに h で確定しているため)
  • 最後の列だけは、連続部が偶数個であっても、最後尾が1の場合はクリスタルは不要(キャラクタは2から0へ飛び降りることになるため)
var q int

func main() {
    q = ReadInt()

    for i := 0; i < q; i++ {
        _, n := ReadInt2()
        P := ReadIntSlice(n)

        ans := 0
        num := 1 // 現在位置を1つとしてカウント
        j := 0
        for j < n-1 {
            if P[j]-P[j+1] == 1 {
                // 差が1なら、列の長さをインクリメント、jは1つ先へ
                num++
                j++
            } else {
                // 差が2以上なら、列の長さは打ち止め、かつそれまでの列の長さが偶数なら購入する
                if num%2 == 0 {
                    ans++
                }
                // 列の最初をP[j+1]+1とする
                num = 2
                j++
            }
        }
        if num%2 == 0 {
            if P[n-1] >= 2 {
                ans++
            }
        }

        fmt.Println(ans)
    }
}

キャラクタは2から0へ飛び降りることになるため

。。コンテスト中は、この部分に気づいていたにもかかわらず、なぜか P[n-1] >= 2 の部分を P[n-1] >= 3 と書いてしまい pretestすら通すことができませんでした。

別のコード

自分の頭のメモリ不足と言われたらどうしようもないですが、このようなシミュレーションのように、 「連続部の長さを数えながら、見ているセグメントの位置によっては微妙に処理内容を変える」というのは、結構脳に負担がかかります。 実際、コンテスト中も他の部分がバグっているのかと思い、初歩的な部分を見落としてしまいました。

リーダブルコードの149ページにも「一度に一つのタスクを適用する」というのがあるので、 それに倣って、

  • 連続部の計算を別に事前に行っておく。
  • 使用するクリスタルのカウントは別で集中して行う。

という方針でも書いてみました。

var q int

func main() {
    q = ReadInt()

    for i := 0; i < q; i++ {
        _, n := ReadInt2()
        P := ReadIntSlice(n)

        ans := 0
        tmp := []int{0}
        for j := 0; j < n-1; j++ {
            if P[j]-P[j+1] >= 2 {
                tmp = append(tmp, j+1)
            }
        }
        tmp = append(tmp, n)
        rows := [][]int{}
        for j := 0; j < len(tmp)-1; j++ {
            idx1, idx2 := tmp[j], tmp[j+1]
            rows = append(rows, P[idx1:idx2])
        }

        if len(rows) == 1 {
            R := rows[0]
            if len(R)%2 == 0 && R[len(R)-1] >= 2 {
                fmt.Println(1)
            } else {
                fmt.Println(0)
            }
            continue
        }
        for k, R := range rows {
            if k == 0 {
                if len(R)%2 == 0 {
                    ans++
                }
            } else if k == len(rows)-1 {
                l := len(R) + 1
                if l%2 == 0 && R[len(R)-1] >= 2 {
                    ans++
                }
            } else {
                l := len(R) + 1
                if l%2 == 0 {
                    ans++
                }
            }
        }

        fmt.Println(ans)
    }
}

。。今度は連続部が1つのみの場合について例外的に扱う必要が出てきてしまいました。

このあたりの強い人達がやっているベストプラクティスが知りたいところです。

D. AB-string(2019-12-08追記)

問題URL

問題の概要

文字列 S について、 S を構成するすべての文字が、2文字以上の S の部分文字列でありかつ回文であるものに含まれているとき、 この文字列 S をgoodとする。

与えられた文字列について、goodな部分文字列の個数を求めよ、という問題。

解答

※基本的に公式editorialの解法をなぞったものです。

goodな文字列というのを考えるにあたって、goodとならない原因となる文字、すなわち回文に含まれない文字のことをnot goodな文字と呼ぶ。

冷静に整理すると、ある文字列 S = ox..xo について、not goodな文字となる可能性があるのは、先頭と末尾の文字だけである。 なぜなら、それ以外の内部の文字について、隣に等しいものがあればそれ自体が回文になり、両隣が異なるときは3文字の回文となるためである。

よって、goodじゃない文字列というのは、1文字の文字列を除くと、以下の4パターンになる。

  • ^AB+$
  • ^BA+$
  • ^A+B$
  • ^B+A$

これを数えて全体から引くことで、goodな文字列の数が求まる。

。。editorialはここまでで、実装についてはpythonのシンプルなコードが用意されているが、正直何をやっているのかよくわかりませんでした。

自分は最近特にお気に入りのランレングス符号化を仲介して数えました。

var n int64
var S []rune

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

    ans := n * (n - 1) / 2

    pressed, counts := RunLengthEncoding(S)

    length := len(pressed)
    for i := 0; i < length; i++ {
        if i+1 < length {
            ans -= int64(counts[i+1])
        }
        if i-1 >= 0 {
            ans -= int64(counts[i-1])
        }
    }
    // 重複して減らした部分を補正
    ans += int64(length - 1)

    fmt.Println(ans)
}

はじめ dp[i]: i番目の文字が末尾となるgoodな文字列の数 というDPを考えて、最後に総和を取ろうとしたのですが、 遷移がうまく定義できずに諦めました(なんかできそうな気もするけど)。


感想

Cなんかは特別なアルゴリズムを使っているわけではないので、純粋な実装力不足が目立つあたり落ち込みますね。。

C++の優れたコードをちゃんと読んで自分のコードにも適用したいので、C++もちょこちょこ勉強してスムーズに読めるぐらいはしておいたほうが良さそうです。