AtCoder が提供しているABC（AtCoder Beginner Contest）332 のC問題をC++とPythonで解いてみました。ABC332は、2023年12月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 T-shirts（Difficulty : 161）
問題はリンク先をご覧ください。
制約は大きくはありませんが、解の二分探索で解きました。AtCoder Problems による Difficulty は 161 でした。
解答案
$1 \leqq M \leqq N \leqq 1000$ とあまり制約は大きくありません。連続する文字をカウントするような解法があるかもしれません。
一方、この問題は解には単調性があります。単調性というのは、ある値以上はすべて条件を満たす（シャツが足りる）が、ある値未満の場合には条件を満たさない（シャツが足りなくなる）、という性質です。
この問題は、解の単調性があり最小値を求めるため、「解の二分探索」が使えます。このブログでも何回も紹介しています。以下の2つを実装します。
- 関数 is_ok：条件を満たすか、満たさないか判断する
- 絶対に条件をみたす変数 ok と、条件を満たさない変数 ng を設定して、解の二分探索をする。このコードは、パターン化できている。
C++ プログラム例（ABC332C）
上記の方針で実装します。
- 関数 is_ok
- m 枚の無地のシャツと、mid 枚のロゴ入りシャツが条件を満たすか確認します。足りるか足りないかは文字列を走査して判断します。
- 食事に行く場合は、無地のシャツを先に着ることにします。
- ng = -1、ok = 1000 を設定します（45、46行目）。
- 残りは定番コードです。これはほとんどの問題で使いまわせます（47ー54行目）。
以下が、C＋＋プログラムとなります。解の二分探索の定番コードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
bool is_OK(int mid)
{
bool result = true;
int t_none = m;
int t_logo = mid;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
t_none = m;
t_logo = mid;
} else if (s[i] == '1') {
if (t_none == 0) {
if (t_logo == 0) {
result = false;
break;
} else {
--t_logo;
}
} else {
--t_none;
}
} else if (s[i] == '2') {
if (t_logo == 0){
result = false;
break;
} else {
--t_logo;
}
}
}
return result;
}
int main()
{
cin >> n >> m;
cin >> s;
int ng = -1;
int ok = 1000;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC332C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 332 C"""
def is_ok(mid):
global n, m, s
result = True
t_none = m
t_logo = mid
for i in range(n):
if s[i] == '0':
t_none = m
t_logo = mid
elif s[i] == '1':
if t_none == 0:
if t_logo == 0:
result = False
break
else:
t_logo -= 1
else:
t_none -= 1
elif s[i] == '2':
if t_logo == 0:
result = False
break
else:
t_logo -= 1
return result
n, m = map(int, input().split())
s = input()
ng = -1
ok = 1000
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
print(ok)こちらも「AC」と判定されました。
最後に
この問題（Difficulty 161）に解の二分探索を使うのことは、大げさと感じる人がいるかもしれません。解けるのであれば、多少難易度が合わなくても手の内にできている手法を使うという方針で解いています。
引き続き ABC の問題を紹介していきます。
