裏 RjpWiki

文字通り,RjpWiki の裏を行きます
R プログラム コンピュータ・サイエンス 統計学

ホーム画面を整理して!

2017年06月13日 | ブログラミング

ホーム画面を整理して!

締め切りが 2017/06/13 10:00 AM なので,その 1 分後に投稿されるように予約

設問

多くの人が使うようになったスマートフォン。
そのホーム画面には多くのアプリのアイコン(以下、アイコン)が並びます。
そこで、このアイコンをフォルダにまとめて整理することを考えます。

1つのフォルダには1個~9個のアイコンを登録でき、登録するとフォルダ1つのアイコンにまとまり、そのフォルダに登録されているアイコンの数が識別できるようになります。
なお、フォルダの中にフォルダを作ることはできません。
n 個のアイコンを整理するとき、そのフォルダ構成について、アイコンの数の組み合わせがいくつ考えられるかを求めます。
ただし、個々のアイコンは識別せず、並び順も考えないものとし、アイコンの数の組み合わせだけを考えます。
(フォルダ内にあるアイコンの数が異なる場合は、別々のフォルダ構成としてカウントします。)
なお、ホーム画面には最大で24個のアイコンを並べられるものとし、n は 1≦n≦216を満たす整数とします。
例えば、n = 5 のとき、以下の7通りがあります。
(図の黄色はフォルダを、数字はアイコンの数を表します。)
当然、n = 216のときは、すべてフォルダにまとめた1通りしかありません。

標準入力から n が与えられるとき、アイコンの数の組み合わせがいくつあるかを求め、標準出力に出力してください。

【入出力サンプル】
標準入力
5

標準出力
7

==============================================================

整数分割問題だが,分割数が 24 以下という制約があるもの。
n=108 で対称。つまり,f(128) == f(88), f(214) == f(2)。
R だと,制限時間オーバー

initDiv = function(length, max) {
    ary = NULL
    repeat {
        if (max >= length) {
            ary = c(ary, length)
            return(ary)
        } else {
            ary = c(ary, max)
            length = length - max
        }
    }
}

nextDiv = function(ary) {
    # 1でない要素を後ろから探す
    sum = 0
    for (pos in length(ary):1) {
        a = ary[pos]
        sum = sum + a
        if (a != 1 && (pos > 1 &&  ary[pos - 1] >= ary[pos])) {
            break
        }
    }
    if (ary[1] == 1) { # 全て1
        return(FALSE)
    }
    ary = ary[1:pos]
    ary[pos] = ary[pos] - 1
    max = ary[pos]
    sum = sum - max
    pos = pos + 1
    repeat {
        if (pos > 24) {
            ary[pos] = sum
            return(ary)
        }
        if (max >= sum) {
            ary[pos] = sum
            return(ary)
        } else {
            ary[pos] = max
            sum = sum - max
        }
        pos = pos + 1
    }
}

f = function(length, max) {
    length = min(length, 216 - length)
    d = initDiv(length, max)
    count = 1
    repeat {
        d = nextDiv(d)
        if (length(d) == 1) {
            break
        }
        count = count + (24 >= length(d))
    }
    cat(count)
}

f(128)
f(5, 9) # 7
f(10, 9) # 41
system.time(f(50, 9)) # 39777, 0.884 sec.
system.time(f(128, 9)) # 449718, 9.317 sec.
system.time(f(214, 9)) # 2

Java で書いて OK

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int n, i;
        if (false) {
            n = 88; // 449718
        } else {
            Scanner cin = new Scanner(System.in);
            String line;
            line = cin.nextLine();
            n = Integer.parseInt(line);
            n = Math.min(n, 216-n);
        }
            int m = 9;
            int[] d = initDiv(n, m);
            int count = 0;
            for (;;) {
                for (i = 0; i < d.length; i++) {
                    if (d[i] == 0 || i > 24) {
                        break;
                    }
                }
                if (24 >= i) {
                    count++;
                }
                if (nextDiv(d) == false) {
                    break;
                }
            }
            System.out.println(count);

            long end = System.currentTimeMillis();
            System.out.println((end - start)  + " ms");
    }

    static int length(int[] a) {
        for (int len = 0;; len++) {
            if (a[len] == 0)
                return len;
        }
    }

    static int[] initDiv(int length, int max) {
        int a = length / max;
        int[] ary = new int[1000];
        for (int i = 0; i < a; i++) {
            ary[i] = max;
        }
        ary[a] = length % max;
        return (ary);
    }

    static boolean nextDiv(int[] ary) {
        int sum, pos, a, max;
        sum = 0;
        for (pos = length(ary) - 1; pos >= 0; pos--) {
            a = ary[pos];
            sum += a;
            if (a != 1) {
                break;
            }
        }
        if (pos == -1) {
            return false;
        }
        max = --ary[pos];
        sum -= max;
        for (pos++;; pos++) {
            if (max >= sum) {
                ary[pos] = sum;
                for (int j = pos + 1; j < 1000; j++) {
                    ary[j] = 0;
                }
                return true;
            } else {
                ary[pos] = max;
                sum -= max;
            }
        }
    }
}

ジャンル:
ウェブログ
コメント   この記事についてブログを書く
この記事をはてなブックマークに追加
« スミス数 | トップ | 「タンジェント・フラクショ... »
最近の画像もっと見る

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。

コメント利用規約に同意の上コメント投稿を行ってください。

数字4桁を入力し、投稿ボタンを押してください。

あわせて読む