Search on the blog

2013年5月25日土曜日

知ってると便利なSTL(11) partial_sum

その名のとおりpartial sumを計算してくれる関数です。
以下の処理と同様のことをしてくれます。
template <class InputIterator, class OutputIterator>
   OutputIterator partial_sum ( InputIterator first, InputIterator last,
                                OutputIterator result )
{
  iterator_traits<InputIterator>::value_type val;
  *result++ = val = *first++;
  while (first!=last)
    *result++ = val = val + *first++;
  return result;
}

これは便利。
#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int x[] = {0,1,2,3,4,5,6,7,8,9,10};
    int y[11];
    
    partial_sum(x, x+11, y);

    for (int i = 0; i < 11; i++)
        cout << y[i] << " ";
    cout << endl;

    return 0;
}
のように書くと、
0 1 3 6 10 15 21 28 36 45 55
のように出力されます。

月間PV10,000達成

 月間PVが初めて10,000を越えました。ブログを読んでくれた皆さん、ありがとうございました。

何の実用性もないおれおれ系ブログですが、これからも自分の好きなことを書きつづけていきたいと思います。


2013年5月18日土曜日

Google Code Jam 2013 Round1C The Great Wall

 本番はwordyなproblem statementに翻弄されてパニクった結果、smallしか解けませんでしたが、落ち着いて考えるとただの一次元の座標圧縮 + セグメント木でした。

 sampleにあるように端点はdiscreteだけど区間内に含まれる値はcontinuousというのがいやらしい感じですが、[a, b]を攻める => [a, b)を攻めると読み替えてもOKと気づくと素直に実装できます。本番中はこれに気づかず、0.5刻みの区間を整数の区間にマッピングして解くという無駄なことをしていました。

 あと、要素数が10^6くらいになるので、set/map(unordered_set/unordered_mapなら大丈夫だと思います。)ではなくvectorを使って処理しています。

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++)  

struct attack {
    int d;   // day
    int w;   // westmost
    int e;   // eastmost
    int s;   // strength

    attack(int d, int w, int e, int s) : d(d), w(w), e(e), s(s) {}
    
    bool operator<(const attack &x) const {
        return d < x.d;
    }
};

int seg[1<<22];

void init() {
    memset(seg, 0, sizeof(seg));
}

void update(int k, int l, int r, int a, int b, int x) {
    if (b <= l || r <= a)
        return;
    if (a <= l && r <= b)
        seg[k] = max(seg[k], x);
    else {
        int mid = (l + r) / 2;
        update(2*k+1, l, mid, a, b, x);
        update(2*k+2, mid, r, a, b, x);
        seg[k] = max(seg[k], min(seg[2*k+1], seg[2*k+2]));
    }
}

const int oo = 1<<30;
int query(int k, int l, int r, int a, int b) {
    if (b <= l || r <= a)
        return oo;
    if (a <= l && r <= b)
        return seg[k];
    else {
        int mid = (l + r) / 2;
        int x1 = query(2*k+1, l, mid, a, b);
        int x2 = query(2*k+2, mid, r, a, b);

        return max(seg[k], min(x1, x2));
    }
}

void solve() {
    int N;
    cin >> N;

    vector<int> pos;
    vector<attack> attacks;

    // read input data
    REP (i, N) {
        int di, ni, wi, ei, si, delta_di, delta_pi, delta_si;
        cin >> di >> ni >> wi >> ei >> si >> delta_di >> delta_pi >> delta_si;

        REP (j, ni) {
            attacks.push_back(attack(di, wi, ei, si));
            pos.push_back(wi);
            pos.push_back(ei);
            di += delta_di; wi += delta_pi; ei += delta_pi; si += delta_si;
        }
    }

    // axis compression
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    int L = pos.size();
    int M = attacks.size();
    REP (i, M) {
        attacks[i].w = lower_bound(pos.begin(), pos.end(), attacks[i].w) - pos.begin();
        attacks[i].e = lower_bound(pos.begin(), pos.end(), attacks[i].e) - pos.begin();
    }
    
    // simulate attacks
    sort(attacks.begin(), attacks.end());
    init();
    int cnt = 0;
    REP (i, M) {
        int j;

        // attack
        for(j = i; j < M && attacks[j].d == attacks[i].d; j++)
            if (query(0, 0, L, attacks[j].w, attacks[j].e) < attacks[j].s)
                ++cnt;

        // build the Wall
        for(j = i; j < M && attacks[j].d == attacks[i].d; j++)
            update(0, 0, L, attacks[j].w, attacks[j].e, attacks[j].s);

        i = --j;
    }

    cout << cnt << endl;
}

int main() {
    int T;
    cin >> T;

    REP (i, T) {
        printf("Case #%d: ", i+1);
        solve();
    }
    return 0;
}

読書「人間失格」

 太宰治の人間失格を読みました。

作中で、主人公が友人と言葉遊びをします。
その中で、「罪」のantonymは何か?という問いがされます。
その答えによって、その人のすべてが分かると主人公は言いますが、結局その場面では答えにたどり着くことは出来ません。

「罪」のantonymは、「死」ではないかと思います。
「生きていくことは罪なのか?」と主人公が自問する場面があります。「生きること」 = 「罪」であれば、罪のantonymは「死」です。
そして作者は自身の人生で罪とは正反対の決断をしました。この作品が太宰治の遺書だとすると、それが答えなのではないでしょうか。


2013年5月15日水曜日

知ってると便利なC++のstringテクニック

charからstringへの変換
みなさんどうやってますか?

僕はよく以下のように書きます。(ここでは、char型のcをstring型のsに変換したいとします。)
#include <iostream>

using namespace std;

int main() {

    char c = 'a';
    string s;
    s += c;

    return 0;
}

以下のように書く人をよく見かけますが、これは無駄にソース量が多いのではと思います。
#include <iostream>
#include <sstream>

using namespace std;

int main() {

    char c = 'a';
    string s;
    stringstream ss;

    ss << c;
    ss  >> s;

    return 0;
}

ちょっと考えてみましたが、下のように書くのが一番いいのでは。
#include <iostream>

using namespace std;

int main() {

    char c = 'a';
    string s(1, c);

    return 0;
}


母音判定
普通に書くとこうなります。
#include <iostream>

using namespace std;

int main() {

    char c = 'a';

    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

    return 0;
}

ifの中が多くて面倒くさいです。以下のように書くとスマートになります。

#include <iostream>

using namespace std;

int main() {

    char c = 'a';

    if (~string("aeiou").find(c))
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

    return 0;
}

少し長くなってしまいますが、以下のような書き方もあります。

#include <iostream>

using namespace std;

int main() {

    char c = 'a';

    if (~string(1, c).find_first_of("aeiou"))
        cout << "vowel" << endl;
    else
        cout << "consonant" << endl;

    return 0;
}

2013年5月14日火曜日

George Orwellでも読んでみようかしら。。

George Orwellの「Animal Farm」と「1984」を買った。


「Animal Farm」はlang-8で進められたから。「1984」は「1Q84」つながりで。

しかしKindleの書籍は安いなー。

「Animal Farm」は紙だと943円なのが100円。

「1984」は紙だと1046円なのが100円。



2013年5月9日木曜日

Code Jam 2013 Round 1B Garbled Email

 前回復習したときに単純なDP解で解けたけど、上位陣の解答がおもしろそうだったのでrngさんのソースを見てみた。

あらかじめ辞書の単語でトライ木を作っておいて、(トライ木のどの節点にいるのか、間違った文字からの距離) -> 異なる文字の数をマップにいれて、それを毎回更新していくという処理をしている。

とりあえず一回写経して理解した後で、同じ解法を何も見ずに自分のスタイルで書いてみるという練習をしてみた。

最近きれいなソースを写経したり、どういうことを考えて実装されたソースなのかを考えたりするのが楽しくなってきた。これは良い練習方法かもしれない。

#include <algorithm>
#include <iostream>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>

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++)  

struct node {
    int next[26];
};

int ptr;

node trie[3000000];
bool goal[3000000];

void update(const string &s) {
    int cur = 0;
    REP (i, s.length()) {
        int c = s[i] - 'a';
        if (trie[cur].next[c] == -1)
            trie[cur].next[c] = ptr++;
        cur = trie[cur].next[c];
    }

    goal[cur] = true;
}

#include <fstream>
void init() {
    ptr = 1;
    memset(trie, -1, sizeof(trie));
    memset(goal, 0, sizeof(goal));

    fstream file("garbled_email_dictionary.txt");
    string s;
    int cnt = 0;
    while (file >> s) {
        update(s);
        ++cnt;
    }
    
    cerr << "dictionary size: " << cnt << endl;
}

void solve() {
    string s;
    cin >> s;
    int N = s.length();

    map<pair<int, int>, int> dp[4010];
    dp[0][make_pair(0, 4)] = 0;

    REP (i, N) {
        EACH (j, dp[i]) {
            REP (k, 26) {
                int st = j->first.first;
                int dist = j->first.second;
                int val = j->second;
                
                st = trie[st].next[k];
                if (st == -1)
                    continue;

                if (s[i] - 'a' == k) {
                    dist = min(dist+1, 4);
                } else {
                    if (dist < 4)
                        continue;
                    dist = 0;
                    ++val;
                }

                pair<int, int> p(st, dist);
                if (dp[i+1].find(p) == dp[i+1].end() || dp[i+1][p] > val)
                    dp[i+1][p] = val;
                if (goal[st]) {
                    p.first = 0;
                    if (dp[i+1].find(p) == dp[i+1].end() || dp[i+1][p] > val)
                        dp[i+1][p] = val;
                }
            }
        }
        dp[i].clear();
    }

    int ret = 1<<30;
    REP (i, 5) {
        pair<int, int> p(0, i);
        if (dp[N].find(p) != dp[N].end())
            ret = min(ret, dp[N][p]);
    }
    cout << ret << endl;
}

int main() {
    init();
    int T;
    cin >> T;
    REP (i, T) {
        printf("Case #%d: ", i+1);
        solve();
    }

    return 0;
}

2013年5月5日日曜日

Google Code Jam 2013 Round1B

 Round 1Bがありました。A small、A large、C-smallを解くことができましたが、Round 2には届きませんでした。C-largeはあと1分あれば間に合ったのに、・・・。惜しかった。

ということで、復習しました。最近Javaを練習中なので、Javaで書きます。

A. Osmos
本番はDPでときましたが、Greedyで解けるようです。moteのサイズを昇順にソートした列をxとします。x[i]をremoveして、x[i+1]を吸収できるようにいくつかのmoteを追加するというのは意味がありません。x[i+1]を吸収できるようにしたのなら、x[i]も吸収できるからです。
ということで最適解は、「あるiまでは吸収して、i+1以降はremoveする。」という条件が成り立っているはずです。このiをループで回してあげればOKです。
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class A {
 Scanner sc = new Scanner(System.in);

 void solve() {
  int A = sc.nextInt();
  int N = sc.nextInt();
  
  int[] x = new int[N];
  for (int i = 0; i < N; i++)
   x[i] = sc.nextInt();
  
  sort(x);
  
  int ret = Integer.MAX_VALUE;
  for (int i = 0; i <= N; i++) {
   int tmp = N - i;
   
   int sz = A;
   for (int j = 0; j < i; j++) {
    if (sz < 2) {
     tmp = Integer.MAX_VALUE;
     break;
    }
    while (x[j] >= sz) {
     sz = 2 * sz - 1;
     ++tmp;
    }
    sz += x[j];
   }
   
   ret = min(ret, tmp);
  }
  
  System.out.println(ret);
   
 }

 void run() {
  int T = sc.nextInt();
  for (int id = 1; id <= T; id++) {
   System.out.printf("Case #%d: ", id);
   System.err.printf("Solving Case #%d...\n", id);
   solve();
   System.out.flush();
  }
 }

 void debug(Object... os) {
  System.err.println(deepToString(os));
 }

 public static void main(String[] args) {
  new A().run();
 }
}


B. Falling Diamonds
これは本番中はまったく解けませんでした。ダイヤが積もっていくときに層ができますが、何番目の層にあたるのかというのが「原点からのマンハッタン距離 / 2」で計算できます。これで、自分が買おうとしている土地が何層目にあるかわかります。
あとはダイヤを層ごとに積み上げていって、目的のダイヤの層を被うことができれば1.0を返し、その層まで届かなければ0.0を返します。目的の層をすべて被うことはできないけど、途中まで被うことができる場合は、DPで(左、右)に(i, j)個ずつ積もっている確率を計算してあげます。
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class B {
 Scanner sc = new Scanner(System.in);

 double solve() {
  int n = sc.nextInt();
  int x = sc.nextInt();
  int y = sc.nextInt();
  
  int m = (abs(x) + abs(y)) / 2;  
  int l = 0;
  int cnt = 1;
  while (n - cnt >= 0) {
   n -= cnt;
   ++l; 
   cnt += 4;
  }
  
  if (m < l) 
   return 1.0;
  if (m > l)
   return 0.0;
  
  double[][] dp = new double[2][5000];
  dp[0][0] = 1.0;
  
  for (int i = 0; i < n; i++) {
   int cur = i&1;
   int nxt = i+1&1;
   
   fill(dp[nxt], 0.0);
   for (int j = 0; j <= i; j++) {
    if (j+1 >= 2*l+1)
     dp[nxt][j] += dp[cur][j];
    else if (i-j+1 >= 2*l+1)
     dp[nxt][j+1] += dp[cur][j];
    else {
     dp[nxt][j+1] += 0.5 * dp[cur][j];
     dp[nxt][j] += 0.5 * dp[cur][j];
    }
   }
  }
  
  double ret = 0;
  for (int i = y+1; i <= n; i++)
   ret += dp[n&1][i];
  
  return ret;
 }

 void run() {
  int T = sc.nextInt();
  for (int id = 1; id <= T; id++) {
   System.out.printf("Case #%d: ", id);
   System.err.printf("Solving Case #%d...\n", id);
   System.out.printf("%.8f\n", solve());
   System.out.flush();
  }
 }

 void debug(Object... os) {
  System.err.println(deepToString(os));
 }

 public static void main(String[] args) {
  new B().run();
 }
}


C. Garbled Email
本番中はDPを使いました。dp[i][j] = (i番目の文字に注目している、直近でミスマッチが起こった場所はj)としていました。これだと9分くらいかかってしまってTLE。
状態数の定義を変更して、dp[i][j] = (i番目の文字に注目している、直近でミスマッチが起こった場所はiよりj+1個前)としてみました。ただし、jが4のときとjが5以上の時は状態としては同じなのでこれをdp[i][4]にまとめました。これで、7分30秒くらい。
さらに、ループの順番を入れ替えてネストを1段浅くして、3分くらいで解けるようになったのが下のコード。
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class C {
 Scanner sc = new Scanner(System.in);
 Scanner dictionary;
 String[] words = new String[521196];
 static final int oo = 1 << 28;

 void init() {
  try {

   dictionary = new Scanner(new File("garbled_email_dictionary.txt"));
   for (int i = 0; i < words.length; i++)
    words[i] = dictionary.next();

   debug(words[0]);
   debug(words[words.length - 1]);

  } catch (FileNotFoundException e) {
   e.printStackTrace();
  }
 }

 void solve() {
  String s = sc.next();

  int[][] dp = new int[s.length() + 1][5];
  for (int i = 0; i < s.length() + 1; i++)
   for (int j = 0; j < 5; j++)
    dp[i][j] = oo;

  dp[0][4] = 0;

  for (int i = 0; i < s.length(); i++) {
   for (int k = 0; k < words.length; k++) {
    String w = words[k];
    if (i + w.length() > s.length())
     continue;

    int cnt = 0;
    int tail = -oo;
    int st = 0;
    for (int l = 0; l < w.length(); l++) {
     if (s.charAt(i + l) != w.charAt(l)) {
      ++cnt;
      if (tail == -oo)
       st = max(0, 4 - l);
      
      if (i + l - tail < 5) {
       cnt = oo;
       break;
      }
      tail = i + l;
     }
    }
    if (cnt < oo) {
     for (int j = st; j < 5; j++) {
      int nwTail = (tail == -oo) ? (i - j - 1) : tail;
      nwTail = min(4, i + w.length() - 1 - nwTail);
      dp[i + w.length()][nwTail] = min(dp[i + w.length()][nwTail],
        dp[i][j] + cnt);      
     }
    }
   }
  }

  int ret = oo;
  for (int i = 0; i < 5; i++)
   ret = min(ret, dp[s.length()][i]);

  System.out.println(ret);

 }

 void run() {
  init();
  int T = sc.nextInt();

  for (int id = 1; id <= T; id++) {
   System.out.printf("Case #%d: ", id);
   System.err.printf("Solving Case #%d...\n", id);
   solve();
   System.out.flush();
  }
 }

 void debug(Object... os) {
  System.err.println(deepToString(os));
 }

 public static void main(String[] args) {
  new C().run();
 }
}