ABC200 F 解答
F - Minflip Summation （2556）
問題
問題文
0, 1, ? のみからなる文字列 S があります。この文字列を K 個連結したものを
T とします。
この文字列の ? を全て 0 か 1 に置き換えた文字列は、S の中に含まれる ? の数を q 個とすると、全部で 2^{Kq} 通り考えられますが、その全てについて以下の問題を解いて、その答えの和を ( 10^9+7 )で割った余りを求めてください。
・? を置き換えた後の文字列を T′ とします。T′ に以下の操作を繰り返し行うことで全ての文字を同じにするとき、必要な最小の操作回数は何回ですか
→ 1 ≤ l ≤ r ≤ |T′| となる整数 l, r を選ぶ。そして、T′ の l 文字目から r 文字目(両端含む)までの各文字を、0 であれば 1 に、1 であれば 0 に変更する。
制約
1 ≤ |S| ≤ 10^5
1 ≤ K ≤ 10^9
考察
本問題では「?」とか「繰り返し」が出ていきますが、一旦はそのあたりを無視ししましてシンプルに考えます。特に工夫も何もない、0,1の文字列を問題文の操作にて 0 または 1 に揃えることをやってみます。
001011101
上記の文字列を用います。0か1のどちらでも良いので、まずは全部 0 にしてみます。次のようにするのが最適でしょう（他にもあります）。
001011101
000011101
000000001
000000000
3回かかりましたね。次に全部 1 にしてみます。
001011101
111011101
111111101
111111111
こちらも3回です。ということで、この文字列を統一するために必要な回数は3回となります。
次にどうして3回でできるのか、少し掘り下げてみましょう。ここで重要なのは値が入れ割っている箇所が何個あるかに注目することです。
値が異なるところを1としてみました。また、0に揃える都合上、両端に0を追加しておきました。この赤色で示している 1 が全部 0 になれば文字が統一されたということになりますのでそれを目標にします。
以下この数を「赤い１」として何度か用いります。
1回操作してみましょう。その時の変化を示します。
一番左の 1 を 0 にしました。とすると、赤色の 1 が 2 個なくなりましたね。実はこれ、最適な反転の操作をする場合には、箇所、順番に行っても赤の1を２つ減らすことが可能です。試しにやってみてください。
以上より操作回数は
赤色の 1 の数（値の変化する箇所）/ 2
と求まります。ここで、赤色の１の数は必ず偶数になります。また、今回は0 にする場合でしたが、すべての数字を揃える場合には数列は循環（円順列）になっていると考えればよいです。
これで本問題に用いる前提の説明はおしまいです。ここから本問題に入っていきます。
本問題では先ほどに加えて2つの要素が追加されています。
１）文字「?」が存在する
２）K 回文字が繰り返される
ただし、裏を返せばそれ以外は先の説明のようにやれば答えが求まります。ですので、追加要素を一つづつ見ていきます。
１）文字「?」が存在する
文字「?」がある場合には、その文字が0の場合と1の場合についてどちらも考えなければいけません。ただし、それだけです。やることは赤色の１の数を数えるだけです。
10?10?10?10?
こんな文字列を考えてみましょう。先ほどと同様に円にしてみます（四角形ですが）。
この円で赤い１が何個現れるかを求めてあげます。右上の？とその下の１に注目します。この？は 0 か 1 に変身します。0 に変身した場合、
01
になるため、赤い１が一つ発生します。なのですが、よくよく考えてみると、右上が０となったときに、他の？は 0 か１を好きなように決められます。ほかの？は 3 個ありますので、その総数は、2^3 = 8通りです。ということで、 この場合には赤い１が８個発生するのです。
１に変身した場合は赤い１が発生しません。
また、今回は「?1」でしたが「?0」でも同様です。
次のその下の1, 0を見てみましょう。これは特に考えることなく、赤い１となりますね。先ほど同様に「?」の分だけ数は増えます。今回、自由な「?」は４個ありますので組み合わせは2^4=16個です。
また、今回はありませんが「?」「?」が隣接した場合はどうなるのでしょう。赤い 1 が発生するのは次の通りです。
0 0 : ×
1 0 : 〇
0 1 : 〇
1 1 : ×
ですね。〇の時には先と同様に他の「?」の2乗通りになります。ここで、2つ決まってますので、2^(総数-2)です。ただし、10, 01 の2通りありますので、 2^(総数-2)の2倍です。ということで、2^(総数-1)となり、結局は ? が1つの時と同様の結果となります。
２）K 回文字が繰り返される
繰り返しです。先ほどの文字を
「10?」が 4 回繰り返された
と考えてみましょう。 そして、各文字のセットが何回出現しているか数えます。
このように、各文字列における出現回数が K 倍されていますね。これは、曲線で示した循環する先頭と末尾の部分が同じ回数出現していると考えればしっくりとくるのかもしれません。
ということで、問題を解く際には K 回繰り返さずに1巡したときに出現した赤い1の数を K 倍してあげれば出現の総数がわかります。ただし、１）説明した「？」の個数は K 倍したときの出現数なのでそこには気を付けましょう。
１）２）を踏まえますと本問題は次のような解法で解くことが可能です。
１.まず「？」の出現回数を数える（1巡の数*K）。
２. 2^(出現回数)を求める。
３.１）のルールに従って K = 1とした際の「赤い１」の数を求める。ただしこのとき、「？」の数はもとの K によるものを用いる。
４）最後に2で割る。これを忘れない。
あとはコーナーケースです。本解法では S = ?, K = 1 のときにちょっと困ったことが起きます。実装を見てもらうとわかるのですが、循環させるときに先頭の文字を末尾に追加しています。となると、この場合は
??
という文字列が生成されます。先のルールに則ると 「??」は「10」と「01」 になりうるから、赤い１は2つ生じるため、答えは１となりそうです。が、この２つの？は同じです。同じ文字なのです。ということは「00」か「11」にしかなりえません。ですので答えは 0 です。
このように、K = 1のときにちょこっと面倒なことが生じますので、この時はコーナーケースとして 0 を出力しましょう。１でも０でも ０になるはずです。
説明は以上となります。あとは実装を見てみましょう。
例のごとくmodintライブラリを用いています。これ便利ですね。
実装
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const int mod = 1e9 + 7;
class mint
{
public:
long long x;
mint(long long x = 0) :x((x% mod + mod) % mod) {}
mint operator -() const { return mint(-x); }
mint& operator +=(const mint a)
{
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator -=(const mint a)
{
if ((x += -a.x + mod) >= mod) x -= mod;
return *this;
}
mint& operator *=(const mint a)
{
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a)
{
mint res(*this);
return res += a;
}
mint operator-(const mint a)
{
mint res(*this);
return res -= a;
}
mint operator*(const mint a)
{
mint res(*this);
return res *= a;
}
mint pow(long long t) const
{
if (!t) return 1;
mint a = pow(t >> 1);
a *= a;
if (t & 1) a *= *this;
return a;
}
//for only prime number
//Fermat's little theorem
mint inv() const
{
return pow(mod - 2);
}
mint& operator/=(const mint a)
{
return (*this) *= a.inv();
}
mint operator/(const mint a)
{
mint res(*this);
return res /= a;
}
};
int main()
{
string s;
int k;
cin >> s >> k;
int n = s.size();
//コーナーケース
if (n == 1 && k == 1)
{
cout << 0 << endl;
return 0;
}
//?の数を数える
ll question = 0;
for (auto c : s)
{
if (c == '?') ++question;
}
question *= k;
//?乗したものが組み合わせ数
mint comb = mint(2).pow(question);
//循環を表現するために先頭を末尾に追加する
s += s[0];
mint ans = 0;
rep(i, n)
{
int c1 = s[i];
int c2 = s[i + 1];
//?があったら、?は1個へるので1/2する
if (c1 == '?' || c2 == '?')
{
ans += comb / 2;
}
//10, 01のときには組み合わせ数
else
{
if (c1 != c2) ans += comb;
}
}
//k倍して/2するのを忘れない
ans *= k;
ans /= 2;
cout << ans.x << endl;
return 0;
}あとがき
pythonなどオーバーフローしない言語であればmodintを使わなくとも、その都度modで割ってあげればよさそう、と思いましたが、最後に2で割るのでそこだけ注意が必要ですね。modの世界では割り算に注意です。
本問題の解法を思いつくのはかなり大変だとは思いますが、解説を聞いてみると、やることはシンプルで難しいアルゴリズムも必要とされない問題だと思いました。せいぜい、繰り返し2乗法ぐらいでしょうか。といいましても、最近は典型90問でも出てきましたし、私は結構慣れてきました。これまたpythonなのですが、pythonでは組み込まれているpow関数が繰り返し2乗法なので、そちらを使うと楽かもしれません。問題を解いて、余裕がありましたらそちらの内容も調べてみると面白いと思います。でもまずは、本問題が解ければよいとは思います。ライブラリは利用するものです。理解は余裕ができたときで良いでしょう。
この解説はyoutubeに上がっている公式の解説にだいぶ則っていますので、なにか不明点などありましたら、そちらを合わせてご覧いただけるとさらに理解が深まると思います。それでも不明点があればおっしゃってください。一緒に考えましょう。
これで京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）の解説はおしまいです。ここまで読んでいただいたそこのあなた、ありがとうございます。お役に立てたでしょうか？
繰り返しになりますが記事に関して、不明点、誤り等ありましたら、お知らせいただけると幸いです。
本日もABCがありますので近いうちにまたお会いしましょう。
この記事が気に入ったらサポートをしてみませんか？