Facebook Hacker Cup 2012 Round1

全部解けました！！無事Round2出場決定です。Top100に残ってT-shirtsゲットしたい。。

Checkpoint

　数学の問題。パスカルの三角形を使って解きました。下のコードでは、len[i]に最短路のパターン数がiになる場合における始点-終点間のマンハッタン距離の最小値を格納しています。len[]が分かれば、答えはlen[j] + len[S/j]の最小値です（jはSの約数）。

view plainprint?

1. const int MAX = 10000000;  
2. const int INF = 100000000;  
3. int comb[2][10000];  
4. int len[MAX+1];  
5.   
6. void solve() {  
7.     for (int i = 0; i <= MAX; i++)  
8.         len[i] = i;  
9.   
10.     memset(comb, 0, sizeof(comb));  
11.     comb[0][0] = 1;  
12.     for (int i = 0; i < 10000; i++) {  
13.         int now = i&1;  
14.         int next = (i+1)&1;  
15.   
16.         if (i > 0) {  
17.             for (int j = 0; j <= i; j++) {  
18.                 int k = comb[now][j];  
19.                 if (k <= MAX)  
20.                     len[k] = min(len[k], i);  
21.             }  
22.         }  
23.   
24.         memset(comb[next], 0, sizeof(comb[next]));  
25.         for (int j = 0; j <= i; j++) {  
26.             comb[next][j] = min(INF, comb[next][j] + comb[now][j]);  
27.             comb[next][j+1] = min(INF, comb[next][j+1] + comb[now][j]);  
28.         }  
29.     }  
30.   
31.     int R, S;  
32.     scanf("%d", &R);  
33.     for (int i = 0; i < R; i++) {  
34.         scanf("%d", &S);  
35.   
36.         int ret = INF;  
37.         for (int j = 1; j * j <= S; j++) {  
38.             if (S % j == 0)  
39.                 ret = min(ret, len[j] + len[S/j]);  
40.         }  
41.   
42.         printf("Case #%d: %d\n", i+1, ret);  
43.     }  
44. }  

const int MAX = 10000000;
const int INF = 100000000;
int comb[2][10000];
int len[MAX+1];

void solve() {
    for (int i = 0; i <= MAX; i++)
        len[i] = i;

    memset(comb, 0, sizeof(comb));
    comb[0][0] = 1;
    for (int i = 0; i < 10000; i++) {
        int now = i&1;
        int next = (i+1)&1;

        if (i > 0) {
            for (int j = 0; j <= i; j++) {
                int k = comb[now][j];
                if (k <= MAX)
                    len[k] = min(len[k], i);
            }
        }

        memset(comb[next], 0, sizeof(comb[next]));
        for (int j = 0; j <= i; j++) {
            comb[next][j] = min(INF, comb[next][j] + comb[now][j]);
            comb[next][j+1] = min(INF, comb[next][j+1] + comb[now][j]);
        }
    }

    int R, S;
    scanf("%d", &R);
    for (int i = 0; i < R; i++) {
        scanf("%d", &S);

        int ret = INF;
        for (int j = 1; j * j <= S; j++) {
            if (S % j == 0)
                ret = min(ret, len[j] + len[S/j]);
        }

        printf("Case #%d: %d\n", i+1, ret);
    }
}

Recover the Sequence

　実装問題。最初にord[i] = iとした配列を用意。デバッグ情報を元にマージソートを再現します。ソート完了後のord[]を見ることで、iはもともとord[i]番目にあったんだなということが分かります。

view plainprint?

1. const LL MOD = 1000003;  
2.   
3. vector<int> merge_sort(vector<int> arr) {  
4.     int n = arr.size();  
5.     if (n <= 1)  
6.         return arr;  
7.   
8.     int mid = n/2;  
9.     vector<int> arr1(arr.begin(), arr.begin()+mid);  
10.     arr1 = merge_sort(arr1);  
11.     vector<int> arr2(arr.begin()+mid, arr.end());  
12.     arr2 = merge_sort(arr2);  
13.   
14.     unsigned int p = 0, q = 0;  
15.     for (;p < arr1.size() && q < arr2.size();) {  
16.         int c = getchar();  
17.         if (c == '1') {  
18.             arr[p+q] = arr1[p];  
19.             ++p;  
20.         }  
21.         else {  
22.             arr[p+q] = arr2[q];  
23.             ++q;  
24.         }  
25.     }  
26.   
27.     for (;p < arr1.size(); p++)  
28.         arr[p+q] = arr1[p];  
29.     for (;q < arr2.size(); q++)  
30.         arr[p+q] = arr2[q];  
31.   
32.     return arr;  
33. }  
34.   
35. void solve() {  
36.     int T;  
37.     int N;  
38.     vector<int> ord;  
39.     vector<int> pos;  
40.   
41.     cin >> T;  
42.     for (int t = 0; t < T; t++) {  
43.         cin >> N;  
44.   
45.         ord.resize(N);  
46.         for (int i = 0; i < N; i++)  
47.             ord[i] = i;  
48.   
49.         getchar();  
50.         ord = merge_sort(ord);  
51.   
52.         pos.resize(N);  
53.         for (int i = 0; i < N; i++)  
54.             pos[ord[i]] = i+1;  
55.   
56.         LL ret = 1;  
57.         for (int i = 0; i < N; i++)  
58.             ret = (31 * ret + pos[i]) % MOD;  
59.   
60.         printf("Case #%d: %I64d\n", t+1, ret);  
61.     }  
62. }  

const LL MOD = 1000003;

vector<int> merge_sort(vector<int> arr) {
    int n = arr.size();
    if (n <= 1)
        return arr;

    int mid = n/2;
    vector<int> arr1(arr.begin(), arr.begin()+mid);
    arr1 = merge_sort(arr1);
    vector<int> arr2(arr.begin()+mid, arr.end());
    arr2 = merge_sort(arr2);

    unsigned int p = 0, q = 0;
    for (;p < arr1.size() && q < arr2.size();) {
        int c = getchar();
        if (c == '1') {
            arr[p+q] = arr1[p];
            ++p;
        }
        else {
            arr[p+q] = arr2[q];
            ++q;
        }
    }

    for (;p < arr1.size(); p++)
        arr[p+q] = arr1[p];
    for (;q < arr2.size(); q++)
        arr[p+q] = arr2[q];

    return arr;
}

void solve() {
    int T;
    int N;
    vector<int> ord;
    vector<int> pos;

    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> N;

        ord.resize(N);
        for (int i = 0; i < N; i++)
            ord[i] = i;

        getchar();
        ord = merge_sort(ord);

        pos.resize(N);
        for (int i = 0; i < N; i++)
            pos[ord[i]] = i+1;

        LL ret = 1;
        for (int i = 0; i < N; i++)
            ret = (31 * ret + pos[i]) % MOD;

        printf("Case #%d: %I64d\n", t+1, ret);
    }
}

Squished Status

　DPの問題。dp[i][j]にcompressed messageのi番目まで見終わったとき最後の文字コードがjとなっているときの場合の数を格納すればOKです。

view plainprint?

1. const LL MOD = 4207849484LL;  
2. LL dp[1024][256];  
3.   
4. void solve() {  
5.     int N;  
6.   
7.     scanf("%d", &N);  
8.     for (int t = 0; t < N; t++) {  
9.         int M;  
10.         string comp;  
11.   
12.         cin >> M >> comp;  
13.         int len = comp.length();  
14.         memset(dp, 0, sizeof(dp));  
15.         dp[0][0] = 1;  
16.   
17.         for (int i = 0; i < len; i++) {  
18.             for (int j = 0; j <= M; j++) {  
19.                 if (dp[i][j] == 0)  
20.                     continue;  
21.   
22.                 int d = comp[i] - '0';  
23.                 int k = 10 * j + d;  
24.   
25.                 if (0 < k && k <= M)  
26.                     dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % MOD;  
27.                 if (k != d && 0 < d && d <= M)  
28.                     dp[i+1][d] = (dp[i+1][d] + dp[i][j]) % MOD;  
29.             }  
30.         }  
31.   
32.         LL ret = 0;  
33.         for (int i = 1; i <= M; i++)  
34.             ret = (ret + dp[len][i]) % MOD;  
35.   
36.         printf("Case #%d: %I64d\n", t+1, ret);  
37.     }  
38. }  

const LL MOD = 4207849484LL;
LL dp[1024][256];

void solve() {
    int N;

    scanf("%d", &N);
    for (int t = 0; t < N; t++) {
        int M;
        string comp;

        cin >> M >> comp;
        int len = comp.length();
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= M; j++) {
                if (dp[i][j] == 0)
                    continue;

                int d = comp[i] - '0';
                int k = 10 * j + d;

                if (0 < k && k <= M)
                    dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % MOD;
                if (k != d && 0 < d && d <= M)
                    dp[i+1][d] = (dp[i+1][d] + dp[i][j]) % MOD;
            }
        }

        LL ret = 0;
        for (int i = 1; i <= M; i++)
            ret = (ret + dp[len][i]) % MOD;

        printf("Case #%d: %I64d\n", t+1, ret);
    }
}

C言語の副作用完了点

以下のようなコードを書いたところ、"operation on 'i' may be undefined"というwarningが出ました。

view plainprint?

1. int main() {  
2.     int a[10];  
3.   
4.     int i = 0;  
5.     a[i] = i++;  
6.   
7.     return 0;  
8. }  

int main() {
    int a[10];

    int i = 0;
    a[i] = i++;

    return 0;
}

調べてみると、「ある変数に 対して副作用が生じるような式においては、他の箇所でその変数を参照すること はできません。その結果は未定義とされています。」ということだそうです。

ちなみに、ある時点においてそこまでの副作用が全て完了することが保証されている区切 りのことを、副作用完了点(sequence point)と呼ぶそうです。後置インクリメントは次の副作用完了点の前までに実行されることは保証されています。しかし、後置演算の該当部分が読み込まれてすぐ、かつ、他の部分が評価される前に実行されるとは限らないということです。

上の例の他にも以下のような処理も同様の理由で未定義となります。

view plainprint?

1. int main() {  
2.     int x, y;  
3.   
4.     x = 0;  
5.     printf("%d\n", x + x++);   // NG  
6.   
7.     y = x + ++x;     // NG  
8.       
9.     return 0;  
10. }  

int main() {
    int x, y;

    x = 0;
    printf("%d\n", x + x++);   // NG

    y = x + ++x;     // NG
    
    return 0;
}

参考サイト：

http://www.kouno.jp/home/c_faq/c3.html

http://www.st.rim.or.jp/~phinloda/cqa/cqa7.html

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!!")

読書「罪と罰（上）」

ドストエフスキーの「罪と罰」の上巻を読みました。海外の古典文学作品を読んだのは人生初です。

　まず、あらすじをちょっとだけ書きます。貧困に苦しむ元学生のラスコーリニコフが金貸しの老婆を殺害します。そして犯行現場を偶然見てしまった老婆の妹も殺してしまいます。これが罪の部分です。後半では、事件後のラスコーリニコフの後悔、焦燥、苦難といった心理描写、証拠隠滅のためにとる不可解な行動、それを疑う彼の家族・友人とのやり取りが書かれています。

　上巻の最後の部分に出てくるラスコーリニコフが週刊誌に寄稿した犯罪に関する思想がこの小説の大きなテーマに繋がっているかと思います。「世界を変えるような優れた人間は犯罪を犯してもよいのか？」ということです。それから本当は大したことのない青年が、自分は優れた人間だと勘違いをして犯罪を犯し出したらどうなるのか？という観点も興味を惹かれるものでした。

　下巻でラスコーリニコフがどうなるのか、そして、この小説のテーマにどのような結論付けがなされるのか楽しみです。

サーバー奮闘記（19） Apacheで負荷分散

Apacheのmod_proxy_balancerを使って、負荷分散の実験をしたのでメモを残しておきます。サーバーはUbuntuです。

■できたもの
http://goodpreparations.co.cc/gourmet/main.html

■やったこと

1. 疑似的に複数のHTTPサーバーが起動しているような環境にするため、3つのVirtualHostを作成してlistenするポートで区別することにした。
2. Apacheのmod_proxyモジュールを利用し、リバースプロキシが実現できることを確認した。
3. Apacheのmod_proxy_balancerモジュールを利用して、ロードバランシングが実現できることを確認した。

■設定箇所

1. /etc/apache2/sites-available/defaultの変更箇所

<VirtualHost *:80>

　　　　# not use forward proxy

　　　　ProxyRequests Off

　　　　# simple proxy setting

　　　　# set reverse proxy

　　　　#ProxyPass /gourmet http://183.181.30.44:81/gourmet

　　　　# override http header info(URL) to reverse proxy server

　　　　#ProxyPassReverse /gourmet http://183.181.30.44:81/gourmet

　　　　# load balancing proxy setting

　　　　<Proxy balancer://gourmet>

　　　　　　　　BalancerMember http://183.181.30.44:81/gourmet/

　　　　　　　　BalancerMember http://183.181.30.44:82/gourmet/

　　　　</Proxy>

　　　　ProxyPass /gourmet balancer://gourmet

　　　　ProxyPassReverse /gourmet balancer://gourmet

</VirtualHost>

<VirtualHost *:81>

　　　　# root directory

　　　　DocumentRoot /home/kenji/gourmet

　　　　<Directory />

　　　　　　　　# enable to follow symbolic links, hide contents of directory

　　　　　　　　Options FollowSymLinks

　　　　　　　　# forbid to override the settings on sub-directories

　　　　　　　　AllowOverride None

　　　　</Directory>

　　　　# error log path

　　　　ErrorLog /home/kenji/gourmet/error.log

　　　　# custom log path

　　　　CustomLog /home/kenji/gourmet/access.log combined

</VirtualHost>

<VirtualHost *:82>

　　　　DocumentRoot /home/kenji/gourmet

　　　　<Directory />

　　　　　　　　Options FollowSymlinks

　　　　　　　　AllowOverride None

　　　　</Directory>

　　　　ErrorLog /home/kenji/gourmet/error2.log

　　　　CustomLog /home/kenji/gourmet/access2.log combined

</VirtualHost>

2. /etc/apache2/ports.confの変更箇所

NameVirtualHost *:80

NameVirtualHost *:81

NameVirtualHost *:82

Listen 80

Listen 81

Listen 82

3. mod_proxy_balancerの有効化

デフォルトでは、mod_proxy_balancerモジュールがアクティブじゃなかったので、下記コマンドを実行して有効にしました。

$ a2enmod proxy_balancer

■その他

sites-available（mod-available）、sites-enabled(mod-enabled)の違いがよく分からなかったので調べました。availableの方には文字通り利用可能なリソースを配置して、enabledでアクティブにしたい設定、またはモジュール（availableの方にあるもの）にシンボリックリンクをはるらしいです。

■参考にしたサイト

1. mod_proxyについて

http://httpd.apache.org/docs/2.1/ja/mod/mod_proxy.html

2. mod_proxy_balancerについて

http://httpd.apache.org/docs/2.2/ja/mod/mod_proxy_balancer.html

3. available、enableの違いについて

http://www.linux.net-japan.info/install08.html

Google Translate APIが有料化されてた

最近気付いたのですが、Google Translate APIが有料化されました。昨年twitter上の英語のつぶやきを日本語に自動翻訳するというサイトを作ったのですが、それがうまく機能していないのに気付き調べてみると以下のとおりでした。

Google Translate API v2 is now available as a paid service only, and the number of requests your application can make per day is limited. As of December 1, 2011, Google Translate API v1 is no longer available; it was officially deprecated on May 26, 2011. These decisions were made due to the substantial economic burden caused by extensive abuse. For website translations, we encourage you to use the Google Website Translator gadget.

(http://code.google.com/intl/ja/apis/language/translate/overview.htmlより引用)

　何とも悲しい限りです。しかしサイトを作った労力は無駄にはならないはずです。RESTの概念やphpでxmlをパースする方法を勉強できたので。

読書「知的会話入門」

「知的会話入門」（樋口裕一）という本を読みました。最近小説を読んでいて、その人の人柄・性格・頭の良さ・年齢などは発する言葉からも伝わってくるものだなと思い、自分の会話力の低さに愕然としたのがこの本を買ったきっかけです。会話において発言する際、大切なのはボキャブラリー・レトリック・それからこの本で述べられている教養だなと思います。

　この本の前半部では、知的会話のtipsが述べられています。後半部では、教養の付け方について書かれています。ここでは前半部で紹介されたテクニックの一部（※多少私自信の拡大解釈があるかもしれません。）をまとめておきます。

1. 分からない言葉を聞く場合

「○○の正確な意味って何でしたっけ？」、「○○の厳密な定義って何でしたっけ？」と聞くとよいです。過去形にすることで、あたかも昔知っていたけど忘れてしまって・・という感じがでます。「○○って何でしたっけ？」ではなく”正確な”意味、”厳密な”定義という聞き方をしているのがポイントです。

2. 質問に対する適切な回答が思いつかない場合

「分かりません。」の後に、「じっくりと考えてみる必要があります。」というと、じっくり考える思慮深い人だなという印象を与えることができます。

3. 相手の意見を否定する場合

「おもしろい意見ですね、しかし○○という考え方もありますが、どう思いますか？」と聞く。独善的に否定するのではなく、反対の意見を質問でぶつけてあげると、相手も悪い気はしないですし、この会話にもつながります。

4. あるものの良さが分からなかった場合

「今日の映画おもしろくなかったね。」というと、もし相手が面白いと感じていたときにとても不快な思いをさせてしまいます。「○○のよさは私には理解できなかったんだけど、あなたはどう思った？」とあくまでも”私には”面白さが伝わらなかった。というふうに言うといいです。ここでも質問で相手の意見を聞くという姿勢が大事です。相手と自分の感じ方の違いを会話で楽しむわけです。

5. あるものがとても良かった場合

「いやーよかった。分かる人には分かるんだよ。このよさが分からないやつなんてダメだ。」と妙に自分が違いが分かる人間であるように言う人がいますが、これはNG。「私にはとても興味深く感じられた。あなたはどうだった？」と聞きましょう。具体的にどこがよかったのか数点挙げてやると会話の幅が広がるでしょう。

　と、私が特に印象に残った使いそうなテクニックをあげてみました。他にも有効なテクニックが複数個挙げられているので、詳しく知りたい人は本を買いましょう。

SRM528 DIV2 1000 Mosquitoes

直線状を移動する複数の蚊を効率的に殺す方法を考えるゲーム。

　時間がfixなら、端点のパターンをすべて試して最適なのを選ぶだけ。時間を選ぶのが難しいが、最適解において、ある２匹の蚊の距離は2Rになっていると仮定してよい。もし最適解において両端の蚊の距離が2R未満だったとしても、時間の経過とともに蚊は拡散していくのであるポイントで両端の蚊の距離は2Rになるからである。拡散しない場合（相対速度が一定）場合は、t=0のときに計算しているのでOK。

　自力では全く解けませんでした。蚊が時間の経過とともにある部分に密集していき、そのあとは拡散していくというようなイメージは浮かんだので、三分探索みたいなことをするのかなーと思ったら全く違った。この問題のように、”ある区間内とかある範囲内に何かを収めたい”というような問題の場合は、同じような思考が使える場合がよくあると思う。（四角形の中にあると言われたら、少なくとも2つの点は辺に接していると仮定していいとか。）最適解があって、そこから最適性を崩すことなく解を上手く動かすことで最適解にある仮定を設定することができ効率的な探索ができる、という考え方はしっかり身に付けたい。

view plainprint?

1. const double EPS = 1e-9;  
2. class Mosquitoes {  
3. public:  
4.     int getMaximum(vector<int> xInit, vector<int> v, int R) {  
5.         int N = xInit.size();  
6.         int ret = 0;  
7.         vector<double> pos(N);  
8.   
9.         // t = 0  
10.         REP(i, N) pos[i] = xInit[i];  
11.         sort(ALL(pos));  
12.         REP(p, N) FOR (q, p, N) {  
13.             if (pos[q] - pos[p] <= 2*R+EPS)  
14.                 ret = max(ret, q-p+1);  
15.         }  
16.   
17.         REP(i, N) REP(j, N) if (i != j){  
18.             if (v[i] == v[j]) continue;  
19.   
20.             // t = time when the distance between mosquito[i] and mosquito[j] = 2*R  
21.             double t = 1.0 * (xInit[i]-xInit[j]-2*R) / (v[j] - v[i]);  
22.             if (t < EPS) continue;  
23.   
24.             REP(k, N) pos[k] = xInit[k] + v[k] * t;  
25.             int cnt = 0;  
26.             REP(k, N) {  
27.                 if (pos[j] <= pos[k] + EPS && pos[k] <= pos[i] + EPS)  
28.                     ++cnt;  
29.             }  
30.             ret = max(ret, cnt);  
31.         }  
32.   
33.         return ret;  
34.     }  
35. };  

const double EPS = 1e-9;
class Mosquitoes {
public:
    int getMaximum(vector<int> xInit, vector<int> v, int R) {
        int N = xInit.size();
        int ret = 0;
        vector<double> pos(N);

        // t = 0
        REP(i, N) pos[i] = xInit[i];
        sort(ALL(pos));
        REP(p, N) FOR (q, p, N) {
            if (pos[q] - pos[p] <= 2*R+EPS)
                ret = max(ret, q-p+1);
        }

        REP(i, N) REP(j, N) if (i != j){
            if (v[i] == v[j]) continue;

            // t = time when the distance between mosquito[i] and mosquito[j] = 2*R
            double t = 1.0 * (xInit[i]-xInit[j]-2*R) / (v[j] - v[i]);
            if (t < EPS) continue;

            REP(k, N) pos[k] = xInit[k] + v[k] * t;
            int cnt = 0;
            REP(k, N) {
                if (pos[j] <= pos[k] + EPS && pos[k] <= pos[i] + EPS)
                    ++cnt;
            }
            ret = max(ret, cnt);
        }

        return ret;
    }
};

　

New Year's Resolutions 2012

A happy new year! -- a little late?? --

I just want to declare my new year's resolutions here:

1. Get a challenging job

2. Go to gym once a week

3. Be promoted to a yellow coder

4. Read one book a month

I'll go further from up to the bottom.

1. I want to tackle on more challenging tasks, which I've hoped for a couple of years. Just like Steve said, "your work takes up most of your life." I have to search more interesting, challenging, thrilling tasks than my hobby: programming competitions.

2. My parents and my younger brother are kind of obese. It's very likely that I'm going to be fatter. This is a dangerous situation I have to avoid with all my efforts. Got to lower my weight to around 55 kg this year. Plus, exercises are good to your heath and brain :)

3. I've stayed tuned in "blue" for a long time, going up and down, up and down between the rating of 1400 and 1500. I know that to be a yellow coder, I have to be able to solve medium-level problems: not always, but one out of three.

4. I think I've somehow developed my math ability and logical thinking by competitive programming. "What I completely lack is knowledge," I noticed. I need more knowledge, that is, "what-is" knowledge, like vocabularies, histories, cultures, and latest news. I bet reading is a good place to start off.