AtCoder Begginer Contest101

C.Minimization(300)

問題

https://beta.atcoder.jp/contests/abc101/tasks/arc099_a

方針

最初に1を含んだk個置き換える。以降は最初に1で置き換えた範囲の1つの数とその他k-1個ずつ置き換えることができる。k-1個置き換える回数をmとすると、

k + m(k-1) >= n
⇔m >= (n-k)/(k-1)

が成り立つので、これを満たす最小の正の整数 m は m = ceil( (n-k)/(k-1) ) で答えは m+1 と考えました。がこの解法は考察が適当なので実は嘘解答なのかもしれません。*1

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int k = in.nextInt();
            long[] a = in.nextLongArray(n);

            out.println(1 + (n-2)/(k-1));
        }

雑記

INPUTの 1~N は実は使用せずに O(1) で解けてしまう不思議な問題でした。本番ではこの問題を6分程度で解けたため、過去最高パフォーマンスの1600が出ました。

D.Snuke Numbers(500)

問題

https://beta.atcoder.jp/contests/abc101/tasks/arc099_b

すぬけ数を小さい数からK個求めよ。すぬけ数とは以下の条件を満たす数である。

  • 正の整数 n であって、n < m である任意の正の整数 m に対して n/S(n) <= m/S(m) を満たす n
  • S(n) = n の桁和

制約

  • 1 <= k
  • すぬけ数は 1015 以下

方針

実験するとすぬけ数は以下のようになっているだろうと想像がつきます。

1,2,3,4,5,6,7,8,9 19,29,39,...,99 199,299,...999 10999,11999,...,99999

...

109999999,119999999,...,999999999,1009999999,1019999999,1029999999

この実験から、1～9以外は先頭のいくつかの桁を除いてすべて9になっていると仮定します。(以降証明なしにこの仮定が正しいとします)。そのとき、先頭からどれくらい数まで9でなくてもいいのでしょうか。この議論については、けんちょんさんのブログが詳しいです。{p}9999999と{p+1}9999999を比較することでpの範囲を確認しています。(1 <= p)

ARC 099 D - Snuke Numbers (500 点) - けんちょん (drken) の競プロ精進記録

p*10n-1 と (p+1)*10n-1 を比較する。数nの桁和をb=f(n)とする。

(p*10n-1)/b > ((p+1)*10n-1)/(b+1)
⇔p*10n-1 > b*10n
よりざっくり p > b
bは最大で15*9=135であるから、p > 135の場合はすぬけ数ではなくなる。
安全を考慮しても、p <= 150 までを試せば十分すぬけ数を列挙できる。

上記の議論により、高速にすぬけ数になりうる候補の数を列挙することができました。

次に、候補として上げた数が実際にすぬけ数になりうるかどうかを検証します。 すぬけ数でない数はどういう数か確認します。これは次のように言えます。

  • 正の整数 n であって、n < m である、ある正の整数 m に対して n/S(n) > m/S(m) を満たす n

具体的な m の数はわかりませんが、ここでは乱択で n < m の m について105回程度ためして問題がなければ、すぬけ数であることにします。 乱択だとかなり通りませんでした。n < m である他のすぬけ数の候補と比較して、すべての数において条件を満たすのであればすぬけ数です。

ここ、なぜ他のすべての候補の数と比較すれば求まるのか分かっていません。理由がわかる方、コメント欄で教えていただけると助かります。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long k = in.nextLong();

            Set<Long> set = new TreeSet<>();
            long base = 1;
            for (int i = 0; i < 15; i++) {
                for (int j = 1; j < 150; j++) {
                    long num = (j*base)-1;
                    if (1 <= num && num <= pow(10, 15)) {
                        set.add(num);
                    }
                }
                base *= 10;
            }

            List<Long> list = new ArrayList<>();
            for (long n : set) {
                boolean not = false;
                for (long m : set) {
                    if (n < m && isNotSunuke(n, m)) {
                        not = true;
                        break;
                    }
                }
                if (!not) list.add(n);
            }

            for (int i = 0; i < k; i++) {
                out.println(list.get(i));
            }
        }

        long s(long n) {
            long ret = 0;

            while (n > 0) {
                ret += n % 10;
                n /= 10;
            }
            return ret;
        }

        boolean isNotSunuke(long n, long m) {
            return n*s(m) > m*s(n);
        }

雑記

がちな数学問題と思いましたが、実験要素で解の候補をエスパーできるなど、プログラミング要素も十分強いのかもしれません。この問題のエスパー解答では9以外の数pがどの範囲に収まるのか確認できると、全探索でも間に合い、十分解にたどりつけそうです。

ポイント

  • 解の範囲を絞る
  • 何かを正しいと仮定
  • 実験

*1:最初に1を含めたkの範囲を選ぶ方法はk通りありますが、最適に選ぶとceil( (n-k)/(k-1) )で良さそうです