C問題を解いても時間が余っていてD問題もやれそうだったのでいつもとは違いD問題もやります。
C問題
forループでiごとにそれまでのM日間に食べたカロリーを集計するのは遅いので別の方法を考える。
解説
0から順にi番目のAを処理していく。K以下のカロリーなら摂取、変数に足す。
摂取してからM日経ったカロリーは除外する。ぶっちゃけA[i-M]がそれ。
これでループの都度集計することなく各i日目のM日間の摂取カロリーが求まる。
食べたかどうかのフラグ変数があるとやりやすい。
あとは問題文の通りに実装するだけ。
動きのイメージとしては底引き網漁。
海がA、船がiで、底引き網がi-M。i番目の要素を足しながらi-M番目の要素を引けばA[i-M]からA[i]までの和が求まる。この問題の場合、i番目の要素を足す時に条件があるため、i-M番目の要素を引く時にも同じ条件を付ける。
D問題
解説
ほとんど公式解説の通りだが一応。
各行各列で#のないインデックスiとjを行と列のリストそれぞれに格納する。そのiとjのそれぞれの組み合わせが安全な空マスとなる。制約では50万マスまでなので、この段階では順に舐めていけば問題ない。
安全な空マスが列挙できるので、あとはそこにK回以内に到達可能なマスを数え上げる。全てのマスについて順に考えるよりも、安全な空マスからK回以内へのグリッドの移動として探索するほうが考慮すべきことが少なく済む。
であればBFSで良さそうに見える……しかし、安全な空マスが複数あるのが厄介。処理順によっては探索済みフラグが本来到達可能なはずのマスへの移動を阻害してしまう。
というわけで多始点で始めればよい。
多始点BFSは公式解説でも記述の通り、通常のBFSとほとんど一緒。ただし実装上の注意点が一つ。
探索済みフラグは単一始点のBFSであればループ処理の内のいずれかにあれば充分であったが、それを流用した多始点BFSの場合は実装によっては頂点への探索が重複してしまうことがあるため、頂点をEnqueueした時点で探索済みフラグを立てる処理必要がある。（１敗）
これは始点をEnqueueする場合も同様に必要。（１敗）
感想
3完2ペナ。久しぶりだからかいつも以上に細かいミスの多い提出になった。
C問題、解法は合っていたがInt64を使っていなかったのと、単純な比較ミス（問題文の通り<=とすべきところを<にしていた）をやらかし、REとWAで2ペナ。
D問題では時間内に間に合わなかったし、解法の考慮不足が目立つ。ij変数ミスもやらかした。BFSを全ての始点から同時に始めてしまえばいいということに気付かずWA。その後も入力例3で想定される出力がどうしても得られず、上記の計２敗が出来上がった。
コメント