072 C - 4/N

数学から決まる議論

特に小さいNに対して大学受験でもよくある問題です. 数学の話でもあって数学系学習と並行した議論を目指す私のスタンスからは大事なため, 公式解説の議論を簡単にくり返します.

対称性によってどれから議論してもよいためまずはhから考えましょう. 必要条件からの絞り込みでhを小さい方から増やして具体的に確認し続ければよく, まさにアルゴリズミックに次のように議論を進めます.

と続けます. 原理的にこれしか議論しようはないものの, 時間内に解けるかが懸念点です. そして問題文でh,n,w≤3500が保証されているため, この範囲内でけりが着くはずと思って全探索します. もちろん3つ全てでループするとTLEするため, 2つ決まれば3つ目は自動的に決まる性質を使って二重ループで片付けます.

解答1: 素直なループ

1つ求めればよいため, 1つ決まったら計算を停止させます. 命令型的なfor文とbreakを使えればよいのですが, 残念ながらF#にはbreakがないようで, 使うならwhileとフラグ管理です.

ただし命令型として素直なforとbreakがないだけです. Haskellの遅延リスト・遅延評価と同じく, 遅延評価してくれるseqを使いましょう. 次のような適切な書き方をすれば明示的なbreakが不要です.

1
2
3
4
5
  seq {
    for h in 1L..N do
      for k in 1L..M do
        if someJudge then yield value
  } |> Seq.head

for h in 1L..N doがカウントアップのforで, 二重ループだから二つ出てきます. 条件を満たした値を取る部分がif b then yield valueです. この場合はyieldキーワードはなくてもよいようですが手癖で書いています. 詳しくは公式のシーケンスを見てください. seqとコンピュテーション式による見慣れない構文には慣れるしかありません.

seq {...}でいわば遅延リストを作り, その先頭の値をSeq.headで取れば必要な計算だけで処理が終わります. Schemeのように有理数を処理してくれる言語もありますが, F#標準で有理数はないため整数の範囲でおさまるように標準的な対処を取ります. 適当なところで打ち切った数による積で構成する三つ目の整数がintに入る保証がないため, int64で計算する点に注意すれば, あとは特に問題ないでしょう. 結論としては次のようなコードで通ります.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
let solve N =
  seq {
    for h in 1L..3500L do
      for k in 1L..h do
        let d = 4L*h*k-N*(k+h)
        if d>0L && (N*h*k)%d=0L then yield (h,k,(N*h*k)/d)
  } |> Seq.head |> fun (h,k,w) -> [|h;k;w|]

let N = stdin.ReadLine() |> int64
solve N |> Array.map string |> String.concat " " |> stdout.WriteLine

出力処理は何となく既存の出力処理を流用するために配列にしました. タプルのまま次のようにも書けます.

1
solve N |> fun (h,n,k) -> printfn "%d %d %d" h n k

解説2: 再帰

「競技プログラミングのためのF#入門」で無限ループを含めてループは再帰で書けると書きました. 実際ここでも再帰で書けます. 提出結果を見ると再帰の方がメモリを食っています. 2022-12時点では効率を求めるよりも通るコードを書く, さらには基本的なアルゴリズムの教育用コンテンツを作る方に主眼があるため, 別解として再帰によるコードも紹介します.

forのコードを素直に書き換えればよく, 結論としては次のように書けます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
let solve N =
  let rec frec h k =
    let d = 4L*h*k - N*(k+h)
    if d>0L && (N*h*k)%d=0L then (h,k,(N*h*k)/d)
    elif k<h then frec h (k+1L)
    else frec (h+1L) 1L
  frec 1L 1L

let N = stdin.ReadLine() |> int64
solve N |> fun (h,k,w) -> printfn "%d %d %d" h k w

ポイントはもちろんifの条件分岐です. 最初に条件をみたして値を返すか(停止するか)判定し, 停止しなければhかkを適切にカウントアップします. ここでは上記のseq+ループアルゴリズムに合わせました.

コードが読みにくくなるためここでは勧めませんが, 例えば次のようにまとめて書けます.

1
2
3
4
5
let solve N =
  let rec frec h k = let d = 4L*h*k - N*(k+h) in if d>0L && (N*h*k)%d=0L then (h,k,(N*h*k)/d) elif k<h then frec h (k+1L) else frec (h+1L) 1L
  frec 1L 1L

stdin.ReadLine() |> int64 |> solve |> fun (h,k,w) -> printfn "%d %d %d" h k w

さらに次のようにも書けます.

1
2
let solve N = let rec frec h k = let d = 4L*h*k - N*(k+h) in if d>0L && (N*h*k)%d=0L then (h,k,(N*h*k)/d) elif k<h then frec h (k+1L) else frec (h+1L) 1L in frec 1L 1L
stdin.ReadLine() |> int64 |> solve |> fun (h,k,w) -> printfn "%d %d %d" h k w

let ... inはOCamlのコードでよく出てきます.