AtCoderRegularContest134 A問題300点「Bridge and Sheets」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^5
$ W \leq L \leq 10^{18}
解法・お気持ち
https://gyazo.com/7fda87c91a4ab6cf8c63879a7d02db67
上記のような $ W幅のシートがすでに$ N枚敷かれています。
よって、まだ埋められていない橋の箇所は最大$ N + 1箇所です。
よって、この $ N + 1箇所に実際にシートを貪欲に割り当てていけばいいです。
計算量
$ O(N)
新たな学び
反省点
極力きれいな実装ができるように心がける
コード
code: go
func solve() {
var N int
var L, W int64
fmt.Scan(&N, &L, &W)
a := make([]int64, N+1)
for i := 0; i < N; i++ {
}
p, ans := int64(0), int64(0)
for i := 0; i <= N; i++ {
ans += (ai - p + (W - 1)) / W }
}
fmt.Println(ans)
}
// ------------------------------------------------------------
// ------------------------------------------------------------
func main() {
solve()
defer io.Flush()
}