Facebook Hacker Cup 2012 Qualification Round

予選だったので、C++、Java、Pythonでのんびり解きました。2問通して予選通過しました。

Billboards

Javaで解きました。greedyで解けます。可変長引数でObject型の配列をとってdeepToString()でprintfデバッグする技は便利ですね。

view plainprint?

1. import java.util.*;  
2. import static java.util.Arrays.*;  
3. import static java.lang.Math.*;  
4. import java.io.*;  
5.   
6. public class Main {  
7.     private void debug(Object...obj) {  
8.         System.out.println(deepToString(obj));  
9.     }  
10.           
11.     public static void main(String args[]) {  
12.         try {  
13.               System.setIn(new BufferedInputStream(new FileInputStream("test.in")));  
14.               System.setOut(new PrintStream(new FileOutputStream("test.out")));  
15.           } catch (Exception e) {  
16.               e.printStackTrace();  
17.           }  
18.           
19.         new Main().solve();  
20.         System.out.flush();  
21.         System.err.println("You are done!!");  
22.     }  
23.   
24.     private void solve() {  
25.         Scanner sc = new Scanner(System.in);  
26.           
27.         int T = sc.nextInt();  
28.         sc.nextLine();  
29.         for (int t = 0; t < T; t++) {  
30.             String line[] = sc.nextLine().split(" ");  
31.               
32.             int w = Integer.valueOf(line[0]);  
33.             int h = Integer.valueOf(line[1]);  
34.             int len = line.length-2;  
35.             int words[] = new int[len];  
36.             for (int i = 0; i < len; i++)  
37.                 words[i] = line[i+2].length();  
38.               
39. //            debug(w, h, words);  
40.               
41.             int ret = 0;  
42.             for (int i = 1; i <= h; i++) {  
43.                 int r = 1;  
44.                 int c = 0;  
45.                 int cur = 0;  
46.                   
47.                 for (int cnt : words) {  
48.                     if (cur > 0) cur++;  
49.                     if ((cur + cnt) * i > w) {  
50.                         cur = cnt;  
51.                         ++r;  
52.                     }  
53.                     else {  
54.                         cur += cnt;  
55.                     }  
56.                     c = max(c, cur);  
57.                 }  
58.                   
59.                 if (i*r <= h && i*c <= w)  
60.                     ret = i;  
61.             }  
62.               
63.             System.out.printf("Case #%d: %d\n", t+1, ret);  
64.         }          
65.     }  
66. }  

import java.util.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;
import java.io.*;

public class Main {
    private void debug(Object...obj) {
        System.out.println(deepToString(obj));
    }
        
    public static void main(String args[]) {
        try {
              System.setIn(new BufferedInputStream(new FileInputStream("test.in")));
              System.setOut(new PrintStream(new FileOutputStream("test.out")));
          } catch (Exception e) {
              e.printStackTrace();
          }
        
        new Main().solve();
        System.out.flush();
        System.err.println("You are done!!");
    }

    private void solve() {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        sc.nextLine();
        for (int t = 0; t < T; t++) {
            String line[] = sc.nextLine().split(" ");
            
            int w = Integer.valueOf(line[0]);
            int h = Integer.valueOf(line[1]);
            int len = line.length-2;
            int words[] = new int[len];
            for (int i = 0; i < len; i++)
                words[i] = line[i+2].length();
            
//            debug(w, h, words);
            
            int ret = 0;
            for (int i = 1; i <= h; i++) {
                int r = 1;
                int c = 0;
                int cur = 0;
                
                for (int cnt : words) {
                    if (cur > 0) cur++;
                    if ((cur + cnt) * i > w) {
                        cur = cnt;
                        ++r;
                    }
                    else {
                        cur += cnt;
                    }
                    c = max(c, cur);
                }
                
                if (i*r <= h && i*c <= w)
                    ret = i;
            }
            
            System.out.printf("Case #%d: %d\n", t+1, ret);
        }        
    }
}

Auction

C++で解こうとしました。解けませんでした。

値段と重さを最小化（terrible dealの場合は最大化）するようなパレート曲面みたいなのを出せばいいと思います。商品の数が10¹⁸なので、全部の商品を列挙するのは無理。値段と重さは周期的に変化していて、それぞれの周期は大きくても10⁷です。値段と重さをペアに考えたときの周期はそれぞれの周期のLCMになりますが、これでも大きい。ということで、値段をfixしたときにその値段で取り得る重さの最小値を出すことができればいいです。そして固定した値段、求まった重さになるような商品が何個あるかを数えればいいというようなことを考えました。が、重さの最小値を出す方法がうまく思い付かず断念。O(1)である区間中の複数の部分区間の和を求めるときにやるようなことが最小値でできないかとか、セグメント木で書けないかとか、いろいろ考えましたが実装までいきませんでした。要復習です。

Alphabet Soup

Pythonで解きました。これが今回の問題セットで一番簡単でした。

view plainprint?

1. import sys  
2.   
3. sys.stdin = open("test.in", "r")    
4. sys.stdout = open("test.out", "w")  
5.   
6. T = int(raw_input())  
7. goal = "HACKERUP"  
8.   
9. for t in range(T):  
10.     line = raw_input()  
11.     ret = len(line);  
12.     for s in goal:  
13.         if s == 'C':  
14.             ret = min(ret, line.count(s)/2)  
15.         else:  
16.             ret = min(ret, line.count(s))  
17.     print "Case #%d: %d" % (t+1, ret)  
18.   
19. sys.stdout.flush()  
20. sys.stderr.write("You are done!!")  

import sys

sys.stdin = open("test.in", "r")  
sys.stdout = open("test.out", "w")

T = int(raw_input())
goal = "HACKERUP"

for t in range(T):
    line = raw_input()
    ret = len(line);
    for s in goal:
        if s == 'C':
            ret = min(ret, line.count(s)/2)
        else:
            ret = min(ret, line.count(s))
    print "Case #%d: %d" % (t+1, ret)

sys.stdout.flush()
sys.stderr.write("You are done!!")