AtCoder ARC 074 / ABC 062 C - Chocolate Bar (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。最近台風の接近が多く関東の天気は荒れがちですね。

問題

本当に全探索すると間に合わないので少しだけ工夫する問題です。

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
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    h, w := nextInt(), nextInt()
    ans := h * (((w + 2) / 3) - (w / 3))
    if (((h+2)/3)-(h/3))*w < ans {
        ans = (((h + 2) / 3) - (h / 3)) * w
    }
    for hi := 0; hi <= h; hi++ {
        blocks := []int{hi * ((w + 1) / 2), hi * (w / 2), (h - hi) * w}
        sort.Sort(sort.IntSlice(blocks))
        if blocks[2]-blocks[0] < ans {
            ans = blocks[2] - blocks[0]
        }
    }
    for wi := 0; wi <= w; wi++ {
        blocks := []int{((h + 1) / 2) * wi, (h / 2) * wi, h * (w - wi)}
        sort.Sort(sort.IntSlice(blocks))
        if blocks[2]-blocks[0] < ans {
            ans = blocks[2] - blocks[0]
        }
    }
    fmt.Println(ans)
}

板チョコを3分割する方法としては次の2つが考えられます。

縦あるいは横に平行に3分割する。
縦あるいは横に2分割し、片方を垂直に（横あるいは縦に）2分割する。

縦に分割する場合を求めれば横に分割する場合も同様に求められるので、縦に分割する場合を考えます。まずは1.について、横の長さによって以下のように場合分けができます。

横の長さが3の倍数であれば、分割した板チョコはすべて同じ大きさ（面積の最大値と最小値との差は0）。
横の長さが3の倍数でなければ、分割した板チョコの面積の最大値と最小値との差は縦の長さに等しい。
1. 分割した板チョコの縦の長さはそれぞれ等しく、横の長さの差は1であるため。

よって計算量 $O(1)$ で求めることができます。

次に2.について、こちらは縦に2分割する位置 $O(W)$ 通りについて考えます。すると分割された片方のチョコを横に分割する方法としてはなるべく均等になるように分割すればよいので、面積の最大値と最小値との差は計算量 $O(1)$ で求めることができます。そのため、全体の計算量としては $O(W)$ となります。