Close Menu Navigation
Open Categories Menu Google Code Jam Qualification Round 2009 (4)
- 4 9月, 2009 -
- Google Code Jam, プログラミング, 就職活動 -
- Tags :
- 2 Comments
C問題：Welcome to Code Jam
Problem
So you’ve registered. We sent you a welcoming email, to welcome you to code jam. But it’s possible that you still don’t feel welcomed to code jam. That’s why we decided to name a problem “welcome to code jam.” After solving this problem, we hope that you’ll feel very welcome. Very welcome, that is, to code jam.
If you read the previous paragraph, you’re probably wondering why it’s there. But if you read it very carefully, you might notice that we have written the words “welcome to code jam” several times: 400263727 times in total. After all, it’s easy to look through the paragraph and find a ‘w’; then find an ‘e’ later in the paragraph; then find an ‘l’ after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase “welcome to code jam”.
To be more precise, given a text string, you are to determine how many times the string “welcome to code jam” appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], …, input[s[18]] is the string “welcome to code jam”.
The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.
Input
The first line of input gives the number of test cases, N. The next N lines of input contain one test case each. Each test case is a single line of text, containing only lower-case letters and spaces. No line will start with a space, and no line will end with a space.
Output
For each test case, “Case #x: dddd”, where x is the case number, and dddd is the last four digits of the answer. If the answer has fewer than 4 digits, please add zeroes at the front of your answer to make it exactly 4 digits long.
Limits
1 ≤ N ≤ 100
Small dataset
Each line will be no longer than 30 characters.
Large dataset
Each line will be no longer than 500 characters.
Sample
Input
3
elcomew elcome to code jam
wweellccoommee to code qps jam
welcome to codejam
Output
Case #1: 0001
Case #2: 0256
Case #3: 0000
コメント
最初の3が3行分という意味。各々の行から”welcome to code jam”を何パターン作れるか？という問題。最初の入力ではelcomewのwまでは出番がない。あとはスペースの位置とかおかしいけど、そのままの並びになっているから1通り。
次が面倒くさい。wweellccoommeeと重なっているだけだから計算するのは簡単で、wが2つ、eが2つ・・・・codeの部分はcが1つ、oが1つ・・・・スペースが2つ、あとは1つずつということで、2 x 2 x 2 x ….. x 2 = 256通り。なんだけど、綺麗に並んでいなかったら面倒くさいなと思って再帰でごりごり書くことに。
問題を見ていて、正規表現とかオートマトン（何とかを受理する言語のクラスとか聞いた記憶が）っぽいなあと思ったけど、正規表現ライブラリでどうにかなる感じはしなかった。正規表現の実装したことのある人なら楽勝なんだろうなあと思ったが、やったことがないのだから仕方がない。
ばっちぃコード
#include ＜stdio.h>
#include ＜stdlib.h>
#include ＜string>
//#define DEBUG
#ifdef DEBUG
#endif
using namespace std;
const string welcome = "welcome to code jam";
int answer;
void recursive( string s, int index )
{
if( welcome.length() <= index )
{
#ifdef DEBUG
puts("end of recursive");
#endif
answer++;
return;
}
#ifdef DEBUG
printf("recursive : \"%s\", index = %d\n", s.c_str(), index );
#endif
while(true)
{
char c = welcome[index];
#ifdef DEBUG
printf("looking for %c\n", c);
#endif
int pos = s.find(c);
if( pos != string::npos )
{
recursive( s.substr( pos + 1 ), index + 1 );
s[pos] = '*';
}
else
{
break;
}
}
}
int main()
{
FILE *in = fopen("input.txt", "rt");
char line[8192];
int N;
if(in == NULL)
return EXIT_FAILURE;
fgets(line, sizeof(line), in);
sscanf(line, "%d", &N );
#ifdef DEBUG
printf("N = %d\n", N );
#endif
for( int i = 0; i < N; i++ )
{
string characters;
string formatted = "";
fgets(line, sizeof(line), in);
for( int i = 0; i < sizeof(line); i++ )
if( line[i] == '\n' )
line[i] = '\0';
characters = line;
#ifdef DEBUG
puts(characters.c_str());
#endif
answer = 0;
recursive(characters, 0);
answer %= 1000;
printf("Case #%d: %04d\n", i + 1, answer );
answer = 0;
}
}
サンプルとsmallはすぐに答えがでて、correctになった。largeをやると・・・・時間がかかりすぎる。これは再帰では無理だったかと思うけど、後の祭り。結局、時間切れでCのlargeは取れませんでした。
- 著者／訳者：ティモシー・フェリス
- 出版社：青志社( 2011-02-03 )
- 単行本：640 ページ
- ISBN-10 : 4905042097
- ISBN-13 : 9784905042099
- 定価：￥ 1,995
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
- 著者／訳者：秋葉拓哉 岩田陽一 北川宜稔
- 出版社：マイナビ( 2012-01-28 )
- 単行本（ソフトカバー）：368 ページ
- ISBN-10 : 4839941068
- ISBN-13 : 9784839941062
- 定価：￥ 3,444
Use dynamic programming.
Create a memory matrix of M[sentence.length][interestphrash.length]. Iterate over each letter in the input string, and calculate how many ways there to be at the jth letter of the phrase of interest. You want to keep summing from the i-th and j-1th memory matrix. When you add, mod by 1000 and add the mods together.
Thanks for your advice. I agree with your implementation. This is a typical DP problem and I should use DP. Anyway, I would like to take part in next opportunity.