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

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

AtCoder AGC 038 A - 01 Matrix (Go)

irisruneです。やはりAGCはB問題が安定しないと手が出し辛いです。

問題

atcoder.jp

いつものAGC-Aらしく数学パズル的な問題です。嘘解法ではないはずですが実行時間1978msでした。

package main

import (
    "bufio"
    "fmt"
    "os"
    "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, a, b := nextInt(), nextInt(), nextInt(), nextInt()

    for hi := 0; hi < b; hi++ {
        for wi := 0; wi < a; wi++ {
            fmt.Print("1")
        }
        for wi := a; wi < w; wi++ {
            fmt.Print("0")
        }
        fmt.Println("")
    }
    for hi := b; hi < h; hi++ {
        for wi := 0; wi < a; wi++ {
            fmt.Print("0")
        }
        for wi := a; wi < w; wi++ {
            fmt.Print("1")
        }
        fmt.Println("")
    }
}

入力例1に対しての出力例1がミスリードになっています。A,Bは各行、各列について0,1の少ない方の数となるので、B=1のときには1列目に1を2個(0を1個)配置することができます。同様にA=1のときには3行目に1を2個(0を1個)配置することができるので、以下のような出力が可能です。

100
100
011

この考え方は制約を満たす任意のH,W,A,Bに対して拡張可能なので、どのような入力に対しても条件を満たす行列を出力することができます。

なお、上記のコードの計算量はO(HW)です。その割に実行時間がかなりギリギリだったのはどうしてでしょう…?Print関数を何回も呼び出しているのがよくない可能性はありそうです。

雑記

  • 使う文字列は高々2通りしかないので、文字列を作成してからループで出力するアルゴリズムを組んだ方が圧倒的に速いです。
    • 計算量はO(H+W)で済みますし、計算時間も5msしかかかりませんでした。