【C#】ABC472 CD問題備忘録

2026.08.24

C問題を解いても時間が余っていてD問題もやれそうだったのでいつもとは違いD問題もやります。

C問題　On a Diet

直近M日間で食べたカロリーを監視しつつ、i日目のカロリーを摂取するか（当日を含めてM日間で食べるカロリーがK以下になるか）をその都度判断して出力する。

C問題へのリンク

解説

forループでiそれぞれについてM日間に食べるカロリーを集計する素朴な方法は遅い（O(n2)）ので別の方法を考える。それぞれについて食べたか食べてないかをどこかしらにメモするなどの方法で計算を少なく済ませられそう。

0から順にi番目のAを処理していく。K以下のカロリーなら摂取、変数に足す。

摂取してからM日経ったカロリーは除外する。ぶっちゃけA[i-M]がそれ。例えばMが3なら、当日含めたM日間のカロリーは「当日」「1日前」「2日前」の計3日間。このことからもMつまり3日前は除外してよい。

これでループの都度集計することなく各i日目のM日間の摂取カロリーが求まる。

食べたかどうかのフラグ変数があるとやりやすい。

あとは問題文の通りに実装するだけ。

動きのイメージとしては底引き網漁。
海がA、船がiで、底引き網がi-M。i番目の要素を足しながらi-M番目の要素を引けばA[i-M]からA[i]までの和が求まる。この問題の場合、i番目の要素を足す時に条件があるため、i-M番目の要素を引く時にも同じ条件を付ける。

この方法はスライディングウィンドウとも言うらしい。一部では尺取り法などと言われたりするが、個人的にはちょっと違うと思います。

疑似コード

疑似コード（折り畳み） 
// 標準入力は省略
M日間のカロリーの摂取量を表す変数msumを宣言;
i日目のおやつを食べたかのフラグ変数を宣言;
for (0からN-1までのi)
{
    変数ansを宣言し文字列"no"で初期化;
    if(M日以上経った && M日前のおやつを食べた) msumからM日前のおやつの分を引く;
    if(i日目を含むM日間のカロリー <= K)
    {
        msumにi日目のカロリーを足す;
        食べたフラグを立てる;
        ansに"yes"を代入;
    }
    ansを出力;
}

ACコード

ACコードへのリンク

D問題　Bomber Mad

H行W列のグリッド上に「.」空マスと「#」爆弾マスのどちらかがある。

同じ行、同じ列に爆弾マスが無ければそこが安全な空マスとなる。

グリッド内では上下左右に移動できる。

K回以内での移動で安全な空マスへ移動できるマスがいくつあるか？　を数え上げる問題。

D問題へのリンク

解説

ほとんど公式解説の通りだが一応。

各行各列で#のないインデックスiとjを行と列のリストそれぞれに格納する。そのiとjのそれぞれの組み合わせが安全な空マスとなる。制約では50万マスまでなので、この段階では順に舐めていけば問題ない。

爆弾のないマス(i,j)を得るには、爆弾のあるiとjのインデックスを行と列で分けて集めた数列を、行は0からhまでの整数列に、列は0からwまでの整数列に対して差集合を取ればよい。残ったiとjの組み合わせが安全な空マスであり、i*jが安全な空マスの総数となります。

これによって安全な空マスが列挙できるので、あとはそこへK回以内に到達可能なマスを数え上げます。とはいえ全てのマスについてそれぞれ考えるよりも、安全な空マスからK回以内のグリッドの移動の最大範囲として解釈して探索するほうが考慮すべきことも計算量も少なく済みます。

であればBFSで良さそうに見えます……が、安全な空マスが複数あるのが厄介です。処理順によっては探索済みフラグが本来到達可能なはずのマスへの移動を阻害してしまいます。

というわけでBFSはBFSでも多始点BFSで始めればよいです。

多始点BFSは公式解説でも記述の通り、通常のBFSとほとんど一緒。ただし実装上の注意点が一つ。

探索済みフラグを立てる処理は単一始点のBFSであればwhile文中のいずれかにあれば十分でしたが、それを流用した多始点BFSの場合は実装によっては頂点への探索が重複してしまうことがあるため、頂点をEnqueueした時点で探索済みフラグを立てる処理である必要があります。（１敗）

これは始点をEnqueueする場合も同様に必要です。（１敗）

図のような状況を避けるために、キューに追加した時点で到達済みフラグを立てる必要があります。

疑似コード

疑似コード（折り畳み） 
// 標準入力は省略
爆弾のある行hbと列wbの重複無し配列を宣言;
二重for文で爆弾のある行hbと列wbに充填;
行を表すインデックスの0からhまでの整数列に対して爆弾のある行の差集合hsafeを取る;
列を表すインデックスの0からwまでの整数列に対して爆弾のある列の差集合wsafeを取る;
// C#はEnumerable.Rangeが使えますしLinqのExceptメソッドも使えちゃいます。楽ですね！
ノードへの到達を表す変数を宣言;
グリッド上の地点を引数にもつ待ち行列のキューを宣言;
変数ansを宣言;
foreach (i in hsafe)
{
    foreach (j in wsafe)
    {
        キューに全てのi,j,Kの組み合わせを入れる;
        地点i,jを到達済みとしてマークする;
while()
{
    キューからi,j,Kの組み合わせを取り出す;
    ans++;
    if (K回あった移動回数が尽きている) continue;
    // キューから取り出した上下左右それぞれについて
    if (グリッド外でないか && 到達済みでないか && 空きマスか)
    {
        Kの移動回数を1減らしてキューに格納する;
        到達済みとしてマークする;  // この処理はここに置くのがおすすめ
    }
}
ansを出力する;

ACコード

ACコードへのリンク

感想

3完2ペナ。久しぶりだからかいつも以上に細かいミスの多い提出になった。

C問題、解法は合っていたがlong型（Int64）を使っていなかったのと、単純な比較ミス（問題文の通り<=とすべきところを<にしていた）をやらかし、REとWAで2ペナ。

D問題では時間内に間に合わなかったし、解法の考慮不足が目立つ。ij変数ミスもやらかした。BFSを全ての始点から同時に始めてしまえばいいということに気付かずWA。その後も入力例3で想定される出力がどうしても得られず、上記の計２敗が出来上がった。

コメント

タイトルとURLをコピーしました