Google Code Jam Round1B

A, B の small, large を提出して 56 点 411 位で通過.
去年は Round1 で敗退したので, 今年は少し進歩したということか ?

A は問題文が長いので, 先に B を見る. B の small の方が点数が低い.
B は std::next_permutation 使う. 最後の順列だった場合は, ソートして先頭の文字と 0 でない最小の文字を入れ替えて, 一文字目に 0 を挿入する. 知っててよかった STL.

A は, 問題文から二分木作る問題. std::istream の文字切り出しを使いたいのだが, ) の前は空白がない場合があるとの説明書き. ) の前には空白を挿入して構文解析しました.

C は, 一つずつ式を増やしてクエリの数字と答え合わせするぐらいしか思いつかず. 後で作りましたが, small は通りましたが large は全然だめでした.

3 分割の Round1 で 400番台だと次の Round2 突破はかなり厳しい. 今年は楽しみますよ.

アルゴリズムイントロダクション ç« æœ«å•é¡Œ 15-7 利益最大化スケジュール

1 台の機械に n 個の仕事 a[1], a[2], ..., a[n] の仕事をさせます. 各仕事には処理時間 t[ j ], 利益 p[ j ], 納期 d[ j ] が与えられています. 機械は同時に二つ以上の仕事をすることはできないし, 途中で止めることもできません. 仕事 a[ j ] を納期までに完了すれば利益 d[ j ] が得られます. 納期を越えるとその仕事に対する利益は 0 になります.
利益を最大にしようとスケジュールし, その最大の利益を与えるプログラムを考えます.
ここでは, 1 <= n <= 1000, 1 <= max(d[ j ]) <= 1000 としておきます.

納期きっちりで終わらせる必要はありませんから, 納期の早い順に, そして仕事が納期を越えないように仕事を並べていったときの最大の利益を求めることを考えます. 納期の早い順に仕事をソートしておきます. ここでは a[1], a[2], ..., a[n] がすでに並び替えられていると考えることにします.

最大の納期を dmax, 時刻 t の時点で, 仕事 a[ j ] まで考慮したときの最大の利益を profit[ t ][ j ] とします. profit[ t ][ j ] は, a[j] の仕事をしたときの利益か, しなかったときの利益 (profit[ t-1 ][ j ] と profit[ t ][ j-1]) の中での最大値になります.
仕事 a[ j ] をするには, t[ j ] <= t でないといけません.
また, 納期を越えたら利益 0 ですから, d[ j ] >= t のときだけ, 仕事をする価値があります.

profit[t][j] = max( p[j]+profit[t-t[j]][j-1] if t[j] <=t and d[j] >= t,
                    profit[t-1][j],
                    profit[t][j-1] )

profit[0][k] = 0 (0 <= k <= n)
profit[k][0] = 0 (0 <= k <= dmax)

ソートで O(n*logn) かかり, 上記の漸化式を動的計画法で O(n*dmax) で計算しますから, 全体では O(n*dmax) のアルゴリズムとなります.

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

struct Job {
  int i,t,p,d;
  Job(int i, int t, int p, int d):i(i), t(t), p(p), d(d) {}
  bool operator<(const Job& job) const { return d < job.d; }  
};

int main() {
  int C;
  std::cin >> C;
  for(int c = 1; c <= C; ++c) {
    int n;
    std::cin >> n;
    std::vector<Job> jobs(n+1, Job(0,0,0,0));
    for(int i = 1; i <= n; ++i) {
      int t,p,d;
      std::cin >> t >> p >> d;
      jobs[i] = Job(i,t,p,d);
    }
    std::sort(jobs.begin()+1, jobs.end());

    int profit[1001][1001];
    memset(profit, 0, sizeof(profit));
    int tmax = jobs.back().d;
    for(int t = 1; t <= tmax; ++t) {
      for(int i = 1; i <= n; ++i) {
	int p = 0;
	if(jobs[i].d >= t && jobs[i].t <= t) {
	  p = jobs[i].p+profit[t-jobs[i].t][i-1];
	}
	p = std::max(p, profit[t-1][i]);
	p = std::max(p, profit[t][i-1]);
	profit[t][i] = p;
      }
    }
    std::cout << "Case #" << c << ": " << profit[tmax][n] << std::endl;
  }
}

Google Code Jam Qualification Round 2009: 予選会

去年に引き続き今年も参加しました. C の large を落としたので, 76 点.

A - Alien Language

正規表現で一撃で解けるようですが, そんなことには気づかない私は, 全パターンを探索して求める方法をとりました.

単純に全探索すると small ですら通らないので, 辞書のワードの全接頭語も辞書に追加して, 枝刈りする小手先の細工で, large も 49 秒で通りました.

全探索などしなくても, パターンが簡単なので, 辞書のワードそれぞれに対して, 一文字づつ照合すればよいだけだったのでした.

#include <iostream>
#include <vector>

int main() {
  size_t L, D, N;
  std::cin >> L >> D >> N;
  std::vector<std::string> dic(D, std::string());
  for(size_t i = 0; i < D; ++i) {
    std::cin >> dic[i];
  }
  for(size_t i = 1; i <= N; ++i) {
    std::string pattern;
    std::cin >> pattern;
    std::vector<std::string> pv;
    for(size_t index = 0; index < pattern.size();) {
      if('(' == pattern[index]) {
	std::string::size_type endparen = pattern.find(")", index);
	pv.push_back(pattern.substr(index+1, endparen-index-1));
	index = endparen+1;
      } else {
	pv.push_back(pattern.substr(index,1));
	++index;
      }
    }
    
    int total = 0;
    for(size_t d = 0; d < D; ++d) {
      const std::string& word = dic[d];
      bool found = true;
      for(size_t i = 0; i < word.size(); ++i) {
	if(pv[i].find(word[i]) == std::string::npos) {
	  found = false;
	  break;
	}
      }
      if(found) {
	++total;
      }
    }
    std::cout << "Case #" << i << ": " << total << std::endl;
  }
}

アルファベット小文字に限定されているので, 'a' がパターンにあるなら, 1 ビット目をセット, 'b' があるなら, 2 ビット目をセットと言う風にビットパターンにして, 照合をビット演算にすると速く解けます. i 番めの文字パターン列 p[i] をビットパターンにすると

int bitpattern[i] = 0;
for(size_t k = 0; k < p[i].size(); ++k) {
  bitpattern[i] |= 1 << (p[i][k]-'a');
}

辞書内のワード W と照合するには, W[i]&bitpattern[i] が 0 なら照合失敗, 1 なら次の文字の照合に進みます.

#include <iostream>
#include <vector>

int main() {
  size_t L, D, N;
  std::cin >> L >> D >> N;
  std::vector<std::string> dic(D, std::string());
  for(size_t i = 0; i < D; ++i) {
    std::cin >> dic[i];
  }
  for(size_t i = 1; i <= N; ++i) {
    std::string pattern;
    std::cin >> pattern;
    std::vector<unsigned int> pv;
    for(size_t index = 0; index < pattern.size();) {
      if('(' == pattern[index]) {
	std::string::size_type endparen = pattern.find(")", index);
	std::string p = pattern.substr(index+1, endparen-index-1);
	unsigned int x = 0;
	for(size_t k = 0; k < p.size(); ++k) {
	  x |= 1 << (p[k]-'a');
	}
	pv.push_back(x);
	index = endparen+1;
      } else {
	pv.push_back(1 << (pattern[index]-'a'));
	++index;
      }
    }
    
    int total = 0;
    for(size_t d = 0; d < D; ++d) {
      const std::string& word = dic[d];
      bool found = true;
      for(size_t i = 0; i < word.size(); ++i) {
	if(!(pv[i] & (1 << (word[i]-'a')))) {
	  found = false;
	  break;
	}
      }
      if(found) {
	++total;
      }
    }
    std::cout << "Case #" << i << ": " << total << std::endl;
  }
}

B - Watersheds

私にとってはこれが一番簡単でした. 問題読むのが面倒でしたが. 'drainage basins' ってなんぞや, って感じで.

左上のマスから順に, すべてのマスを舐めて, 流れる方向を決めていきます.
次に, すでにラベル付けされているマスはスキップしながら, 左上のマスから順に, 流れる方向をたどって, sink を探します. そして, sink から流れを逆順に辿って, ラベル付けします. 最後にラベルを更新します.

C - Welcome to Code Jam

提出したものは, 再帰で解いたもので, 文章の位置と "welcome to .." の位置のペアをキーにして, その時点での個数をメモしました. 残念ながら large が失敗していました.

ここでは表を用いて解いてみます. T を文章, W を "welcome to code jam" とします.
t を T の長さ, w を W の長さをします.
C[ i ][ j ] を W[ i ], T[ j ] まで見たときの場合の数とします.
W[ i ] == T[ j ] の時, C[ i-1 ][ j-1 ] だけ, 場合の数が増えることになります.
W[ i ] != T[ j ] の時は, 場合の数は増えないので, C[ i ][ j-1 ] までの場合の数と同じになります. これを漸化式にすると,

C[i][j] = C[i][j-1]+C[i-1][j-1] if W[i] == T[j]
          C[i][j-1]             if W[i] != T[j]

i = 0 のときに W[ i ] == T[ j ] となったら, 場合の数が 1 増えるので,

C[0][j] = 1, 0 <= j <= t
C[i][0] = 0, 0 <= i <= w

としておきます. これでプログラムが簡単になります.

あとは, O(W*T) の時間をかけて, C[ w ][ t ] を計算します. C[ w ][ t ] が答えです.

#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

int main() {
  const std::string W = "welcome to code jam";
  int N;
  std::cin >> N;
  std::string line;
  getline(std::cin, line);
  for(int n = 1; n <= N; ++n) {
    std::string T;
    getline(std::cin, T);

    int C[20][501];

    memset(C, 0, sizeof(C));
    std::fill(&C[0][0], &C[0][501], 1);

    for(size_t i = 1; i <= W.size(); ++i) {
      for(size_t j = 1; j <= T.size(); ++j) {
	C[i][j] = C[i][j-1];
	if(W[i-1] == T[j-1]) {
	  C[i][j] += C[i-1][j-1];
	}
	C[i][j] %= 10000;
      }
    }
    std::cout << "Case #" << n << ": " << std::setfill('0')
	      << std::setw(4) << C[W.size()][T.size()] << std::endl;
  }
}

これが本番にできればよいのですね. 眠いとか深夜とか明日早いとかいろいろ言い訳はできるんですが.

アルゴリズムイントロダクション ç« æœ«å•é¡Œ 15-2 プリンタによる浄書

入力文章は文字数が l1, l2, ..., ln の n 個の単語の列です.
この文章を 1 行最大 M 文字の行に印字したいとします.
同じ行の単語と単語の間には空白が一つ入ります.
最終行を除く, 各行の行端の空白の三乗和を最小にするように印字するアルゴリズムを考えよ,
という問題です.

問題文にもあるように動的計画法にて解くことを考えます.
ここでは行端の空白の三乗和の最小値を出力するプログラムを作成しました.
S[i,j] を単語 i から単語 j を使ったときの行端の空白の三乗和であるとします.
求めるものは, S[1,n] になります. 単語 i から j の長さの和を sumw(i,j)とすると,
S[i,j] は, M-j+i-sumw(i,j)の三乗(1), S[i,k]+S[k+1,j], i <= k <= j-1 のうちの最小値となります.
(1) では, 単語 i から j が一行に収まらない場合は, 負の値になるのでこの場合は,
この値を最小値とすることはできませんので無視します. また, 負ではない場合で, j == n の場合,
これは最終行なので 0 となり, 自動的に最小値になります.
この計算は, 下のプログラムの cost 関数にて行っています. 単語 i から j が収まらない場合は
十分に大きな値を返しておけばよいので, INT_MAX を返しています

S[i,i] 1 <= i < n については, (1) の式にて計算できます.S[n,n] は最終行なので 0 になります.

for の 3 重ループでそれぞれの添字はたかだか n 個の値をとるので実行時間は O(n^3) になります.

#include <limits.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

int S[1001][1001];
int M;
int n;

int cost(const std::vector<int>& wlv, int first, int last)
{
  int c = M-last+first-std::accumulate(wlv.begin()+first, wlv.begin()+last+1, 0);
  if(c < 0) {
    return INT_MAX;
  } else if(last == n) {
    return 0;
  } else {
    return c*c*c;
  }
}

int main() {
  int C;
  std::cin >> C;
  for(int c = 1; c <= C; ++c) {
    std::cin >> M;
    std::cin >> n;
    std::vector<int> wlv(n+1, 0);
    for(int i = 1; i <= n; ++i) {
      std::cin >> wlv[i];
    }
    
    memset(S, 0, sizeof(S));
    for(int i = 1; i < n; ++i) {
      S[i][i] = cost(wlv, i, i);
    }
    for(int l = 2; l <= n; ++l) {
      for(int i = 1; i <= n-l+1; ++i) {
	int j = i+l-1;
	int c = cost(wlv, i, j);
	if(c > 0) {
	  for(int k = i; k <= j-1; ++k) {
	    c = std::min(c, S[i][k]+S[k+1][j]);
	  }
	}
	S[i][j] = c;
      }
    }
    std::cout << "Case #" << c << ": " << S[1][n] << std::endl;
  }
}

サンプル入力

2
10
10 3 5 9 2 3 2 2 1 4 5
6
2 3 3

サンプル出力

Case #1: 4
Case #2: 27

このブログ

なんかつながるのがいつも遅い. Twitter が快適すぎなのか.

EVONY の AD

なんとかならんか, これ

Alien Numbers を解いてみる

http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtcg4LEghjb250ZXN0cxh5DA#s=p0

Alien Numbers を解いてみる.
戦略は, Alien Number を 10 進にしてから, ターゲットの基数に直す.

import sys

C=int(sys.stdin.readline().strip())
for c in range(C):
    line=sys.stdin.readline().strip()
    alienNumber, source, target=line.split(" ")
    
    sbase=len(source)
    tbase=len(target)

    decnum=0
    for i in range(len(alienNumber)):
        decnum*=sbase
        decnum+=source.find(alienNumber[i])

    result=[]
    while decnum > 0:
        result.append(target[decnum%tbase])
        decnum/=tbase
    result.reverse()
    print "Case #%d: %s"%(c+1, "".join(result))