ABC-62 C Chocolate Bar を解いてみた

ABC-62 C は400点だったこともあり、理解まで時間を少し要しましたが、なんとか自力ACできました。 今回の問題の概要は配列を連想させるような問題ですが、本質は数学的な考えができるかの問題でした。

では、以下問題

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 400点

問題

縦 Hブロック、横 W ブロックの板チョコがあります。 すぬけ君は、この板チョコをちょうど 3 つのピースに分割しようとしています。 ただし、各ピースはブロックの境目に沿った長方形でなければなりません。すぬけ君は、3 つのピースの面積 (ブロック数) をできるだけ均等にしようとしています。 具体的には、3 つのピースの面積の最大値を Smax、最小値を Smin としたとき、Smax−Smin を最小化しようとしています。 Smax−Smin の最小値を求めてください。

制約

2≤H,W≤105

とまあこんな感じ

自分の考えてたこと

線の引き方を考えました。1つのものを他の線とクロスしないような引き方でいくと2本の線を引くことで三分割が実現します。 ここで3分割の方法でつまづいてなかなかACできませんでした。。

分割の方法

一つの面を3分割にするので分割の手順は4通りあります。

* 横×横
* 縦×縦
* 縦×横
* 横×縦

ですね ですが、この分割の見方を変えると2通りの分割を考えておけばいいという考えに辿りつきます。 縦からするか横からするかの問題で、縦と横をスワップして同じ操作を行えば解決します。

フローは以下のようになります。

  • 入力の受け取り
  • もし 縦が3で割り切れる または 横が3で割り切れる
    • 答えを0とする
  • それ以外の場合
    • 答えを縦の長さと横の長さの短い方にする
  • 縦の長さに対して線形的にアクセスする
    • その時点での面積をSaとし変数に格納する
    • 横の長さを二等分する (w1 = W / 2 , w2 = W - w1)
    • 求めた横の長さで面積Sb,Scを求める
    • 面積の最小最大を求める
    • 差が最小な値を答えとする
  • 縦と横をスワップする
  • 縦の長さに対して線形的にアクセスする
    • その時点での面積をSaとし変数に格納する
    • 横の長さを二等分する (w1 = W / 2 , w2 = W - w1)
    • 求めた横の長さで面積Sb,Scを求める
    • 面積の最小最大を求める
    • 差が最小な値を答えとする
  • 答えを出力

見たいな考え方で行けます スワップ後は全く同じ処理なので関数に分けたらきれいになるかもですね

以下コードになります。

    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <algorithm>
    using namespace std;
     
    int main(void){
        long long H,W;
        const int MAX = 100000;
        // input
        cin >> H >> W;
        // 制約
        if (H < 2 && H > MAX && W < 2 && W > MAX){
            return 0;
        }
        long long Sa,Sb,Sc,Smax,Smin;
        long long ans = 100000000000000;
        // 横横 縦縦
        if (H % 3 == 0 || W % 3 == 0){
            ans = 0;
        }else{
            ans = min(ans, min(H,W));
        }
        // 横 縦
        for (int i = 1;i < H;i++){
            Sa = i * W;
            long long w = W / 2;
            Sb = (H - i)*w;
            Sc = (H - i)*(W -w);
            Smax = max(Sa,max(Sc,Sb));
            Smin = min(Sa,min(Sc,Sb));
            ans = min(ans,Smax - Smin);
        }
        swap(H,W);
        // 縦 横
        for (int i = 1;i < H;i++){
            Sa = i * W;
            long long w = W / 2;
            Sb = (H - i)*w;
            Sc = (H - i)*(W -w);
            Smax = max(Sa,max(Sc,Sb));
            Smin = min(Sa,min(Sc,Sb));
            ans = min(ans,Smax - Smin);
        }
        cout << ans << endl;
     
        return 0;
    }

これでAC取れました。