ABC346｜ardririy

ペナまつりでも、5完は5完なのです。

A - Adjacent Product

言われたものをそのままやればよいです。

出力周りはさくっと書けるようにしている(末尾に無駄な空白があるとcargo-competeの自動テストが通らないのでかんたんにするため)のですが、最初空白なしで出力していてちょっと焦るなどしました。

"wbwbwwbwbwbw"の開始地点を全探索すればよいです。条件を満たさずにw, bのいずれかの個数が与えられたものより大きくなったらその開始地点はだめで、一個でも引っかかったらYes, そうでなければNoです。

体感Bよりかんたん。1からKまでの総和はO(1)でも止められるので、そこから一度でも現れた値を引いていってあげれば良いです。重複とK以上のものは引かないように。

DはDPのD。今までに一度でも連続する部分があったら1, そうでなければ0として

dp[i][j][k] := i番目に状態jであり、kを採用したときの最小コスト

と定義すれば良いです。遷移は、よしなに

上書きする問題は最後から見ていくと良い、典型です。横向きに塗った場合、それ以前に縦向きに塗るときには塗ることができるますが減っていく(縦横逆でも同じ)というイメージ。文字で書くのが難しいので諦めます。