AOJ 1131 : Unit Fraction Partition

はじめに

ACM-ICPC 2年連続国内予選突破を目指して朝練を始めました。

Virtual Arena: Room 3044

• 寝坊
• IntelliJ Students License更新忘れ
• A問題なのに解けない

の3コンボ。泣きそう。思えば長いこと競プロしてない...。楽しいのになあ。

Unit Fraction Partition | Aizu Online Judge

2004 年のA問題。去年も朝練で解いた記憶があるけどどう解いていたか。

AIZU ONLINE JUDGE: Code Review
Fraction を作ろうとしていて、通分・約分をしている。

・・・。こんなの時間内でできないでしょ。A問題にそんな時間かけたくない。

大きくて1/12000 しか足さないので、浮動小数点でも解けるのでは？

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  Scanner sc;

  Main() {
    sc = new Scanner(System.in);
  }

  int ni() {
    return sc.nextInt();
  }

  public static void main(String[] args) {
    new Main().run();
  }

  int a, n;
  int p, q;

  int dfs(int last, int sa, int sn, double sm) {
    if (sn > n) {
      return 0;
    }

    int cnt = 0;
    if (Math.abs(sm - (double) p / q) < 1e-9) {
      ++cnt;
    }
    if ((sm - (double) p / q) > 1e-9) {
      return 0;
    }
    for (int i = last; i <= a / sa; ++i) {
      cnt += dfs(i, sa * i, sn + 1, sm + 1.0 / i);
    }
    return cnt;
  }

  void run() {
    for (; ; ) {
      p = ni();
      q = ni();
      a = ni();
      n = ni();

      if (p == 0) {
        break;
      }

      System.out.println(dfs(1, 1, 0, 0));
    }
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }
}

（1e-6 にするとWAになります。）

AC。やったぜ。これ以上シンプルにならないのでは？（慢心）

と思って検索してみたら、以下を発見。圧巻。こういう考え方パパッとできるようにしたいなあ。

taku-k.hatenablog.com