[JOI精進録] 難易度7「国土分割」(JOI2021/2022 二次予選C)

問題リンク

atcoder.jp

問題概要

行列のGridがある。
このGridを縦もしくは横に線を一本以上引いて分割することを考える。
Gridには値が設定されている。分割された領域の値の総和が全て同じになる分割の方法はどれだけありますか？

解説

AC解法 (100/100点)

Gridを一本もしくは縦横一本づつで2本引いてしまえば後は不可能であるか、1パターン条件を満たす分割方法が存在するかになります。 ということで探索はでできることが分かります。 後の線を引いて条件を満たして分割できるのか、実際に線を引いて判定部分に二次元累積和を使えばで判定できます。
ということで全体計算量で求められそうです。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int h,w,r(0); cin >> h >> w;
  vector A(h, vector<int>(w)),dp(h+1,vector<int>(w+1));
  for (int i(0);i < h;++i) for (int k(0);k < w;++k){
    cin >> A[i][k];
    dp[i+1][k+1]=dp[i+1][k]+dp[i][k+1]-dp[i][k]+A[i][k];
  }
  for (int i(0);i < h;++i) for (int k(0);k < w;++k){
    if (i==h-1&&k==w-1) continue;
    int base = dp[i+1][k+1];
    vector<int> K(1,k+1);
    if (k!=w-1){
      for (int j(k+2);j < w;++j) if (dp[i+1][j]-dp[i+1][K.back()]==base) K.emplace_back(j);
      if (dp[i+1][w]-dp[i+1][K.back()]!=base) continue;
      K.emplace_back(w);
    }
    vector<int> I(1,i+1);
    if (i!=h-1){
      for (int j(i+2);j < h;++j) if (dp[j][k+1]-dp[I.back()][k+1]==base) I.emplace_back(j);
      if (dp[h][k+1]-dp[I.back()][k+1]!=base) continue;
      I.emplace_back(h);
    }
    bool f = 1;
    for (int j(1);j < I.size();++j){
      for (int l(1);l < K.size();++l){
        if (dp[I[j]][K[l]]-dp[I[j-1]][K[l]]-dp[I[j]][K[l-1]]+dp[I[j-1]][K[l-1]]!=base){ f = 0; break; }
      }
      if (f==false) break;
    }
    if (f)++r;
  }
  cout << r << endl;
}

提出結果

atcoder.jp 今年に2021/2022二次予選出たらボーダー300点超えそうです。400点超えるかもしれない。今年の二次予選ちょっと予想できなすぎる...