AtCoder ABC62-C Chocolate Bar

C - Chocolate Bar

良い子のみんなは微分しちゃダメだぞ！！

実験的に思考過程を思い出しながら書いてみます。

理由は２つあります。

１つ目は解法と直接関係のない自分の思考を言語化することで、考察の無駄を省き、自分の思考の癖を発見し、考察力アップを図ることです。

２つ目は、マラソンで思考ログを公開してくれる方はよくいらっしゃるのですが、アルゴだとあまりいません。アルゴでやって見ても面白いかなと思ったからです。

問題の解説を求めてる方は、解法まとめへどうぞ。

問題概要

縦H、横Wをブロックに沿って３つの長方形に分ける。一番面積の大きい長方形と一番面積小さい長方形の面積の差の最小値を求めなさい。

$2≦H,W≦10^5$

思考過程

一番大きい面積の長方形の面積を $S_{max}$ 一番小さい面積の長方形の面積を $S_{min}$ とします。

制約を見ます。 $O(HW)$ はダメなようです。

HかWが３の倍数なら均等に３等分出来るから答えは０。よって、どちらかが３の倍数の時は考える必要はありません。以下、HもWも３の倍数ではないとして扱います。これを一般化して、H、Wについてそれぞれmod3をとって場合分けしたらうまくいくんじゃないか、とか考えたけどうまくいきません。

切り方について考えます。

同じ方向に２回切る場合（縦縦、横横）と違う方向に１回ずつ切る場合（縦横、横縦）で計算方法が異なりそうなので分けて考えます。

同じ方向に切る場合。

縦に２回になるべく同じ大きさに切る場合、実験するとわかるのですが、同じ大きさの長方形２つと、それより幅が１だけ違う長方形ができます。（例えば、 $(H,W)=(5,7)$ の時、 $(5,2)(5,2)(5,3)$ の切り方が最善で、最大と最小の差は $5$ になります。）このように、縦縦と切る場合 $S{max}$ と $S{min}$ は幅が１ブロック異なるだけなので、その差は $H$ となります。横に２回なるべく同じ大きさに切る場合も同様の議論で $S{max}$ と $S{min}$ の差は $W$ となります。

よって、同じ方向に切る場合

$S{max}-S{min}=min(H,W)$

の時、左辺は最小となります。

違う方向に切る場合。

縦、横という順序で切る場合を考えます。順番を入れ替えても同様な議論ができます。お絵描きします。

f:id:guitarjoepass:20180627150627p:plain

（チョコレートなので黒にしたのですが絶対見にくい）

左からaブロックのところを縦に切り、上からbブロックのところ横に切ります。そしてそれぞれの長方形を $X,Y,Z$ とします。aとbを全探索すれば答えがでると一瞬考えましたが、 $O[HW$ ]なのでダメです。aとbの範囲を絞る必要があります。ここでアホな僕はX-Y,Y-Zなどなどをa,bで偏微分すればなんかわかるんじゃね、とか考えました。場合分けと偏微分の手計算の沼に１時間半落ちました。流石にこれは変だと気づきます。

そもそも何がしたかったのかを考えます。 $S_{max}-S_{min}$ の最小化です。これが達成できた時はどんな時なのかを考えます。チョコレートを３等分に近くなるように分けた時です。なんで、厳密に３等分にできないのか考えます。ブロックがあるからです。ブロックを無視して見ましょう。

f:id:guitarjoepass:20180627152004p:plain

$(W,H)=(10,7)$ の時の図です。

この時厳密に３等分出来るので、 $S_{max}-S_{min}=0$ となります。実際にはブロックがあるのでこのような分け方はできませんが、３等分に最も近い分け方のできるa,bはこの前後にありそうです。つまり、 $a=(3,4) b=(3,4)$ がa,bの候補であり、これら４パターンを全て試したどれかに $S_{max}-S_{min}$ の最小値がありそうです。一般化すると、

$a=W/3,W/3+1,b=H/2,H/2+1$

$X=aH,Y=b(W-a),Z=(W-a)(H-b)$

となります。

解法まとめ

同じ方向に２回切る場合と、違う方向１回ずつ切る場合で場合分けを行います。

①同じ方向に２回切る場合

HもしくはWが3で割り切れるならば、等しく３等分出来るので答えは０です。

そうでないならば、同じ面積の長方形２つと、それと幅が１ブロック分異なる長方形が出来るので、切った方向と平行の長さが答えになります。（縦向きに切ると縦の長さが答え）

$(H*W) mod 3 = 0 ならば ans=0$

$(H*W) mod 3 ≠ 0 ならば ans=min(H,W)$

②違う方向で１回ずつ切る場合

f:id:guitarjoepass:20180627150627p:plain

XとYとZをできる限り等しくしたいです。つまり、X,Y,ZをそれぞれW*H/3に近づけるイメージです。そう考えると、 $a=(W/3,W/3+1) , b=(H/2,H/2+1)$ がそれぞれa,bの候補であることがわかります。

解答例

gist.github.com

反省

・400点初ACなので嬉しい。

・図形を分割する問題。切り方の順序によって場合分けする解法。

・達成目標はなにで、それはどんな時達成されますか？という考え方。

・微分しに行ったのは頭悪かった。そもそも、何がしたいのか意識するの大事。

・ブロックを無視して考察するの良かった。問題文から条件を１個取り除いて考察するのは考察の典型な気がする。

・思いっきり迷走したけど、解説見なかった自分えらい。

・思考ログを書き起こすタイプのアルゴの競プロブログってあまりない気がするのですがどうですか...?

2018/06/27 コードと本文中の説明で食い違いがあったので、コードの修正を行いました。

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;
}

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;
}

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;
}

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;
}

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;
}

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;
}

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

int main(){
  long long int h,w,a,b;
  long long int ans,M,m,X,Y,Z;
  cin>>h>>w;
  if(h*w%3==0){
    cout<<0<<endl;
    return 0;
  }
	
  ans=min(h,w);
  for(int k=0;k<2;++k){
    for(int i=0;i<=1;++i){
      for(int j=0;j<=1;++j){
        a=w/3+i;b=h/2+j;
        X=a*h;
        Y=b*(w-a);
        Z=(w-a)*(h-b);
        M=max(X,Y);
        M=max(M,Z);
        m=min(X,Y);
        m=min(m,Z);
        ans=min(ans,M-m);	
      }
    }
    swap(h,w);
  }
  cout<<ans<<endl;

imiko’s blog

AtCoder ABC62-C Chocolate Bar

C - Chocolate Bar

目次

問題概要

思考過程

解法まとめ

解答例

反省