67392


# 問題文

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

<https://atcoder.jp/contests/abc062/tasks/arc074_a>

# 回答方針

以下の方針でアプローチを行いました。

## 縦か横の長さが３の倍数

答えは０に決定する。

## 縦か横のどちらかが偶数の場合

奇数の方の長さの切断場所を総当りで求める。  
偶数側の辺は２等分する。  
これで長方形は３等分されるので、最も差の少ない答えを計算する。

## 縦・横のどちらも奇数の場合

はじめの切断場所を総当りで求める。  
二度目の切断は可能な限り真ん中で行う。(奇数辺なので真ん中は不可能)  
３等分された長方形の最も差の少ない答えを計算する。

# 疑問点

例題のテストケースでは全て正解するのですが、  
実際にジャッジにかけると２件の不正解が出ます。

なぜ不正解がでるのでしょうか？  
自身では疑問が解決できなかったため、ここで質問させて頂きます。

# ジャッジにかけたソースコード

[code]

    H, W = list(map(int, input().split()))
    
    ans = float('inf')
    
    # 縦と横どちらかが偶数である場合を考える
    # 縦の長さが偶数の場合
    if H % 2 == 0:
      # 横から切断
      for x in range(1, W):
        S1 = x * H
        S2 = (W - x) * (H / 2)
        ans = min(ans, abs(S1 - S2))
    # 縦の長さが偶数の場合
    if W % 2 == 0:
      # 縦から切断
      for x in range(1, H):
        S1 = W * x
        S2 = (H - x) * (W / 2)
        ans = min(ans, abs(S1 - S2))
    # 縦と横の両方の長さが奇数だった場合
    else:
      # 横から切断
      for x in range(1, W):
        S1 = x * H
        S2 = (H // 2) * (W - x)
        S3 = ((H // 2) + 1) * (W - x)
        # 縦横療法が奇数だった場合３種類の面積が出現するので、大小関係を計算する必要が出てくる。
        S_max = max(S1, S3)
        S_min = min(S1, S2)
        ans = min(ans, S_max - S_min)
      # 縦から切断
      for x in range(1, H):
        S1 = W * x
        S2 = (W // 2) * (H - x)
        S3 = ((W // 2) + 1) * (H - x)
        S_max = max(S1, S3)
        S_min = min(S1, S2)
        ans = min(ans, S_max - S_min)
    
    # 縦か横が３等分できるなら、答えは０になる。
    if H % 3 == 0 or W % 3 == 0:
      ans = 0
    
    print(int(ans))
    
[/code]


CC BY-SA 4.0
2020-06-07T10:33:27.240
67389
2020-06-07T12:43:45.933
9616
question
python python3
AtCoder Beginner Contest 062　C問題で不正解が発生する


質問者さんのコードだとH=100000,
W=5という入力に対して50000を返しますが、実際には横方向に33333,33333,33334と切るとより良い5という値が得られます。

より単純に、縦横問わず１つ目の切れ目の入れ方を全列挙し、一方の切れ端をなるべく半分ずつになるように切る、というのが良いのではないでしょうか。


CC BY-SA 4.0
2020-06-07T11:59:43.633
67392
2020-06-07T12:11:53.833
2020-06-07T12:11:53.833
13199
13199
67389
answer


まず、解説と、自分のコードの違いを洗い出しましょう。

解説にある4パターンを、すべて調べるコードに、なっているか？。

縦の三分割と、横の三分割の、バリエーションを試してないのがわかります。


CC BY-SA 4.0
2020-06-07T12:43:45.933
67395
2020-06-07T12:43:45.933
18851
67389
answer