Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Google Code Jam 2009 Qualification Round

Google Code Jam 2009 に参加してみました。初参加です。

Qualification Round は平日開催ということで,午前中に休みをとってA,Bの2問,帰宅後にCの1問にチャレンジとなりました。
初めて参加する大会なので,システムのI/Fに慣れるのに苦労したという感があります。システムトラブルにも丁度ひっかかりましたし(はじめは自分の環境が悪いのかと焦りました),IEからデータをアップロードする部分ではVistaのセキュリティ警告がうっとおしく出て,しかもセキュリティ警告のウインドウがIE本体の後ろに隠れて,IEがハングアップした状態になるという始末。異なるファイルをアップロードしてしまうという間違いもやらかしました。
他にもいくつかの問題が生じましたが,これらを乗り越え,本Roundは何とか全問通しました。

A,Bの問題については,他の方々と同じような解き方で,code jamサイトのContest Analysisの説明とも変わらない感じだと思います。

Cの問題,出ました「典型的なDP」。Contest Analysisでも「a standard dynamic programming problem」と書かれています。解法を考えているときには,直感的にDPだろうなあとは思っているのですが,DPによる解法へは至れませんでした。
コンテスト終了後にDPで解けることを知って,けっこうへこみました。典型的と言われる問題でDPに気付けないとすると先が思いやられます。

 Cの問題は熟考の末,"welcome to code jam"の各文字の出現位置を結ぶツリーを考えて,ボトムアップにケースの数を数え上げるという手法を思いつきました。計算量はDPと同等だと思います。

▼ 問題C のコード
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
#pragma warning(disable: 4996)

typedef struct {
  int pos;
  int case_num;
} ELEM;

vector< vector<ELEM> > place;

void main(int argc, char*argv[])
{
  FILE* fin = fopen(argv[1],"r");
  FILE* fout = fopen(argv[2],"w");
  if( fin == NULL ){
    printf("cannot open in-file : %s\n", argv[1]);
    return;
  }
  if( fin == NULL ){
    printf("cannot open out-file : %s\n", argv[2]);
    return;
  }
  /////////////////////////////
  char line[1024];
  int CASE;
  fgets(line,1024,fin);
  CASE = atoi(line);

  int start[512];
  int end[512];
  const char phrase[20] = "welcome to code jam";
  vector<ELEM> letter_place;
  vector<ELEM>::iterator it,it2;
  ELEM elem;
  int sum;

  for( int cs = 0; cs < CASE; cs++ ){
    fgets(line,1024,fin);
    int pos = 0;
    int line_size = strlen(line);
    place.clear();
    // start
    for( int letter = 0; letter < 19; letter++ ){
      while( pos < line_size ){
        if( line[pos] == phrase[letter] ){
          start[letter] = pos;
          pos++;
          break;
        }
        pos++;
      }
      if( pos == line_size ){
        sum = 0;
        goto finish;
      }
    }
    // end
    pos = line_size-1;
    for( int letter = 18 ; letter >= 0; letter-- ){
      while( pos >= 0 ){
        if( line[pos] == phrase[letter] ){
          end[letter] = pos;
          pos--;
          break;
        }
        pos--;
      }
    }
    /// 
    for( int letter = 0; letter < 19; letter++ ){
      letter_place.clear();
      for( pos = start[letter]; pos <= end[letter]; pos++ ){
        if( line[pos] == phrase[letter] ){
          elem.pos = pos;
          elem.case_num = 1;
          letter_place.push_back(elem);
        }
      }
      place.push_back(letter_place);
    }
    /// 
    for( int letter = 17; letter >= 0; letter-- ){
      for( it = place[letter].begin();it != place[letter].end(); it++ ){
        sum = 0;
        for( it2 = place[letter+1].begin(); it2 != place[letter+1].end(); it2++ ){
          if( it->pos < it2->pos ){
            sum += it2->case_num;
          }
        }
        sum %= 10000;
        it->case_num = sum;
      }
    }
    ///
    sum = 0;
    for( it = place[0].begin();it != place[0].end(); it++ ){
      sum += it->case_num;
    }
    sum %= 10000;
    ///
finish:
    fprintf(fout,"Case #%d: %04d\n", cs+1, sum );
  }
}

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/36-eb49f846
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。