AtCoder ABC469-Cの考え方と実装ミスを解説｜二分探索ではなく区間管理で解く方法

AtCoderの問題では、実装方法だけでなく「何を数えて、どの状態を管理するか」という考え方が重要になります。特にABC469-Cのような区間や条件管理が必要な問題では、変数の意味を正しく設計しないと一見動きそうなコードでも誤答になってしまいます。

この記事では、ABC469-Cを題材に、提示されたC++コードの問題点や、なぜ期待した結果にならないのか、正しい考え方と実装方針について解説します。

まずコードの目的を整理する

提示されたコードでは、文字列sの中に存在する「o」と「x」を利用して、ある位置から条件を満たす範囲を探そうとしています。

そのために、最初のループで「o」の累積数をvector haveに保存し、次のループでreachを伸ばしながら「x」の数を減らす処理をしています。

しかし、この方法では各位置ごとの必要な情報管理が正しくできていません。特にhave[i]は「i番目までに存在するoの数」であり、i番目以降の区間で必要な情報とは一致しません。

コードでは以下の部分で累積値を作っています。

if(s[i]=='o')count++; have[i]=count;

このhave[i]には、0番目からi番目までにあるoの個数が入ります。

例えば文字列が「oxoox」の場合、haveは「1,1,2,3,3」のようになります。

しかし後半の処理では、have[i]を「iより右側にあるoの数」のように扱っています。ここが大きな問題です。

累積値は過去の情報を表すものであり、未来の範囲を調べるためには別の管理方法が必要になります。

次の部分にも問題があります。

reach=max(reach,i+1);

reachは前回の探索位置を保持していますが、その後のwhile文で全体の状態を変更しています。

そのため、各iについて独立した答えを求める処理になっておらず、前のループの結果が次のループに影響します。

このような場合、現在見ている位置と探索済みの範囲を明確に分けて管理する必要があります。

この種類の問題では、単純にoの数とxの数を比較するだけではなく、「どの位置からどこまでが条件を満たすか」を考える必要があります。

例えば、ある位置から右方向へ探索する場合、必要なのはその区間内に存在する文字数や条件を満たす位置です。

そのため、累積配列を使う場合でも、左からの累積と右からの累積を区別して設計する必要があります。

このような問題では、まず問題文から「各位置で何を求める必要があるか」を整理します。

例えば、区間内の個数を高速に求めたい場合は累積和を使います。ある範囲のoの数を求めたいなら、

sum[r]-sum[l]

のように区間計算できる形にしておくと、毎回ループで数え直す必要がありません。

また、条件を満たす範囲を伸ばしていく問題では、two pointer（しゃくとり法）を使うことが多いです。

しゃくとり法では左端と右端を管理しながら、現在の区間が条件を満たしているかだけを確認します。

今回のコードのように、「途中で作った配列の意味が変わってしまう」というミスは競技プログラミングで非常によくあります。

例えば累積和を作った場合、その配列は「どの範囲の情報を持っているのか」を常に意識する必要があります。

haveという名前だけを見ると「持っている数」という意味ですが、実際には「左側にあるoの累積数」です。このような名前と役割のズレもバグの原因になります。

修正する場合は、いきなりコードを書き換えるのではなく、以下を確認すると原因を特定しやすくなります。

特にAtCoderでは、コード量を減らすことよりも、変数の意味を正しく保つことが重要です。

提示されたコードの主な問題は、have配列に保存している情報と、後半の処理で必要としている情報が一致していない点です。

累積値は便利な手法ですが、「何を累積しているのか」を明確にしなければ正しい答えにはつながりません。

ABC469-Cのような問題では、まず区間で管理すべき情報を整理し、その上で累積和やしゃくとり法など適切なアルゴリズムを選択することが、安定して解くためのポイントになります。