ABC159 E Dividing Chocolate

ABC159 E Dividing Chocolate

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc159/tasks/abc159_e

考察

• どう分ければいいのか分からん
• が小さいので怪しい．．．なんだこれ．．．
• １行だけの場合を考えてみると貪欲っぽく見える
• これを行の場合に拡張すればいいのか．．．．
• が小さいし，横を決め打ちすればあとは同じに見えたので実装してみると通りました笑
• バグを埋め込んだので反省

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

typedef long long int ll;

const int INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

/******************************************************************************************/

char mp[15][1005];


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	int h, w, k;
	cin >> h >> w >> k;

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> mp[i][j];
		}
	}

	int ans = INF;
	for (int mask = 0; mask < (1 << (h - 1)); mask++)
	{
		vector<vector<int> > comp;
		vector<int> hoge(w + 10, 0);
		int cnt = 0;
		bool can = true;

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				hoge[j + 1] += mp[i][j] - '0';
			}

			if ((mask >> i) & 1) {
				//ここで線が入る
				for (int j = 0; j <= w; j++)
				{
					if (hoge[j] > k) {
						can = false;
						break;
					}
				}

				if (!can)break;
				comp.push_back(hoge);
				fill_v(hoge, 0);
				cnt++;
			}
		}

		for (int j = 0; j <= w; j++)
		{
			if (hoge[j] > k) {
				can = false;
				break;
			}
		}
		if (!can)continue;
		
		comp.push_back(hoge);


		//あとは左から貪欲
		for (int j = 0; j < w; j++)
		{
			bool ok = true;
			for (int i = 0; i < comp.size(); i++)
			{
				ok &= (comp[i][j] + comp[i][j + 1] <= k);
			}


			if (ok) {
				for (int i = 0; i < comp.size(); i++)
				{
					comp[i][j + 1] += comp[i][j];
				}
			}
			else
			{
				cnt++;
			}
		}
		ans = min(ans, cnt);
	}


	cout << ans << endl;

	return 0;
}