B - fLIP O(N)解法

Quiz

https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_b

解説

  • editorialにO(N)でも可能と書いてあったのでやってみた
  • 行への操作を全探索する
  • 縦への操作をa回行って、Kが実現できるかを考える
  • 下記画像の最後の式を変形してa=の形に変形し、aが範囲に収まっていれば答え

f:id:peroon:20200616031700p:plain

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M,K;cin>>N>>M>>K;
    if(N>M) swap(N,M);

    if(K==0) yes();

    rep(i,N+1){
      if(N-2*i==0){
        ll blk = M*i;
        if(blk==K) yes();
        continue;
      }
      
      if((K-M*i)%(N-2*i)==0){
        ll a = (K-M*i)/(N-2*i);
        if(0<=a && a<=M) yes();
      }
    }
    no();

    return 0;
}