Leverage Copy

メモの公開場所

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

Cが少しでもいけそうと思ってしまった時点で負けでした。

※Bは通ったものの、正当性の保証が全くできていないのでコードのみ記載します。

※Cは後日追記します(2019-10-14追記)。

A: Pens and Pencils

問題URL

問題

※あまりにも問題文が冗長なので、要点のみ。

a 個の講義と b 個の実践演習がある。 1本のペンで c 個の講義のノートを取る事ができ、1本の鉛筆で d 個の実践演習の設計図を描ける。 全部の講義と実践演習をこなしたいが、筆箱の容量はペンと鉛筆合わせて k 本までしか入らない。

すべての講義と実践演習をこなせるか判定し、こなせる場合は筆箱に収まるペンと鉛筆の本数をそれぞれ答えよ。

テストケースは t 個あるため、それぞれについて答えよ。

制約:

  • 1 <= t <= 100
  • 1 <= a, b, c, d, k <= 100

解答

答えはなんでも良いので最小化する必要はないが、最小限必要な本数をそれぞれ答えるほうが簡単なので、それを求める。

a 個の講義をこなすために必要なペンの本数と、 b 個の実践演習をこなすために必要な鉛筆の本数は、 それぞれ Ceil(a/c), Ceil(b/d) で求まる。

それの合計が k を超えていなければ、それぞれ出力すれば良い。

var t int

func main() {
    t = ReadInt()

    for i := 0; i < t; i++ {
        a, b, c, d := ReadInt4()
        k := ReadInt()

        pen := (a + (c - 1)) / c
        pencil := (b + (d - 1)) / d
        if pen+pencil > k {
            fmt.Println(-1)
        } else {
            fmt.Println(pen, pencil)
        }
    }
}

オーバーフローとゼロ除算に注意するぐらい。

B. Rooms and Staircases

問題URL

問題

※問題URLの図がわかりやすいため、ここでは要点のみ。

Nikolayは2階建ての家に住んでいる。家のそれぞれのフロアには n 個の部屋があり、一列に並んでいる。 左から 1 ~ n の番号が振られている。

同じフロアの隣り合っている部屋はすべて移動可能である。 また、いくつかの部屋には1階と2階をつなぐ階段がある場合があり、その場合は、各階同じ番号の部屋を行き来できる。

Nikolayは以下の2つのルールを守りながら、できるだけ多くの部屋を回りたい。 回れる部屋の最大個数を答えよ。

  • スタートする部屋は好きに選ぶことができる。
  • 一度通った部屋は二度と通ることはできない。

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

制約:

  • 1 <= t <= 100
  • 1 <= n <= 1000

解答

※とりあえずはコードのみ。

いずれかのフロアの端の部屋から出発したほうがよく、出発地点からできるだけ遠くの階段のある部屋まで移動する。 階段を使ったあとは、また別フロアの出発地点の部屋番号の部屋まで戻る。

複数の出発地点のうち、回ることができた部屋数が大きい方を出力する。

var t int

func main() {
    t = ReadInt()

    for i := 0; i < t; i++ {
        n := ReadInt()
        S := ReadRuneSlice()

        allZero := true
        for i := 0; i < n; i++ {
            if S[i] == '1' {
                allZero = false
                break
            }
        }
        if allZero {
            fmt.Println(n)
            continue
        }

        if S[0] == '1' || S[n-1] == '1' {
            fmt.Println(2 * n)
            continue
        }

        minIdx, maxIdx := 0, n-1
        for j := 0; j < n; j++ {
            if S[j] == '1' {
                minIdx = j
                break
            }
        }
        for j := n - 1; j >= 0; j-- {
            if S[j] == '1' {
                maxIdx = j
                break
            }
        }

        res := Max(2*(maxIdx+1), 2*(n-(minIdx)))
        fmt.Println(res)
    }
}

正当性はどうやって保証するのだろう。。?

C. The Football Season

問題URL

問題

Berlandのフットボールのシーズンが終わった。 Berlandフットボールのルールによると、それぞれの試合は2つのチームで争われる。 試合結果は、引き分けかどちらか片方のチームの勝利・敗北のいずれかである。 チームが勝つと勝利チームに w ポイントが入り、負けると敗北チームは点数を獲得できない。 また、引き分けの場合は両チームに d ポイントが入る。

マネージャは結果をまとめようとしたが、詳細を紛失してしまい、 残されているのは n 試合で p ポイント獲得した、という情報のみだった。

これらの情報から x, y, z 、すなわち勝利数、敗北数、引き分け数を求めて出力せよ。 答えが存在しない場合は -1 を出力せよ。

制約: 1 <= n <= 10^12, 0 <= p <= 10^17, 1 <= d < w <= 10^5

解答(2019-10-14追記)

制約が大きすぎるため、愚直に全探索するとTLEしてしまう。

以下の2つを抑えると、全探索の範囲を大幅に小さくできる。

  1. w > d のため、 x をできるだけ大きくした方が良い、すなわち、 y は小さい値から探索すれば良い。
  2. 1と併せて考えると、 y < w までの探索で打ち切って良い。

1はほとんど自明だが、2は以下のようにして考えられる。

y = m*w + y' (m >= 0, 0 <= y' < w) とすると、 y 試合引き分けとなったことによって取得できる点数は d*y = d*m*w + y'*d である。 ここで、得点 d*m*wd*m 試合勝った場合の得点と同じである。 1より、 y 試合引き分けと考えるよりも y' 試合引き分けと考えたほうが良いため、 0 <= y < w で十分。

y が決まれば x, z も与えられた方程式から順に決まるため、それぞれ0以上の整数であればそれを出力すれば良い。。

var n, p, w, d int64

func main() {
    n, p, w, d = ReadInt64_4()

    for y := int64(0); y < w; y++ {
        if (p-d*y)%w == 0 {
            x := (p - d*y) / w
            z := n - x - y

            if x >= 0 && y >= 0 && z >= 0 {
                fmt.Println(x, y, z)
                return
            }
        }
    }
    fmt.Println(-1)
}

Codeforcesの本コンテストのブログのやりとりを参考にしました。 (多分、整数問題たくさん解いてきた人には典型なんだろうなぁ。)

本番中は拡張ユークリッドの互除法固執してしまい、全く手が出ませんでした。

さっさと諦めるのがベストだったので、愚直に問題と向き合うだけではなく、選球眼も磨いていきたいところです。

D. Paint the Tree

問題URL

問題

n 頂点からなる木が与えられる。 木は、無向で連結で閉路のないグラフである。

木の各頂点を、3つの色のうち1つを選んで塗らなければならない。 各頂点について、いずれかの色で塗る場合のコストがわかっているとする。

色を塗る際は、以下のルールに従う必要がある。

木の任意の3つの頂点として、 (x, y, z), x != y, y != z, z != x, xとyは1つの辺でつながっている, yとzは1つの辺でつながっている というものを考えたとき、 x, y, z はそれぞれ違う色で塗られなければならない。

このようなルールのもとですべての頂点を塗るときの、最小コストを求めよ。 また、塗り方が存在しない場合は -1 を出力せよ。

解答

一見、色々なことをやらなければいけないように見えるが、 以下の図に示すように、ある頂点の次数が3以上になるともうアウトになってしまうことがわかる。

f:id:maguroguma:20191014002327j:plain
次数3以上の頂点が存在するとうまく塗れない

よって、すべてのノードの次数は2以下でなければならず、ノードが一列に並んだような木しか考えなくて良い。

次に、その塗り方も単純で、次数が1のノードから塗り始めて、つながっているまだ塗っていないノードを順次塗っていくと、 最初の2つの色を決めた時点で、以降は自動的に塗るべき色が定まることがわかる。

f:id:maguroguma:20191014002025j:plain
次数1のノードから塗り方を決めていく

図にも示したとおり、塗り方はせいぜい12通りしかないため、その 塗り方をすべて試して最小の塗り方はどれか、を調べれば良い。

訂正: くるさんより訂正いただきました。 順方向の6通りだけで十分網羅できています(2つの連続ノードの塗り方は、2色の選び方が Comb(3, 2) 通りでその2色の並べ方が 2! 通りのため積で6通り、そして2つ決まればすべてが決まるので6通りで十分)。

実装部分が本体だと思うので、コードについても補足。

次数を調べたりする部分は素直にやればよいが、色の塗り方の持ち方などは色々な方針がある。 なるべくバグらせないように気をつけながら、実装方針として以下のように考えた。

  1. 毎回根から探索するのは大変なので、ある根から見た頂点のつながっている順番を配列で持っておく( orders )。
  2. 12通りの塗り方について、各ノードの色をすべて保存しておく( howto )。
  3. 各塗り方については前処理に従ってコストの計算のみに集中する。
var n int
var C [4][]int
var edges [100000 + 5][]int
var degins [100000 + 5]int
var howto [20][100000 + 5]int
var orders [100000 + 5]int

func main() {
    n = ReadInt()
    C[1] = ReadIntSlice(n)
    C[2] = ReadIntSlice(n)
    C[3] = ReadIntSlice(n)
    for i := 0; i < n-1; i++ {
        u, v := ReadInt2()
        u--
        v--
        edges[u] = append(edges[u], v)
        edges[v] = append(edges[v], u)
    }

    for i := 0; i < n; i++ {
        for _, e := range edges[i] {
            degins[e]++
        }
    }

    for i := 0; i < n; i++ {
        if degins[i] > 2 {
            fmt.Println(-1)
            return
        }
    }

    roots := []int{}
    for i := 0; i < n; i++ {
        if degins[i] == 1 {
            roots = append(roots, i)
        }
    }

    dfs(roots[0], -1, 0)

    temp := [][]int{
        []int{1, 2, 3}, []int{1, 3, 2},
        []int{2, 1, 3}, []int{2, 3, 1},
        []int{3, 1, 2}, []int{3, 2, 1},
    }
    for i := 0; i < 6; i++ {
        for j := 0; j < n; j++ {
            howto[i][orders[j]] = temp[i][j%3]
        }
    }
    for i := 6; i < 12; i++ {
        for j := 0; j < n; j++ {
            howto[i][orders[n-1-j]] = temp[i-6][j%3]
        }
    }

    ans := int64(1 << 60)
    ansOrderIdx := -1
    for i := 0; i < 12; i++ {
        tmpAns := int64(0)

        for j := 0; j < n; j++ {
            c := howto[i][j]
            tmpAns += int64(C[c][j])
        }

        if ans >= tmpAns {
            ans = tmpAns
            ansOrderIdx = i
        }
    }

    fmt.Println(ans)
    for i := 0; i < n; i++ {
        if i == n-1 {
            fmt.Println(howto[ansOrderIdx][i])
        } else {
            fmt.Printf("%d ", howto[ansOrderIdx][i])
        }
    }
}

func dfs(cid, pid, curIdx int) {
    orders[curIdx] = cid
    for _, e := range edges[cid] {
        if e == pid {
            continue
        }
        dfs(e, cid, curIdx+1)
    }
}

実装ゲーでした。 強い人達は「冗長、虚無」といった感想だったようですが、 自分レベルだと実装面ではできるだけバグらせにくい実装を考える労力が必要で、 やる価値はあるかと思います。


個人的な体感難易度は A < D < B << C でした。

Codeforcesはフルフィードバックはないことを加味すると、自分の性格上、AtCoder以上に早解き勝負に期待できないので、 すこしでも詰まったら積極的に次の問題にシフトしたほうが良さそうです。

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

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

Dについても近々追記するかと思います。

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つのみの場合について例外的に扱う必要が出てきてしまいました。

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


感想

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

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

競技プログラマーにアピールしたいVim/VSCodeVim

この記事の目的

エディタに興味の薄い競技プログラマー(あるいは誰でも)に、「Vimちょっと調べてみようかな、遊んでみようかな」と少しでも思ってもらうことです。

導入

私は昨年の4月に働き始めてからVimを使い始めて、1年半ほど経った今ではVimキーバインドは手放せないものとなりました。

職場で周囲のほとんどの人がVimを使っていたことから、「きっと素晴らしいものなんだろう」と思いはじめました。 当時は研修中で比較的時間に余裕があったため、帰宅してからVimについて調べたり練習したりしていました。

また一方で、昨年9月頃から始めた競技プログラミングでは、素早く問題を解くことが重要で、ひいては高速なコーディングがプレイする上で有利になります。 最近ではVSCodeを使っている競技プレイヤーも多いようですが、幸いVSCodeにはVSCodeVimという優れたVim拡張があります。 多少の初期投資によって今後一生活かせる、快適で高速で、そしてなにより楽しいコーディング体験をしてみませんか。

Vimって難しいんじゃないの?

しばしば、Vimの習得難易度は高いと聞きます。 自分もVimを使い始めるまではそう思っていましたし、実際にそのとおりな部分もあると思います。 しかしながら、標準のキーバインドや初歩的なコマンドを常用して快適にコーディング・文書作成する分には、それほど難しいものではないと思っています *1

自分の場合、よく使うコマンドを整理した上で数週間Vim縛りでコーディング、テキスト編集をしていたら、自然と定着していました。

Vimを覚えるためのモチベーション

「これは便利そう」と思えるような「かんたんな」操作を実際に観てみる のが一番いい気がします。

よく「とりあえずvimtutorをやってみよう」とか「実践Vimという本を読むといいよ」と呼びかけているのを見かけます。 しかしながら、これらを両方完遂できる人はすでに決意が硬い人であって、殆どの「やってみようかな」レベルの人は途中で折れるか飽きてしまうような気がします *2

いずれはこれらについても一度さらっておいたほうがいいのは間違いないのですが、 まずは強い動機づけをすることで、意欲を保ったまま効率的に学習できると考えています。 そのために、黒魔術のようなとても覚えられそうにないものではなく、すぐにでも便利に使えそうな操作を「下見してみる」のが良いかと思います。

私が1年半ほど使ってみて、今でも変わらずに便利だと思っておりかつかんたんな操作は、以下のようなものです。

テキストオブジェクトの操作

私がVimを学び始めて一番「おおっ」となったのはこれで、今でも他人に勧めたい操作No.1です。

かんたんに紹介すると、例えば ciw は "correct in word" の略で、現在カーソルが置かれている単語を削除しインサートモードに移行するコマンドです。 削除後にインサートモードに移行してくれるおかげで、単語を即座に修正することができます。

f:id:maguroguma:20191009201214g:plain
カーソル位置の単語の修正

あるいは、 da" とすると "delete all "" の略で、現在カーソルが置かれておりダブルクォートで囲まれている部分を、 ダブルクォート含めてすべて削除するコマンドです。

f:id:maguroguma:20191009201306g:plain
カーソル位置の二重引用符部分の削除

これらのコマンドを XYZ と表すなら、 X = {c(correct), d(delete), y(yank, copy), v(visual)}, Y = {i(in), a(all)}, Z = {(, ), [, ], ", ', w, ...} というようなバリエーションが有り、それぞれの要素数の掛け算の数だけ異なった操作ができることになります。

同様な操作を普通のエディタでやるならば、マウスカーソルで正確にドラッグする手間が必要だと思います。 あるいは、カーソルを消したい文字の一番右に移動させてからback space長押し、とかでしょうか。

一方、Vimであれば「雑に」目標位置にカーソルを移動させたあと、上記の3つのキーを押下するだけで、所望の結果が達成できます。

ノーマルモードにおける o コマンド

めちゃくちゃ地味なんですが、これを知ったときかなり嬉しかったのを覚えています。

このコマンドは、現在のカーソル位置に関わらず、1つ下に改行してインサートモードに移行します。 行の途中にカーソルがあるけど、すぐ下に改行したい、というケースは結構あるのではないでしょうか。

f:id:maguroguma:20191009201347g:plain
行末以外で改行

これも普通のエディタだと、「カーソルを行末に移動させてEnter」という手間が必要だと思いますが、Vimならばキー入力一回のみです *3

dd による1行削除、 yy による一行コピー

これもとても地味ですが、1行単位で削除したりコピーしたりというのは、頻繁に行う操作の1つかと思います。 Vimでは、これらはそれぞれ dd および yy で実現できます。 p で後ろにペーストできます。

f:id:maguroguma:20191009201427g:plain
カーソル位置の行削除とカーソル後へのペースト

普通のエディタを使っていた頃は、複数回左クリックし行を選択してからback spaceもしくはctrl+cとかやっていました (行全体を選択するのに2回でいいときと3回やらないとダメなときとかがあって、ちょっといらっとするときがあります)。

surround.vimによる「なにかを囲むもの」に対する操作

Vimネイティブなものではなく、プラギンの範疇なのですが、おそらくは導入することになるので紹介しています。

ちょっと操作がややこしくなりますが、例えば以下のように、ビジュアルモードで選択した範囲について Sb もしくは S( と打つと、 選択範囲を丸括弧で囲んでくれます。

f:id:maguroguma:20191009201519g:plain
選択範囲を丸括弧で囲む

また、ビジュアルモードを介さなくても、先述のテキストオブジェクトの要領で ysiw" と打つと、 現在カーソル位置にある単語に対してダブルクォートで囲むことができます。

f:id:maguroguma:20191009201608g:plain
カーソル位置の単語を二重引用符で囲む

あるいは、既存の「囲んでいるもの」を別のものに置換することもできます。 例えば、 cs'" と打つと、現在のカーソル位置を囲んでいる最近傍のシングルクォートを、ダブルクォートで置換します。

f:id:maguroguma:20191009201739g:plain
単引用符を二重引用符に置換

もう予想がつくかもしれませんが、 dsb とすると、カーソル位置を囲む最近傍の丸括弧を削除します。

f:id:maguroguma:20191009201840g:plain
既存の丸括弧を削除

紹介した操作の中ではちょっとだけ複雑ですが、何回も使っていると忘れないぐらいには頭に染み込んできます。 直前に別のプログラミング言語を使っていて、「この言語では丸括弧が必要なのに丸括弧なしで書いちゃった」というときなどはよく使っています。


ごく一部ですが、私が特に便利だと感じている操作を紹介しました。 殆どの操作において、普通のエディタならばマウスや矢印キーを慎重に使うことが要求されるのに対し、Vimでは雑かつ楽に実行できます。

VSCodeVim: VSCodeVim拡張

VSCodeにおけるVim拡張がVSCodeVimなんですが、話を聞いたところ他のIDEVimプラグインに比べて出来がいいようです*4

個人的に優れていると思うのは、以下の点です。

  1. オリジナルのキーマッピング設定が(それなりに)可能、初心者によっては.vimrcよりも書きやすいかも
  2. 有名なVimプラギンがデフォルトで有効になっている
  3. VSCodeオリジナルの機能とのバッティングがない(自分が知らないだけかも)

1については、例えば ESCjjマッピングしたりだとか、 ctrl + h,l について、ノーマルモード時はビューグループ間の左右移動でインサートモード時はカーソルの1文字左右移動にしたりとか、 モードごとに動作を変えたりもできます。 なので、込み入ったものでなければ.vimrcに記述しているようなカスタムマッピングは、たいていVSCodeVimでも再現できます。

2については、surround.vim, easymotion, commentary.vimなどが該当します*5

雑に紹介しておくと、easymotionはカーソル移動に関するプラギンで、例えば <space><space>j と打つと*6、下方向へのジャンプのアシスト文字が表示され、 対応する文字を入力すると、文字が付与されている部分にカーソルがジャンプします。

f:id:maguroguma:20191009201913g:plain
easymotionのデモ

また、commentary.vimはコメント補助のプラギンで、 gcc とだけ打つとカーソル位置の行をコメントアウトしてくれます。 また、行ビジュアルモードで複数行選択している状態で gc と打つと、その行範囲をすべてコメントアウトしてくれます。

f:id:maguroguma:20191009201945g:plain
カーソル位置の行をコメントアウト
f:id:maguroguma:20191009202017g:plain
選択した複数行をコメントアウト

3については、そもそもVSCode本来の機能で便利なものが多いため、VSCodeの強みとVimの強みの両方を享受できます。 VSCodeの話になりますが、ファジーファインダーになっているquickOpenが特にお気に入りです。

インストール方法はVSCodeの他の拡張機能と同じで、簡単に導入・破棄できます。 「ちょっとだけVim試してみよう」と思ったら是非気軽にインストールしてみてください。

おまけ: Vimを学ぶことによる副次的なメリット

ある程度Vimに習熟してから気づいたことですが、以下のようなメリットがあったことに気づきました。

  • いくつかのVimキーバインドとシェルのショートカットが同じであるため、シェルの操作も効率的に行えるようになる
  • 置換コマンドを覚えると同時に、かんたんなsedコマンドの使い方も覚えられる
  • 置換コマンドを覚えると同時に、正規表現も覚えられる
  • CUIに抵抗がなくなる、CUIが好きになる

1年目はフロントエンドの業務がほとんどであり、シェルを操作する機会が少なかったため、 このあたりの抵抗が早めになくせたのは、個人的には結構大きいと思っています。

これらをVimを学習する主たる動機にするのは難しいと思いますが、一応触れておこうと思いました。

おわりに

Vimの解説記事などは出尽くしており、今更自分が書くほどでもないと思ったので、 「自分はVimのここが好きで、そんなに導入コストは高くないと思うから試してみて!」という部分に特化した内容をまとめてみました。

自分自身、これまでVimのいいところに触れる機会がなく、もっと早く知っていればなぁと思ったりしたので、 若い人などで「Vimってなんなの?」と思っている人が少しでも興味を持ってくれたりするととても嬉しいです。

ちなみに、私は業務ではVSCodeを、競技プログラミングではneovimを使っています*7

*1:Vim scriptや周辺技術をちゃんと理解してプラギンを管理したり、あるいはプラギンを自作するとなると、とても難しくなってくるという認識です。

*2:どちらも優れた教材なのは疑いようがなく、実際に私も両方やりました。

*3:これは流石に自分のエディタ操作スキルが低いだけで、それぞれのエディタでショートカットがあるものなのかもしれません。

*4:聞いたところによると、Vimの基本的な機能もエミュレートできていないものもしばしばあるとか。

*5:最近はREADMEを読めていないので、もう少し増えているかもしれません。

*6:厳密には、Leaderをspaceキーにマッピングする設定が必要です。

*7:GoとVimの相性が良いのと、neosnippetがとても使いやすい。

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

初めての unrated codeforces を体験してしまいました。

A, B, Cがコンテスト後に確認したところちゃんと通っており、Dは嘘解法だったようでpretestで弾かれていました。

Dも勉強になりそうな雰囲気なので、後日解説ACの上追記していきます(2019-10-11に追加)。

全体

A. CME

問題URL

問題

※長いので意訳。

q 個のクエリに対して n が与えられる。

n 本のマッチ棒を必ず使い切り a + b = c という数式を満たすようにマッチ棒を a, b, c に割り当てる。

ただし、 a, b > 0 でなければならない。

数式を作る際にマッチ棒が足りない場合、好きな本数買い足すことができる。

n に対して、買い足す必要のあるマッチ棒の本数の最小値をそれぞれ答えよ。

制約: 1 <= q <= 100, 2 <= n <= 10^9

解答

必要なマッチの総本数は明らかに偶数であり、逆に偶数本マッチがあればCMEを作れる。

なので、 n が偶数ならば 0 、奇数ならば 1 とすれば良い。

ただし、 n = 2 のときは a + b = 1 となり、いずれかが 0 となって条件を満たせなくなる。 これを避けるために、左辺と右辺にそれぞれ 1 ずつ足す必要があり、2 本必要となる。

var q int

func main() {
    q = ReadInt()
    for i := 0; i < q; i++ {
        n := ReadInt()

        if n%2 == 0 {
            if n/2 == 1 {
                fmt.Println(2)
            } else {
                fmt.Println(0)
            }
        } else {
            fmt.Println(1)
        }
    }
}

上で「明らかに」とか言ってますが、コンテスト中は無為に数式こねくり回してますし、 前日のAGCで太陽拝んでしまった後遺症でコーナーケース探りまくっていて、 提出に15分かかっています。

B. Strings Equalization

問題URL

問題

2つの英小文字からなる、同じ長さの文字列 s, t が与えられる。 「操作」は何回行っても良い(0回でも良い)。

操作では、どちらの文字列についてでも、2つの隣り合った文字に関して、1つ目に選んだ文字を2つ目に選んだ文字に代入して良い。

q 個のクエリが与えられるので、それぞれの s, t について、任意回数の操作のもとで s, t を等しくできるかどうか判定せよ。

制約: 1 <= q <= 100, 1 <= |s| = |t| <= 100

解答

制約が小さく、文字列を全部舐めても大丈夫なことを抑える。

「何回でも操作ができる」というのが強力で、ある文字列中に存在する1文字によって、 それを左右に伝搬する形でその文字列の他の文字列を上書きしてしまえる。

よって、 s, t について舐めて、「それぞれに同じ文字が1文字でも存在すればOK、なければNG」とする。

var q int

func main() {
    q = ReadInt()

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

        smemo := [ALPHABET_NUM]int{}
        tmemo := [ALPHABET_NUM]int{}

        for j := 0; j < len(S); j++ {
            s, t := S[j], T[j]
            smemo[s-'a']++
            tmemo[t-'a']++
        }

        flag := false
        for j := 0; j < ALPHABET_NUM; j++ {
            if smemo[j] > 0 && tmemo[j] > 0 {
                flag = true
                break
            }
        }
        if flag {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
    }
}

これも10分弱悩まされてしまったのが悔しい。

C. Save the Nature

問題URL

問題

※長いので意訳。

n 枚のチケットを好きな順番で売ることができる。 売上の一部は以下の規則のもとで、環境保全基金に寄付される。

  • a の倍数番目で売られたチケットの x %が寄付される。
  • b の倍数番目で売られたチケットの y %が寄付される。
  • a, b の公倍数番目で売られたチケットの x + y %が寄付される。

できるだけ少ない枚数のチケット販売で目標トータル寄付金額 k を寄付したい。

目標を達成するためのチケット販売枚数の最小値を答えよ。 また、全チケットを販売しても目標が達成できない場合は -1 を出力せよ。

クエリが q 個与えらるため、それぞれについて答えよ。

制約:

  • 1 <= q <= 100
  • 1 <= n <= 2 * 10^5
  • 100 <= p[i] <= 10^9, p[i] % 100 = 0
  • 1 <= a, b <= n, 1 <= x, y <= 100, x + y <= 100
  • 1 <= k <= 10^14
  • チケットの全クエリの合計は 2 * 10^5 を超えない。

解答

当然ながら、各クエリについてすべてのチケットの順列を総当りすることはできない。

また、チケットの金額が高いものほど、寄付割合の高い順番に配置したいが、 できるだけ少ない枚数のチケットで目標を達成したいという縛りがあるため、 貪欲に a, b の公倍数番目に高いチケットを配置するわけにはいかない。

とりあえず「答えを m 枚として、目標を達成できる最適なチケットの並べ方」をイメージしてみる。

このような並び方を考えたとき、 m 枚のチケットは、すべてのチケットを高い順に並べたときの金額の上位 m 枚となるはずである。 (仮に、必ずしも高い順に m 枚となっていなくても目標を達成できる場合、上位 m 枚に入らないチケットと上位 m 枚のチケットと交換しても、金額的に損しないので変わらずに目標を達成できる。)

また、 m 枚のチケットで目標が達成できるとき、 m + 1 以上のチケットでも当然目標が達成できる。

よって、二分探索で m の境界を探索してやればよい。

m 枚で条件を達成できるかの判定は、少し横着をして n * logn で行うことにした。

※大雑把な見積もりでも、

logn[i] * n[i]logn[i] = n[i](logn[i])^2 <= n[i](logn)^2 (n = Sum(n[i])) より、

Sum(n[i](logn[i])^2) <= (logn)^2 * Sum(n[i]) = n * (logn)^2 なので、間に合いそうと判断。

var q int

func main() {
    q = ReadInt()

    for i := 0; i < q; i++ {
        n := ReadInt()
        P := ReadIntSlice(n)
        for j := 0; j < n; j++ {
            P[j] /= 100
        }
        x, a := ReadInt2()
        y, b := ReadInt2()
        k := ReadInt64()

        sort.Sort(sort.Reverse(sort.IntSlice(P)))
        percents := make([]int, n)
        for j := 0; j < n; j++ {
            if (j+1)%a == 0 && (j+1)%b == 0 {
                percents[j] = x + y
            } else if (j+1)%a == 0 {
                percents[j] = x
            } else if (j+1)%b == 0 {
                percents[j] = y
            }
        }

        isOK := func(m int) bool {
            tmp := make([]int, m)
            for h := 0; h < m; h++ {
                tmp[h] = percents[h]
            }
            sort.Sort(sort.Reverse(sort.IntSlice(tmp)))

            val := int64(0)
            for h := 0; h < m; h++ {
                val += int64(tmp[h]) * int64(P[h])
            }

            if val >= k {
                return true
            }
            return false
        }

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

        if isOK(ok) {
            fmt.Println(ok)
        } else {
            fmt.Println(-1)
        }
    }
}

正しい考察にたどり着くまでに結構時間がかかってしまったので、この速度を上げるように努めたいです。

D. Sequence Sorting(※2019-10-11に追加)

問題URL

問題

整数の数列 A が与えられる。

この数列に対して、1回の操作で、ある要素 x を選んだときに、すべての x を一番右、もしくは一番左に移動させることができる。

各クエリについて、最終的に、数列が非減少となるようソートするために必要な操作回数の最小値を答えよ。

制約:

  • 1 <= q <= 3*10^5
  • 1 <= n <= 3*10^5
  • 1 <= n <= n
  • クエリに渡って n の合計は 3*10^5 は超えない。

解答

すべての要素について非減少となるようソート済みの数列に対して、 初期状態ですでにソート済みの部分列(間になにか「不純物」が挟まっていてもいい)を考える。 このソート済みの部分列の長さを l とし、数列中のユニークな要素の数を t とすると、 t - l の要素については必ず一度は左・右のいずれかに寄せる必要がある。 また、正しい順番であればそれぞれの操作対象の要素について1回のみ右・左のいずれかに寄せれば、目的のソート済み数列が得られる。

よって、一番長いソート済みの列の長さを求めることを考える。 これを数えるためには、数列中における各要素 x について、その登場位置の最大・最小をそれぞれ前計算して求めておくことで計算できる。 前計算のあとは、ユニークな要素を昇順ソートしたものに対し、前から順に見て「小さい方の要素の最大位置 < 大きい方の最小位置」となっていれば、 今注目している部分列の長さを加算し、そうでなければリセット、というふうにして線形探索すればよい。

各クエリにおいて、ソート部分がネックになるため、計算量は O(nlogn)

var q int

func main() {
    q = ReadInt()

    for i := 0; i < q; i++ {
        n := ReadInt()
        A := ReadIntSlice(n)
        maxIds, minIds := make(map[int]int), make(map[int]int)

        // A[j]のmax, minなidxを記録
        for j := 0; j < n; j++ {
            maxIds[A[j]] = j
        }
        for j := n - 1; j >= 0; j-- {
            minIds[A[j]] = j
        }

        // A[j]についてuniq | sortする
        uniqs := []int{}
        for k := range maxIds {
            uniqs = append(uniqs, k)
        }
        sort.Sort(sort.IntSlice(uniqs))

        ans := 1
        tmpAns := 1
        for j := 0; j < len(uniqs)-1; j++ {
            l, r := uniqs[j], uniqs[j+1]
            if maxIds[l] < minIds[r] {
                tmpAns++
            } else {
                ChMax(&ans, tmpAns)
                tmpAns = 1
            }
        }
        ChMax(&ans, tmpAns)
        fmt.Println(len(uniqs) - ans)
    }
}

Goだと実行時間が1100msecぐらいになってました。 n = 3*10^5 における O(nlogn) あたりからはあまり横着した実装をしないように注意するべきなのかもしれません。 (minIdx, maxIdx は範囲が小さいのでちゃんと固定長配列とかでやるべきだったかも。)


感想

Cとかは別にクエリ形式にする必要ないのでは。。?

社会人として、日曜0時スタートのコンテストが unrated になるのはなかなか心にくるものがありますが、 問題自体は楽しいので引き続き参加していきたいです。

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

全体

残り時間15分ぐらいで後回しにしたCが解けて5完でした。

Cに時間がかかりすぎてしまったのは悔やまれますが、実力的に何回参加しても好転はしないと思います。

Eはコンテスト中に目を通せて「面白そう」と思ったので、後日解き直しました(解説ACになりましたが)。


A. Equalize Prices Again

問題URL

問題

※やたらと長いので意訳。

各値段が A[i] コインである n 個の商品のすべての値段を等しくしたい。 もともとの商品の値段合計よりも小さくならないという条件のもとで、金額はいくらに設定すればよいか。

このようなクエリが q 個与えられるので、それぞれについて答えよ。

制約: 1 <= q <= 100, 1 <= n[i] <= 100, 1 <= A[i] <= 10^7

解答

各クエリの情報を読み込みながら、都度 Ceil(sum / n) を計算すれば良い。

var q int

func main() {
    q = ReadInt()
    for i := 0; i < q; i++ {
        n := ReadInt()
        A := ReadIntSlice(n)

        sum := Sum(A...)
        fmt.Println((sum + (n - 1)) / n)
    }
}

特に言うことはないと思います。

B1. Social Network (easy version)

問題URL

問題

※問題文があまりにも冗長なので省略。

解答

要するに、以下を守りながら、ディスプレイを配列でモデル化し、シミュレーションを行えば良い。

  • 次に処理するメッセージがすでにディスプレイに表示されているのならば、何もしない。
  • 次に処理するメッセージが表示されていない場合は、そのメッセージを配列の先頭に挿入する。
  • ディスプレイサイズが k を超える場合、配列の最後尾のメッセージを配列から除外する。

最後に、シミュレーション終了時の配列を出力すればOK。

なお、easy versionは制約が小さいので、配列の調整やメッセージの存在チェックを適当に都度スキャンしても通る。 実際に、コンテスト中は完全なシミュレーションに集中したので、効率化を一切考えないコードを書いた。

var n, k int
var A []int
var Ids []int

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

    Ids = []int{}
    for i := 0; i < n; i++ {
        a := A[i]

        if isExist(a) {
            continue
        }

        newIds := []int{}
        newIds = append(newIds, a)
        if len(Ids) < k {
            newIds = append(newIds, Ids...)
        } else {
            newIds = append(newIds, Ids[:len(Ids)-1]...)
        }
        Ids = newIds
    }

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

func isExist(id int) bool {
    for i := 0; i < len(Ids); i++ {
        if id == Ids[i] {
            return true
        }
    }
    return false
}

正直英文読解が最大の敵だと思いました (サンプル見るまで確信が持てませんでしたし、なんならサンプル見るまで勘違いしている部分もありました)。

B2. Social Network (hard version)

問題URL

問題

※easy versionと問題設定は全く同じ。

制約: 1 <= n, k <= 2 * 10^5, 1 <= Id[i] <= 10^9

解答

総メッセージ数とディスプレイサイズが大きくなったため、easy versionのコードは通らなくなった。 具体的には、

  • 存在チェックの際、ディスプレイをスキャンしている
  • メッセージの出し入れの部分を、新しい配列に順番が正しくなるようにすべて詰め直している

部分がまずい。

それぞれ、

  • 存在チェックを map で行う
  • ディスプレイの向きを逆向きにすることでQueueでディスプレイをモデル化できるため、出し入れが O(1) で可能になる。

というふうに変更する。

var n, k int
var A []int
var Ids []int
var memo map[int]int

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

    memo = make(map[int]int)
    for i := 0; i < n; i++ {
        memo[A[i]] = 0
    }

    Ids = []int{}
    for i := 0; i < n; i++ {
        a := A[i]

        if isExist(a) {
            continue
        }

        // 追加
        memo[a] = 1

        Ids = append(Ids, a)
        if len(Ids) <= k {
            continue
        } else {
            memo[Ids[0]] = 0
            Ids = Ids[1:]
        }
    }

    fmt.Println(len(Ids))
    reverseIds := rev()
    fmt.Println(PrintIntsLine(reverseIds...))
}

func isExist(id int) bool {
    if value, ok := memo[id]; ok {
        if value == 1 {
            return true
        } else {
            return false
        }
    } else {
        return false
    }
}

func rev() []int {
    res := []int{}

    for i := len(Ids) - 1; i >= 0; i-- {
        res = append(res, Ids[i])
    }

    return res
}

C. Pipes

問題URL

問題

2行n列のマス目に対して、各マスに6種類のパイプが設置されている。 各マスのパイプを時計回り・反時計回りに90度単位で何回も回転させて良い。 左上から流入する水を、右下に流出させることが可能か答えよ。

また、このようなクエリは q 個与えられ、それぞれについて n およびパイプの配置が与えられるので、 それら全てに答えよ。

※パイプの種類や水の流し方に関する制約は、問題文の図が詳しいのでそちらをご参照ください。

制約: 1 <= q <= 10^4, 1 <= n <= 2 * 10^5(n の総和は 2 * 10^5 を超えないことが保証される)

解答

行列の列の総和がboundされているため、素直にクエリごとに各マスのパイプをチェックして問題ない。

整理すると、問題がシンプルになる。

  • パイプ1, 2は互いに同じで、パイプ3, 4, 5, 6はそれぞれ互いに同じ
  • 水を左方向に流す意味はない
  • 3, 4, 5, 6のパイプを経由して行方向を上・下に移動した後に1, 2のパイプに出会った場合は、確実に失敗する
    • それぞれ行列を上・下に踏み外すか、水が流れなくなるかのいずれかのため

以上から、初期位置を (0, 0) とし、出会ったパイプの種類によって座標を変化させていけば良い。

var q int
var n int
var Rows [2][]rune

func main() {
    q = ReadInt()

    for i := 0; i < q; i++ {
        n = ReadInt()
        Rows[0] = ReadRuneSlice()
        Rows[1] = ReadRuneSlice()
        // 現在地
        h, w := 0, 0

        for w < n {
            if Rows[h][w] == '1' || Rows[h][w] == '2' {
                w++
            } else {
                if h == 0 && (Rows[1][w] == '1' || Rows[1][w] == '2') {
                    fmt.Println("NO")
                    break
                }
                if h == 1 && (Rows[0][w] == '1' || Rows[0][w] == '2') {
                    fmt.Println("NO")
                    break
                }

                if h == 0 {
                    h++
                    w++
                } else {
                    h--
                    w++
                }
            }

            if w == n {
                if h == 0 {
                    fmt.Println("NO")
                } else {
                    fmt.Println("YES")
                }
            }
        }
    }
}

It is guaranteed that the sum of n over all queries does not exceed 2 * 10^5 を見落としたため、無理だと思って先にDを解きました。

実装で手間取りすぎてこの問題だけで1時間弱使ってしまった結果を見ると、正しい動きでした。

D. Distinct Characters Queries

問題URL

問題

英小文字のみからなる文字列 s と、この文字列に関する q 個のクエリが与えられる。

s[l;r]s の部分文字列 s[l], s[l+1], ..., s[r] とする。

クエリは2つのタイプからなる。

  1. 1 pos c: s[pos]c で置換する
  2. 2 l r: 部分文字列 s[l;r] 内の異なる文字の個数を計算する

各クエリに答えよ。

制約: 1 <= |s| <= 10^5, 1 <= q <= 10^5

解答

26種類の文字について累積和が計算できれば、与えられた区間内の各文字の個数は計算できるので、 1個以上存在する文字の種類数が答えになる。

しかしながら、あるインデックスについて文字の置換が途中で割り込むため、通常の累積和では再計算していては間に合わない。

BITが要件を満たしており、26個に増やすのも容易に思えたため、BITを採用した。

const ALPHABET_NUM = 26

var S []rune
var q int

// [1, n]
var bit [ALPHABET_NUM][100000 + 5]int
var lenS int

func sum(i, alpha int) int {
    s := 0

    for i > 0 {
        s += bit[alpha][i]
        i -= i & (-i)
    }

    return s
}

func add(i, alpha, x int) {
    for i <= lenS {
        bit[alpha][i] += x
        i += i & (-i)
    }
}

func main() {
    S = ReadRuneSlice()
    q = ReadInt()
    lenS = len(S)

    for i := 0; i < len(S); i++ {
        r := S[i]
        c := int(r - 'a')
        add(i+1, c, 1)
    }

    for i := 0; i < q; i++ {
        query := ReadInt()
        if query == 1 {
            idx := ReadInt()
            R := ReadRuneSlice()
            newc := R[0]
            newcint := int(newc - 'a')
            oldc := S[idx-1]
            oldcint := int(oldc - 'a')

            add(idx, newcint, 1)
            add(idx, oldcint, -1)
            S[idx-1] = newc
        } else {
            l, r := ReadInt2()
            res := 0
            for alpha := 0; alpha < ALPHABET_NUM; alpha++ {
                ss := sum(r, alpha) - sum(l-1, alpha)
                if ss > 0 {
                    res++
                }
            }
            fmt.Println(res)
        }
    }
}

26個の累積和を計算し終わった後に点更新できない事に気づき、紙の蟻本を取りに行きました。

あと提出し終わった後、長さ0の文字列がケースに入っていないかとても心配でした (プログラムがコケるから無いだろうと決め込みましたが。。)。

E. Special Permutations

問題URL

問題

数列 P(i, n)[i, 1, 2, ..., i-1, i+1, ..., n] のように定義する。 すなわち、 n の順列とほとんど同じだが、 i のみが先頭に移動したものである。

また、数列 X: X[1], X[2], ..., X[m] (1 <= X[i] <= n) が与えられる。

pos(P, val) は数列Pが与えられたときの、数列P中における val が位置する1-basedのインデックスである。

ここで、関数 f(P) = Sum(|pos(P, X[i]) - pos(P, X[i+1])|) を定義する。

f(P(1, n), n), f(P(2, n), n), ..., f(P(n, n), n) を求めよ。

解答

問題文でも言われている通り、先頭に何が移動しようが、もとの昇順に並んだ数列 P(1, n) とほとんど同じであることを踏まえると、 関数 f の値もそれぞれ似通いそう、すなわち f(P(1, n), n) を事前にもとめておいて、 それを適切に調整すればうまく求められそうな気はする。

実際、以下の図のように場合分けによって、項間の距離が計算できる。

f:id:maguroguma:20191005170041j:plain
E問題の整理

手順としては、以下のようなものとなる。

  1. 昇順に並んだ数列について関数値を求め、これをベースとする。これは、単純に X の階差の和で求まる。
  2. X[i] について X[i] が先頭に来る場合の X[i-1]X[i+1] との距離( A[i] とする)を計算しておく。先述の図示した内容に従って場合分けすれば良い。
  3. X 中における 1 <= i <= ni が登場する箇所をリスト形式( C[i] とする)で記憶しておく。後半でベースをもとに f(P(i, n), n) を計算する際、リスト C[i] の中身についてのみ、2で求めた値を参照する。もともとベースを計算するために用いた階差が、2で求めた値に置き換わることとなる。
  4. すべての X に置ける隣接項のペア(公式tutorialでは segment というワードが使われている)について、 1 <= i <= ni が間に挟まるものの数を数える。cnt[i] とすると、これが求まればベースから cnt[i] を引くことで、「 i が先頭に来ることによってグループ1とグループ2の間の距離が1縮まる」という部分が、すべての X の隣接項ペアについて考慮できたことになる。普通にやると O(m * n) なので、imos法により O(m + n) で賢く行う。
  5. これまでに前処理したデータを利用し、ベースを調整することで各 f(P(i, n), n) を求める。おおまかな方針は以下のようになる。X[idx] が先頭に移動する場合は、ベースを求めるのに使った階差の代わりに A[idx] を使うようにする。cnt[i] をベースから引く。

コードの最後で2重ループとなっているが、 C の要素数は全部で m であるため、 計算量は O(n + m) となって十分間に合う。

var n, m int
var X []int

var A, diff []int
var C [][]int
var cnt []int

func main() {
    n, m = ReadInt2()
    X = ReadIntSlice(m)

    // Xの階差を計算する、和がf(P1(n))となる
    diff = make([]int, m-1)
    for i := 0; i < m-1; i++ {
        diff[i] = AbsInt(X[i] - X[i+1])
    }

    // X[i]が数列の先頭に来る場合の、前後のxとの位置の差の絶対値を計算しておく
    A = make([]int, m)
    for i := 0; i < m; i++ {
        if i < m-1 {
            if X[i+1] > X[i] {
                A[i] += X[i+1] - 1
            } else if X[i+1] < X[i] {
                A[i] += X[i+1]
            }
        }

        if i > 0 {
            if X[i-1] > X[i] {
                A[i] += X[i-1] - 1
            } else if X[i-1] < X[i] {
                A[i] += X[i-1]
            }
        }
    }

    // X中における、1<=i<=nのiが登場する位置を記憶しておく
    C = make([][]int, n+1)
    for i := 1; i <= n; i++ {
        C[i] = []int{}
    }
    for i := 0; i < m; i++ {
        C[X[i]] = append(C[X[i]], i)
    }

    // cnt[i]: 1<=i<=nのiについて、
    // Xにおけるすべての隣接項間のうち、隣接項間にiが挟まるものの個数
    cnt = make([]int, n+1)
    for i := 0; i < m-1; i++ {
        if AbsInt(X[i]-X[i+1]) < 2 {
            continue
        } else {
            cnt[Min(X[i], X[i+1])+1]++
            cnt[Max(X[i], X[i+1])]--
        }
    }
    for i := 0; i < n; i++ {
        cnt[i+1] = cnt[i+1] + cnt[i]
    }

    base := int64(0)
    for _, d := range diff {
        base += int64(d)
    }
    answers := []int64{}
    for i := 1; i <= n; i++ {
        ans := base
        for _, idx := range C[i] {
            if idx == 0 {
                ans += int64(A[idx] - diff[idx])
            } else if idx < m-1 {
                ans += int64(A[idx] - diff[idx] - diff[idx-1])
            } else {
                ans += int64(A[idx] - diff[idx-1])
            }
        }
        ans -= int64(cnt[i])
        answers = append(answers, ans)
    }

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

// PrintIntsLine returns integers string delimited by a space.
func PrintIntsLine(A ...int64) string {
    res := []rune{}

    for i := 0; i < len(A); i++ {
        // str := strconv.Itoa(A[i])
        str := strconv.FormatInt(A[i], 10)
        res = append(res, []rune(str)...)

        if i != len(A)-1 {
            res = append(res, ' ')
        }
    }

    return string(res)
}

図示したところの、「グループ1とグループ2の要素間はもともとの距離から1縮まる」の部分が、 なぜか自力では最後の方まで抜けてしまっていました。。 気づいてもimos法の適用までには至れず、解説ACとなりました。

個々に要求される知識や実装はそれほど難しいわけではないですが、 しっかり落ち着いて解ききるにはまだ地の力足りてないなぁ、という気がします。

筋トレしましょう。


感想

Codeforcesってクエリ問題多いんですかね?

今回Cでやらかした制約の見落としなんかはこれからもありそうなので気をつけたいと思います。

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

全体

結果は前回と同じくA, Bの2完でしたが、通すべきCを通せなかったので順位もパフォーマンスも惨憺たる事に。。

Dも難易度的にはちょうど良さそうで解いてみたいのですが、 方針としてコンテスト中の集中力がある状態で目を通した問題のみ時間を書けて復習する、としているので、とりあえずはCまでを解きます。


A. Distinct Digits

問題URL

問題

以下の2つの条件を満たす x が存在すれば、どれでも良いので1つ出力せよ。 存在しない場合は -1 を出力せよ。

  • l <= x <= r
  • x のすべての桁の数が異なる

制約: 1 <= l <= r <= 10^5

解答

調べるべき範囲が十分狭いので、全探索を行う。

var l, r int

func main() {
    l, r = ReadInt2()

    for i := l; i <= r; i++ {
        if sub(i) {
            fmt.Println(i)
            return
        }
    }

    fmt.Println(-1)
}

// すべての桁の数字が異なるかどうか?
func sub(n int) bool {
    nn := n
    memo := [10]int{}

    for n > 0 {
        memo[n%10] = 1
        n /= 10
    }

    res := 0
    for i := 0; i < 10; i++ {
        res += memo[i]
    }

    if res == decimalLength(nn) {
        return true
    }
    return false
}

// nの10進数表現の桁数
func decimalLength(n int) int {
    res := 0
    for n > 0 {
        res++
        n /= 10
    }
    return res
}

なんということは無い問題なんですが、個人的にこのような繰り返し整数除算するコードを書くのなんか苦手です(素因数分解とか)。

このときもやたらと石橋を叩いて時間を使いすぎたので、そろそろ自信を持ちたい。。

B. Filling the Grid

問題URL

問題

※長いので意訳

各行・列に与えられた数値が1つのみのロジックパズル(マリオのピクロスみたいなやつ)について、 完成後のパターンとして考えられるものの数を 10^9+7 で割ったあまりで答えよ。

制約: 1 <= h, w <= 10^3

解答

素直にシミュレーションを行う。

行方向について決定するときは素直に決めればよいが、 続いて縦方向について決定するときは、矛盾のチェックを逐次行う。

矛盾が最後までなければ、未確定のマスの数の分だけ2倍していき、都度MODを取れば良い。

var h, w int
var R, C []int

var cells [1000 + 5][1000 + 5]int  // 1: 黒, 0: 白
var dones [1000 + 5][1000 + 5]bool // true: 確定

func main() {
    h, w = ReadInt2()
    R = ReadIntSlice(h)
    C = ReadIntSlice(w)

    // 行は無責任に決める
    for i := 0; i < h; i++ {
        r := R[i]
        for j := 0; j < r; j++ {
            cells[i][j] = 1
            dones[i][j] = true
        }

        // 白で確定させる
        cells[i][r] = 0
        dones[i][r] = true
    }

    // 列はチェックしながら決める
    for j := 0; j < w; j++ {
        c := C[j]
        for i := 0; i < c; i++ {
            if dones[i][j] {
                // すでに決定済みかつ、白でないとダメなら矛盾
                // 黒だったならOK
                if cells[i][j] == 0 {
                    fmt.Println(0)
                    return
                }
            } else {
                cells[i][j] = 1
                dones[i][j] = true
            }
        }

        // 白で確定させる
        if dones[c][j] {
            // すでに決定済みかつ、黒でないとダメなら矛盾
            // 白だったならOK
            if cells[c][j] == 1 {
                fmt.Println(0)
                return
            }
        } else {
            cells[c][j] = 0
            dones[c][j] = true
        }
    }

    ans := int64(1)
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if !dones[i][j] {
                ans *= int64(2)
                ans %= int64(MOD)
            }
        }
    }
    fmt.Println(ans)
}

これまた途中でバグを生んでしまったり、ものすごく時間を使ってしまった。

何気なく i, jイテレータとして使うにしても、列方向は j で固定するなど、 こういった部分で混乱を減らし、極力バグを生みにくくなるように工夫していきたい。

C. Primes and Multiplication

問題URL

問題

※これも長いので省略

与えられた定義のもとで f(x, 1) * f(x, 2) * ... * f(x, n) % (10^9+7) を求めよ。

制約: 2 <= x <= 10^9, 1 <= n <= 10^18

解答

自分の解答が非常に説明しづらいので、大部分を図示する。

f:id:maguroguma:20191005033448j:plain
Cの解法

素直に定義式に従って与えられた式を分解していくと、たくさんの g(?, ?) の積を計算することになる。 特に n が非常に大きく、これをまともに全部計算するわけには行かないので、図示した赤枠の縦方向について効率的に計算できないか考える。 求め方は図中の文章通りで、説明の都合上ところどころ一般化して文字式で置いたりしているが、 コンテスト中は適宜適当な数値を当てはめて考えるとわかりやすいと思う(「例示は理解の試金石」*1)。

指数の計算をする部分は、指数部が大きすぎるので二分累乗法が必要。 逆元のスニペットを作るときに同時に作ることになると思うので、一緒に揃えておきたい。

var x, n int64

func main() {
    x, n = ReadInt64_2()

    primes := TrialDivision(int(x))

    ans := int64(1)
    for p := range primes {
        prod := int64(1)
        for {
            if isOverflow(prod, int64(p)) {
                break
            }

            prod *= int64(p)
            if n < prod {
                break
            }
            num := int64(n / prod)

            tmp := modpow(int64(p), num, MOD)
            ans *= tmp
            ans %= MOD
        }
    }

    fmt.Println(ans % MOD)
}

func isOverflow(i, j int64) bool {
    return !(i < math.MaxInt64/j)
}

func modpow(a, e, m int64) int64 {
    if e == 0 {
        return 1
    }

    if e%2 == 0 {
        halfE := e / 2
        half := modpow(a, halfE, m)
        return half * half % m
    }

    return a * modpow(a, e-1, m) % m
}

// TrialDivision returns the result of prime factorization of integer N.
func TrialDivision(n int) map[int]int {
    if n <= 1 {
        panic(errors.New("[argument error]: TrialDivision only accepts a NATURAL number"))
    }

    p := map[int]int{}
    for i := 2; i*i <= n; i++ {
        exp := 0
        for n%i == 0 {
            exp++
            n /= i
        }

        if exp == 0 {
            continue
        }
        p[i] = exp
    }
    if n > 1 {
        p[n] = 1
    }

    return p
}

上記のコードでオーバーフローチェックをしていますが、本番中に40分かけてもこれに気づけませんでした。。

初歩的とはいえ、このようなつまり方をしたのは初めてだったので、早い段階で自分の中の地雷処理ができたとポジティブに考えておきます。。


感想

百歩譲って未経験のタイプのオーバーフローを解決できなかったのはともかく、 A,Bの実装が遅すぎたのも問題でした。

競技プログラミングの筋トレが全く足りていないので、引き続きCodeforcesで鍛えていきたいと思います。

*1:結城浩さんの数学ガールに登場するらしいですね。いい言葉だと思います。

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

初めてCodeforcesに参加しました。

CodeforcesAtCoderほど日本語の記事が見当たらなかったので、そのあたりモチベーションにしつつブログの練習も兼ねて参加録をつけていこうと思います。

全体

A, Bの2完でRate 1511スタートでした。 こちらも青色を目指して頑張っていこうと思います。

Cはpretestは通りましたが、ちゃんと全探索しておらずsystem testで撃沈しました。 Dもぱっと浮かんだ解法を後日実装したところ、撃沈していたので、この2問を重点的に復習していきます。


A. Dawid and Bags of Candies

問題URL

問題

Dawidはキャンディの入った4つの袋を持っている。 i 番目の袋は A[i] 個のキャンディを含んでいる。 Dawidはこれらの袋を二人の友人のいずれかにそれぞれ配る(必ず配らなければならず、自身が保持してはいけない)。

二人の友人に同じ数のアメを配ることは可能か判定せよ。

制約: 1 <= A[i] <= 100

解答

それぞれの袋の配り方を全探索したいと考えた。

袋はどちらか一方に所属することになるので、ビット全探索を書いた。

var A []int

func main() {
    A = ReadIntSlice(4)

    for i := 0; i < (1 << uint(4)); i++ {
        one, two := 0, 0
        for j := 0; j < 4; j++ {
            if NthBit(i, j) == 1 {
                one += A[j]
            } else {
                two += A[j]
            }
        }
        if one == two {
            fmt.Println("YES")
            return
        }
    }
    fmt.Println("NO")
}

B. Ania and Minimizing

問題URL

問題

Aniaは大きな整数 S を持っている。 この S は、10進数表現で n 桁となる(上位桁の桁埋めのための0(leading zeroes)はない)。

Aniaは最大で k 個の桁を変えることができる(ただし、leading zeroesを作ってはいけない)。 Aniaができるだけ小さい数を作ろうとするとき、その値は何になるか答えよ。

制約: 1 <= n <= 200000, 0 <= k <= n

解答

S がとても大きいので文字列のまま処理する方針で考える。

気持ちとしては上位桁を小さくするほうが得なので、上の桁から0にしていきたいが、条件から「最上位桁を0とするのはご法度」となる。

なので、最上位桁は泣く泣く1とし、それ以降を可能なだけ0で置き換えていくことにする。

シミュレーションする際は、変える必要のない桁を変えて k を無駄に減らしてしまったり、ループを抜けるところを間違えて変える桁の過不足が発生しないように注意した。

var n, k int
var S []rune

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

    if k == 0 {
        fmt.Println(string(S))
        return
    }

    if n == 1 {
        S[0] = '0'
        k--
    } else {
        if S[0] != '1' {
            S[0] = '1'
            k--
        }
    }

    if k == 0 {
        fmt.Println(string(S))
        return
    }

    // この時点で k > 0
    for i := 1; i < n; i++ {
        if S[i] != '0' {
            S[i] = '0'
            k--
        }

        if k == 0 {
            break
        }
    }

    fmt.Println(string(S))
}

leading zeroes というのはあまり馴染みがなかったので覚えておきたいところ。

C. Anadi and Domino

問題URL

問題

Anadiはドミノの1セットを持っている。 それぞれのドミノは、両サイドに1から6のサイコロの面が描かれており、それぞれの種類について1ピースあるため、全部で21個のドミノがある。

※URLの画像が親切なので詳しくはそちらをご参照ください。

また、Anadiは自己ループ・多重辺の無い無向グラフを持っており、そのグラフの辺にドミノを置こうとしている。 ドミノを置く際のルールは以下のようになっている。

  • ドミノの両サイドが、辺を結ぶノードを向くようにする。
  • 複数のドミノがあるノードを指すように置かれる場合、そのノードが刺されるドミノの数字は等しくなければならない。

Anadiは最大で何個のドミノを置けるか答えよ。

制約: 1 <= n <= 7, 1 <= m <= n*(n-1)/2 (それぞれノード、辺の数)

解答

よくわからないまま、サンプル4のノード数7の完全グラフのケースについて、色々とお絵かきをしながら考えた。

考えるうちに、ノードが6個以下の場合は、すべての辺に対してなんらかのドミノが置けることがわかった(1からnの番号を素直にノードに振ってやった後、その番号に向くようにドミノを選んで置いていけば良い)。

なので、 n <= 6 のケースでは m をそのまま出力すれば良い。

ノード数が7のときだけは、2つのノードは互いにドミノの数字をかぶらせる必要が出てくる。

ここで、ドミノの数字をかぶらせるノードペアが同じであれば、それぞれのノードに向けるドミノの数字のパターンが変わろうとも、置けるドミノの数は変わらない、事がわかる (使うドミノが数字に合わせて変わるだけで、使いたいドミノがセットの中にない、ということは起こらない。)

なので、ノード数が7の場合は、「ドミノの数をかぶらせるノードのペアの選び方」を全探索する。

ノード間の辺の有無や、ある種類のドミノの使用済みかどうかの判断はそれぞれともに行列を利用して行っている。

var n, m int

var adjMatrix [10][10]int
var dominoMatrix [10][10]int

func main() {
    n, m = ReadInt2()
    for i := 0; i < m; i++ {
        a, b := ReadInt2()
        // 常にaをbより小さくする
        if a > b {
            a, b = b, a
        }
        adjMatrix[a][b] = 1
        adjMatrix[b][a] = 1
    }

    if n <= 6 {
        fmt.Println(m)
    } else {
        fmt.Println(sub())
    }
}

func sub() int {
    res := 0

    // i, jを同じ数字とする
    for i := 1; i <= n; i++ {
        for j := i + 1; j <= n; j++ {
            // ノードにサイコロの目を割り振る
            memo := make(map[int]int)
            dice := 1
            for k := 1; k <= n; k++ {
                if k == j {
                    continue
                }
                memo[k] = dice
                dice++
            }
            memo[j] = memo[i]

            tmp := 0
            initialize()
            for l := 1; l <= n; l++ {
                for m := l + 1; m <= n; m++ {
                    ll, mm := memo[l], memo[m]
                    if ll > mm {
                        ll, mm = mm, ll
                    }
                    if adjMatrix[l][m] == 1 && dominoMatrix[ll][mm] == 1 {
                        tmp++
                        dominoMatrix[ll][mm] = 0
                    }
                }
            }

            ChMax(&res, tmp)
        }
    }

    return res
}

func initialize() {
    for i := 1; i <= 6; i++ {
        dominoMatrix[i][i] = 1
        for j := i + 1; j <= 6; j++ {
            dominoMatrix[i][j] = 1
        }
    }
}

コンテスト中は、「数字をかぶらせる必要のあるノード番号を7とし、 7を割り当てるノードを全部調べる」というようなことを考えていたら、 見るからにバグりそうなコードが出来上がってしまった(実際にsystem testで撃沈した)。

ヤバそうなコードを書いているときは、たいてい予想通りどこかでひっかかるので、 コンテスト中も途中で考えを捨てる勇気を持ちたい。

とはいえ、改めて整理して書いてみても、それなりに複雑なコードになってしまった。

ごちゃごちゃ考えずに、n の値によらずに全探索する方法もあるらしい。 そちらのほうが確実そうな一方で、実装方法がよくわかっていない(のでどなたか教えて下さい)。

全探索による別解(2019-10-06追記)

この記事を読んでくださったくるさんから、 全探索のコードを提供していただいたので、Goで書き直してみました(くるさんありがとうございます。。!呟いてみるもんですね)。

頂点数が7のときが〜とかかぶらせる数字は2個まで〜とか、そんな面倒な採番を考えなくても、 1〜6まで重複順列で全パターン洗い出してしまえばいいじゃないか、という解法です。

6^7*21 = 5878656 なので問題なく間に合いますね。

重複順列はスニペットにしているので、せっかくなので久しぶりにそれを使って書いてみました。 シンプルでバグらせようがなくてベストな解法だと思いました。

var n, m int

var edges []Edge

type Edge struct {
    s, t int
}

func main() {
    n, m = ReadInt2()
    for i := 0; i < m; i++ {
        s, t := ReadInt2()
        s--
        t--
        edges = append(edges, Edge{s, t})
    }

    ans := 0
    patterns := DuplicatePatterns([]int{0, 1, 2, 3, 4, 5}, n)
    for _, p := range patterns {
        A := [6][6]int{}
        for i := 0; i < 6; i++ {
            for j := 0; j < 6; j++ {
                A[i][j] = 1
            }
        }

        cnt := 0
        for _, e := range edges {
            l, r := p[e.s], p[e.t]
            if A[l][r] == 1 {
                A[l][r], A[r][l] = 0, 0
                cnt++
            }
        }
        ChMax(&ans, cnt)
    }

    fmt.Println(ans)
}

// DuplicatePatterns returns all patterns of n^k of elems([]int).
func DuplicatePatterns(elems []int, k int) [][]int {
    return dupliRec([]int{}, elems, k)
}

// DFS function for DuplicatePatterns.
func dupliRec(pattern, elems []int, k int) [][]int {
    if len(pattern) == k {
        return [][]int{pattern}
    }

    res := [][]int{}
    for _, e := range elems {
        newPattern := make([]int, len(pattern))
        copy(newPattern, pattern)
        newPattern = append(newPattern, e)

        res = append(res, dupliRec(newPattern, elems, k)...)
    }

    return res
}

D. Marcin and Training Camp

問題URL

問題

Marcinは大学の講師で、n人の合宿に参加したい生徒を抱えている。 Marcinは、互いにcalmlyに共同作業できる生徒たちを送ろうとしているとしている。

生徒たちは1からn番の番号が振られており、それぞれ A[i], B[i] で特徴づけられている。

  • A[i]: このビット表現は、0から59のアルゴリズムを、i 番目の生徒が知っているかどうかを示している(1ならば知っている)。
  • B[i]: i 番目の生徒のスキルの高さを示している(高ければ高いほどよい)。

生徒たちは、「あるアルゴリズムについて、自分は知っているが相手は知らない」というようなアルゴリズムが1つでもある場合に、相手のことを見下す。 2人以上のグループを組んだとき、相手のことを見下す生徒が一人もいない場合に、そのグループはcalmlyに共同作業できる。

共同作業できるグループを作る際、そのグループを構成する生徒のスキルレベルの和を最大化する場合、スキルレベルの和はいくらになるか答えよ。

解答

グリーディに考える。

グループが作れる条件を、「少なくとも1組のペアが、互いに知っているアルゴリズムの集合が同じで、互いを対等だと思っている」ことだと考える。

そこで、まずは対等な人同士でグループを作ってしまう。 対等な人のグループは、Aでソートすれば見つかる。

また、この対等な人たちでのみ構成されるグループに対して、まだグループが組めていない生徒を組み込んでいくことを考える。 具体的には、グループを表すビット集合と、ある生徒のビット集合のビットOR演算をとり、ビット集合がグループのビット集合のままであれば、 その生徒はグループに組み込むことができる。 逆に、グループのビット集合が変化してしまう場合、その生徒はそのグループの人全員を見下してしまうため、そのグループには組み込めない。

最後に、出来上がった全てのグループを併合しても問題ないため、グループに所属している生徒のスキルレベルの和を計算する。

和を計算するときは、32ビット整数の範囲を超えてしまうことに注意。

ソート部分の計算量が O(n * log(n)) で、対等な人たちのグループに残った人の組み込みを考える部分の計算量が O(n^2) となる。

var n int
var A []int64
var B []int

type Student struct {
    key int64
    a   int64
    b   int
    idx int
}
type StudentList []*Student
type byKey struct {
    StudentList
}

func (l StudentList) Len() int {
    return len(l)
}
func (l StudentList) Swap(i, j int) {
    l[i], l[j] = l[j], l[i]
}

func (l byKey) Less(i, j int) bool {
    return l.StudentList[i].key < l.StudentList[j].key
}

var flags []bool

func main() {
    n = ReadInt()
    A = ReadInt64Slice(n)
    B = ReadIntSlice(n)
    flags = make([]bool, n)

    if n == 1 {
        fmt.Println(0)
        return
    }

    L := make(StudentList, 0, 200000)
    for i := 0; i < n; i++ {
        L = append(L, &Student{key: A[i], a: A[i], b: B[i], idx: i})
    }
    sort.Stable(byKey{L})

    // 2以上のサイズのメモ
    memo := make(map[int64]int)
    for i := 0; i < len(L); i++ {
        if i == 0 {
            if L[i].a == L[i+1].a {
                memo[L[i].a] = 1
            }
        } else if i == len(L)-1 {
            if L[i-1].a == L[i].a {
                memo[L[i].a] = 1
            }
        } else {
            if L[i-1].a == L[i].a || L[i].a == L[i+1].a {
                memo[L[i].a] = 1
            }
        }
    }

    for bits := range memo {
        for i := 0; i < n; i++ {
            if bits|A[i] == bits {
                flags[i] = true
            }
        }
    }

    sum := int64(0)
    for i := 0; i < n; i++ {
        if flags[i] {
            sum += int64(B[i])
        }
    }

    fmt.Println(sum)
}

対等な人たちのグループを併合してから、そのグループのアルゴリズムセットが包含するような生徒を取り込む、というようにすると誤りになる (もとの個々のグループの人全員を見下してしまう生徒を組み込んでしまう場合がある)。

やむを得ず貪欲法を選択することになった場合は、ちゃんと整理しきってから提出したい。

これもどうやら全探索的なやり方があるらしいので、コンテスト中はできる限りそういったものが選択できるようにしたい。


感想

細かい部分でなれない実装が要求される感じがあり、本質的でない部分で消耗してしまった気がします。 最近のABCのE問題以降では、これぐらいの実装が要求されるものも少なくないように感じるため、慣れていきたいところです。

また、無証明の貪欲は危険だということも体験できたので、証明をスムーズにできる訓練もしていきたいと思います。