ABC062: C - Chocolate Bar

問題

C: Chocolate Bar - AtCoder Beginner Contest 062 | AtCoder

解説

縦の分割線を1本全探索し、残った部分の片方について縦または横で半分に割る。 半分に割る時幅が奇数の場合は、その小さい方を最小値の候補の一つ、大きい方を最大値の候補の一つとみなせる。 横の分割線を全探索する場合も試して、全体で4通りののループを行えば良い。

ll F(ll k, ll l, ll m) {
  ll max = std::max(k, l);
  ll min = k > l ? m : std::min(k, m);
  return max - min;
}

int main() {
  ll H, W; cin >> H >> W;
  ll ans = 1e18;
  REP(i, 1, H) {
    auto k = i * W;
    auto l = (H - i) * (W - W / 2);
    auto m = (H - i) * (W / 2);
    ans = std::min(ans, F(k, l, m));
  }

  REP(i, 1, W) {
    auto k = i * H;
    auto l = (W - i) * (H - H / 2);
    auto m = (W - i) * (H / 2);
    ans = std::min(ans, F(k, l, m));
  }

  REP(i, 1, H) {
    auto k = i * W;
    auto l = ((H - i) - ((H - i) / 2)) * W;
    auto m = (H - i) / 2 * W;
    ans = std::min(ans, F(k, l, m));
  }

  REP(i, 1, W) {
    auto k = i * H;
    auto l = ((W - i) - ((W - i) / 2)) * H;
    auto m = (W - i) / 2 * H;
    ans = std::min(ans, F(k, l, m));
  }

  std::cout << ans << "\n";
  
  return 0;
}

感想

以下の式が正しいが、

auto l = (H - i) * (W / 2);

次のように括弧を付け忘れて値が変わってしまい気づくのに時間がかかった。

auto l = (H - i) * W / 2;

整数除算で切り捨てが行われていると勘違いしていた精神異常者だ。