Search on the blog

2012年10月31日水曜日

Codeforces Round #147 Build String

問題概要
文字列tとn個の文字列s1, s2, ...., snが与えられる。sを用いてtを作る。一回の操作で
  1. s1, s2, ...., snの中から任意の文字列を一つを選ぶ。
  2. 1.で選んだ文字列から任意の一文字を選び、紙に書く。
  3. 選んだ文字列から選んだ文字を消去する。
この操作を複数回行い、紙に書かれた文字列がtと等しくなるようにする。ただし、それぞれのsi, i = 1,2, ..., nについて使用できる回数が決まっている。i番目の文字列を使用するとコストがiかかる。tを作るために必要な最小コストを求めよ。


方針
最小費用流を使う。
乱択を使った解法でシステムテスト通過している人がいて、おもしろいなぁと思って同じようなことやってみたけど、以下のケースで落とせるじゃん。。ただ、この考え方は覚えておいて損は無さそうだ。
abcdefghijklmnopqrstuvwxyz        
26
abcdefghijklmnopqrstuvwxyz 1
abcdefghijklmnopqrstuvwxy  1
abcdefghijklmnopqrstuvwx   1
abcdefghijklmnopqrstuvw    1
abcdefghijklmnopqrstuv     1
abcdefghijklmnopqrstu      1
abcdefghijklmnopqrst       1
abcdefghijklmnopqrs        1
abcdefghijklmnopqr         1
abcdefghijklmnopq          1
abcdefghijklmnop           1
abcdefghijklmno            1
abcdefghijklmn             1
abcdefghijklm              1
abcdefghijkl               1
abcdefghijk                1
abcdefghij                 1
abcdefghi                  1
abcdefgh                   1
abcdefg                    1
abcdef                     1
abcde                      1
abcd                       1
abc                        1
ab                         1
a                          1


ソースコード
上が最小費用流を使った解法、下が乱択を使った解法。
using namespace std;

int V;
int main()
{
    string tar;
    int n;

    cin >> tar >> n;
    vector strs(n);
    vector caps(n);

    REP(i, n) 
        cin >> strs[i] >> caps[i];

    V = 1 + n + 26 + 1;
    REP (i, n) {
        add_edge(0, 1+i, caps[i], 0);
        REP (j, 26) {
            int cnt = count(strs[i].begin(), strs[i].end(), (char)(j+'a'));
            if (cnt)
                add_edge(1+i, 1+n+j, cnt, i+1);
        }
    }

    REP (i, 26) {
        int cnt = count(tar.begin(), tar.end(), (char)(i+'a'));
        if (cnt)
            add_edge(1+n+i, 1+n+26, cnt, 0);
    }

    cout << min_cost_flow(0, 1+n+26, tar.length()) << endl;

    return 0;
}

const int INF = 1<<30;
string tar;
int n;
vector strs;
vector caps;
vector pri;

int calc(vector &x, vector &y, char c) {
    REP (i, n) { 
        if (y[i] == 0) 
            continue;
        REP (j, x[i].length()) {
            if (x[i][j] == c) {
                x[i][j] = ' ';
                y[i]--;
                return i+1;
            }
        }
    }
    return INF;
}

int main() {
    cin >> tar >> n;
    strs.assign(n, "");
    caps.assign(n, 0);
    pri.assign(tar.length(), 0);

    REP(i, n)
        cin >> strs[i] >> caps[i];
    REP(i, tar.length())
        pri[i] = i;
    
    int ret = INF;
    while (clock() < 1.8*CLOCKS_PER_SEC) {
        random_shuffle(pri.begin(), pri.end());

        vector _strs = strs;
        vector _caps = caps;

        int total = 0;
        REP (k, tar.length()) {
            char c = tar[pri[k]];
            
            int cost = calc(_strs, _caps, c);
            if (cost == INF) {
                total = INF;
                break;
            } else {
                total += cost;
            }
        }
        ret = min(ret, total);
    }

    if (ret == INF) 
        cout << -1 << endl;
    else
        cout << ret << endl;

    return 0;
}

2012年10月30日火曜日

読書「ボッコちゃん」

星 新一の「ボッコちゃん」を読みました。50作のSF短篇小説が入っています。 個人的には鏡が一番おもしろかったです。

2012年10月27日土曜日

Codeforces Round #146 Let's Play Osu!

問題概要
Osuと呼ばれるゲームをする。連続するx個の○についてx2の得点が与えられる。 n文字の文字列が与えられるので、得点の期待値を求める。ただし、i番目の文字が○である確率はpiである。

方針
n2 = 2 * nC2 + n
という関係から以下のような問題の読み替えができる。
「連続する○について○の長さの2乗が加点される。」→ 「一つの○につき1点加点し、○のペアについて間に×が一つもなければ2点加点する。」
これを利用して期待値を計算する。後半のペアうんぬんのところは動的計画を使って計算する。

ソースコード
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

int main() {
    int n;
    static double p[100000];
    cin >> n;

    REP(i, n) scanf("%lf", p+i);

    double ret = 0;
    double q = 0;
    REP (i, n) {
        ret += p[i];
        if (i > 0)
            q = (q + p[i-1]) * p[i];
        ret += 2*q;
    }

    printf("%.8lf\n", ret);
    return 0;
}

Codeforces Round #141 Fractal Detector

問題概要
ある規則によって作成されるフラクタルが、与えられた平面上にいくつかるか数える。

方針
フラクタルかどうかは分割統治で判定できる。メモ化して高速化する。実装ややこしそうと思ったけど、以外と簡単に書けた。

ソースコード
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

string bd[512];
bool dp[1<<4][10][512][512];
int r, c;

int main() {
    cin >> r >> c;

    REP (i, r) cin >> bd[i];
    
    // base case
    for (int i = 0; i + 1 < r; i++) {
        for (int j = 0; j + 1 < c; j++) {
            int mask = 0;
            mask |= (bd[i][j] == '*');
            mask <<= 1;
            mask |= (bd[i][j+1] == '*');
            mask <<= 1;
            mask |= (bd[i+1][j] == '*');
            mask <<= 1;
            mask |= (bd[i+1][j+1] == '*');
            dp[mask][1][i][j] = true;
        }
    }

    int size = 2;
    for (int k = 2; k < 10; k++) {
        size *= 2;
        for (int i = 0; i + size - 1 < r; i++) {
            for (int j = 0; j + size - 1 < c; j++) {
                for (int p = 0; p < 16; p++) {
                    dp[p][k][i][j] = true;
                    for (int q = 0; q < 4; q++) {
                        int x = i;
                        int y = j;

                        if ((q & 1) == 0) y += size / 2;
                        if (q / 2 == 0) x += size / 2;

                        if (p & 1 << q)
                            dp[p][k][i][j] &= dp[15][k-1][x][y];
                        else
                            dp[p][k][i][j] &= dp[p][k-1][x][y];
                    }
                }
            }
        }
    }

    int ret = 0;
    for (int i = 0; i < 512; i++)
        for (int j = 0; j < 512; j++)
            for (int p = 0; p < 16; p++)
                for (int q = 2; q < 10; q++)
                    ret += dp[p][q][i][j];

    cout << ret << endl;
    
    return 0;
}

2012年10月6日土曜日

読書「スティーブ・ジョブズ 驚異のプレゼン」

会社の人に勧められて読みました。以下のいずれかに当てはまる人は読んでおいた方がいいと思います。実践すれば誰でもプレゼンがうまくなるテクニックが盛り沢山です。
  • 営業職の人
  • 人に何かを教える職業に就いている人
  • 学会発表をする人
  • 面接を受ける人
  • スティーブ・ジョブズのスピーチを聞いて感動したことがある人


 

特に印象に残ったところだけ紹介します。

習得には1万時間が必要
どのようなことであれ、世界的な達人というレベルに熟達するには1万時間の練習が必要。1日3時間を10年続けること。

バケツ方式
尋ねられる可能性が高い質問をリストアップし、カテゴライズしておく。実際に質問されたら用意しておいたバケツにあてはまる回答をする。7種類バケツを用意しておけば十分。

なぜ気にかける必要があるか
なぜ気にかける必要があるのかを話す。自分自身にメリットがない話を聞きたいと思う人はいない。

2012年10月1日月曜日

サーバー奮闘記(24) SCPでファイル転送

sshの設定が以下のような場合、どのようにオプションを書けばいいかメモしておく。
  • 秘密鍵で認証(以下の例では秘密鍵は~/.ssh/id_rsaに格納されているとする。)
  • ポートはデフォルトの22番ではない(以下の例では1234番のポートを使用しているとする。)

リモートからローカルへファイル転送
scp -P1234 -i ~/.ssh/id_rsa user@host:source_file_path destination_file_path

ローカルからリモートへファイル転送
scp -P1234 -i ~/.ssh/id_rsa source_file_path user@host:destination_file_path