あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder Mujin Programming Challenge 2017 B - Row to Column (Go)

irisruneです。1300点問題が解けたのは嬉しいです。

問題

atcoder.jp

得点が高いですが、アルゴリズムや実装の難しさよりも数学パズル寄りの問題だとは思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

type row struct {
    num    int
    blacks int
}

type rows []row

func (r rows) Len() int {
    return len(r)
}

func (r rows) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r rows) Less(i, j int) bool {
    return r[i].blacks < r[j].blacks
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    board := make([][]bool, n)
    for i := range board {
        board[i] = make([]bool, n)
        s := nextStr()
        for j, r := range s {
            if r == '#' {
                board[i][j] = true
            }
        }
    }

    var rows rows = make([]row, n)
    for i, line := range board {
        rows[i].num = i
        for _, b := range line {
            if b {
                rows[i].blacks++
            }
        }
    }
    sort.Sort(sort.Reverse(rows))

    if rows[0].blacks == 0 {
        fmt.Println(-1)
        return
    }

    ans := INF
    for _, r := range rows {
        if n-r.blacks > ans {
            break
        }
        count := 1
        for i := range board {
            if board[i][r.num] {
                count -= 1
                break
            }
        }
                count += (n - r.blacks)
        if ans > count {
            ans = count
        }
    }

    for j := 0; j < n; j++ {
        for i := range board {
            if !board[i][j] {
                ans++
                break
            }
        }
    }

    fmt.Println(ans)
}

まずはロボットの操作によってマス目がどのように変化するか考えてみます。すると以下のことがいえます。

  1. すべてのマスが黒の行を記憶することで、任意の列のすべてのマスを黒にすることができる。
  2. 白のマスが1つでも存在する行を記憶したならば、塗り替えた列には白のマスが最低1つは存在する。
  3. 黒のマスが存在しないとき、塗り替えた後も黒のマスは存在しない。

ここから、行うべき操作の手順が以下のように示せます。

  1. 黒のマスが存在しなければ、すべてのマスを黒にすることができないと判定する。
  2. すべてのマスが黒の行が存在するならば、白のマスが1つでも存在する列を塗り替える。
  3. すべてのマスが黒の行が存在しないならば、マスを塗り替えることですべてのマスが黒の行を生成する。
    1. i列目が黒の行を記憶することでi行目のすべてのマスを黒にすることができる。
    2. 黒のマスが1つでも存在する行を記憶してi列目を塗り替えることでi列目が黒の行を生成することができる。

こちらの手順から、出力すべき値が以下のように導き出せます。

  1. 黒のマスが存在しなければ、-1を出力する。
  2. すべてのマスが黒の行が存在するならば、白のマスが1つでも存在する列の数を出力する。
  3. すべてのマスが黒の行が存在しないならば、1\leq i \leq Hにおける以下の最小値を出力する。
    1. i列目が黒の行が存在するならば、i行目の白のマスの数。
    2. i列目が黒の行が存在しないならば、i行目の白のマスの数+1

このようにして導き出した値が(1.の場合を除き)操作回数の最小値となることは以下により示せます。

  1. すべてのマスが黒の列を塗り替える必要はないので、一連の操作で白のマスが1つでも存在する列の数が増えることはない。
  2. すべてのマスが黒の行が存在しないならば、塗り替えた列には白のマスが最低1つは存在するので、白のマスが1つでも存在する列の数が減ることはない。
  3. 1.と2.より、すべてのマスが黒の行を生成する過程と白のマスが1つでも存在する列を塗り替える過程は独立であるとみなすことができる。

雑記

  • この問題のDifficultyが2000強あったので(得点の割に低い気はしますが)、解いた問題では最高Difficultyだと思っていました。
    • 実際は以前記事にしましたAGC035-Cの方がDifficultyが高かったです。こちらもかなりパズル寄りの問題ですね。