概要

一昨日、昨日に引き続いて解いていきます。
ようやくC問題ですね。
この問題、分割数も求めれば実際にチョコレートを割るときに使えるかも…？

問題

n*mのチョコレートをk回割りたい。
割るときは、よくある溝に沿って割らないといけない。
一番小さいチョコが最大の大きさになるように割った時、その大きさを求めよ。

1 \leq n,m \leq 10^9 \\
1 \leq k \leq 2 \cdot 10^9

アルゴリズム

n,m,kがいつも通りでかいので、O(n)では間に合いませんね。
面積が$10^18$あるチョコレート、見てみたい。単位がわからんけど。
ということは、全部の割るパターンを網羅はできないです。
Div.2 A問題なら全探索もありですが、これは生憎Div.1 A問題ですね。

こういう時は、実際に割って考えてみましょう。

さて、適当に割ってみると、どうも縦と横、両方向から割るのはダメそうです。
縦なら縦、横なら横だけで割ると大きくできそうです。
割る回数が多い時は、しょうがなく両方向から割る感じですね。

長い辺を割るか、短い辺を割るかは場合によって違いそうです。
例えば、4×3を割るとき、k=1なら4の辺を割ると6になって最大ですが、k=2なら3の辺を割った場合が4で最大です。
ここに法則を求めるのは難しそうなので、両方求めて大きい方を採用します。
オーダー的には変化しないので問題ないでしょう。

なお、$(n-1)+(m-1) < k$なら割る回数が多すぎて、割ることができません。
こういう場合は-1を返して終わります。

まとめると、

割る回数が多過ぎたら-1
両方の辺を割らないといけない時は、単方向から割り切って、残りの回数でもう一方向から割る
それ以外の時は、縦横それぞれの方向で割った結果を比較

というシンプルな処理で実現できそうです。
これをコードに落とします。

解答

Scalaっぽさはありません。
関数型感出せるんかな、こういう処理…。

import scala.math.BigInt

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n,m,k = sc.nextInt

  def solve( n: BigInt, m: BigInt, k: BigInt ): BigInt = {

    if( k == 0 )
      n * m
    else if( (n-1) + (m-1) < k )
      -1
    else {
      val shortSide = n.min(m)
      val longSide = n.max(m)

      // 両方の辺を割らないといけない場合
      if( longSide < (k+1) ) {
        solve(1, m, (k + 1) - n).max(
          solve(n, 1, (k + 1) - m)
        )
      }
      // 片方向からだけ割って、大きい方を採用
      else {
        val nCut = ( n / (k+1) ) * m
        val mCut = ( m / (k+1) ) * n
        nCut.max(mCut)
      }
    }
  }

  println( solve( n, m, k ) )
}

結果

Time: 218 ms
Memoy: 0 KB

Codeforces #257 div.1 A

概要

問題

アルゴリズム

解答

結果