ABC062C
解けなかった…。
――――――――――――――――――――――――
問題文
縦Hブロック、横Wブロックの板チョコがあります。 すぬけ君は、この板チョコをちょうど3つのピースに分割しようとしています。 ただし、各ピースはブロックの境目に沿った長方形でなければなりません。
すぬけ君は3つのピースの面積 (ブロック数) をできるだけ均等にしようとしています。 具体的には3つのピースの面積の最大値をSmax、最小値をSminとしたとき、Smax−Sminを最小化しようとしています。Smax−Sminの最小値を求めてください。
制約
• 2≤H,W≤10^5
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
Smax−Sminの最小値を出力せよ。
――――――――――――――――――――――――
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;
class Program{
public static void Main(){
var input = Console.ReadLine().Split();
int h = int.Parse(input[0]);
int w = int.Parse(input[1]);
long min = Math.Min(smin(h,w),smin(w,h));
Console.WriteLine(min);
}
//縦から切っていったときに最小値を返す関数
static long smin(int h, int w){
long a,b,c;
long min = h * w;
for(int i=1;i<h;i++){
a = i * w;
//■■■■ a こういう分割
//■■■■ b
//■■■■ c
b = ((h-i)/2) * w;
c = h * w - a - b;
if(b>0 && c>0){
min = hikaku(a,b,c,min);
}
//■■■■ a こういう分割
//■ ■ b c
b = (h-i) * (w/2);
c = h * w - a - b;
if(b>0 && c>0){
min = hikaku(a,b,c,min);
}
}
return min;
}
//面積a,b,cとその時点の最小値minからSmax-Sminの最小値を求める関数
static long hikaku(long a, long b, long c,long min){
long s1 = Math.Min(a,Math.Min(b,c));
long s2 = Math.Max(a,Math.Max(b,c));
return Math.Min(s2-s1,min);
}
}
考え方的にはあっていると思うんだけどなー。いったん保留にして先に進みます。
C#で初めて関数使ったかもしれない。