POJ 3388 - Japanese Puzzle

http://poj.org/problem?id=3388

概要

K 種類の絵がそれぞれ L[i] 個あり，これを N * N のグリッドに並べる． ΣL[i] = N^2 であることは保証されている．

このとき，全く同じパターンの行を最大何個作ることができ，またそのときはどのようなパターンであるかを答える． その最大の個数を達成できればどのようなパターンを答えてもよい (Special Judge)．

制約

• 1 <= N <= 4 * 10^4
• 1 <= K <= 5 * 10^4

解法

全く同じパターンを m 行作れるかどうかを O(K) で判定しながら m に関して二分探索して O(K log N) で計算できる．

G++，GCC だと TLE するけど，全く同じコードを C で提出すると 1000MS で通るクソゲー．

 1 #include <stdio.h>
 2 
 3 int f(int x, int K, const int *a)
 4 {
 5   int i, n = 0;
 6   for (i = 0; i < K; i++) {
 7     n += a[i]/x;
 8   }
 9   return n;
10 }
11 
12 int main()
13 {
14   int N, K;
15   int i, j;
16   static int a[50000];
17   int lo, hi;
18   int c;
19 
20   scanf("%d %d", &N, &K);
21   for (i = 0; i < K; i++) {
22     scanf("%d", &a[i]);
23   }
24 
25   lo = 1; hi = N;
26   while (lo+1 < hi) {
27     const int mid = (lo + hi)/2;
28     const int x = f(mid, K, a);
29     if (x >= N) {
30       lo = mid;
31     } else {
32       hi = mid;
33     }
34   }
35   if (f(hi, K, a) >= N) {
36     lo = hi;
37   }
38   printf("%d\n", lo);
39   c = 0;
40   for (i = 0; i < K && c < N; i++) {
41     for (j = 0; j < a[i]/lo && c < N; j++, c++) {
42       printf("%d\n", i+1);
43     }
44   }
45   return 0;
46 }