Coding Memorandum

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

スポンサーサイト

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

Google Code Jam 2009 Round1

Google Code Jam 2009 Round1 にチャレンジしました。
Roudn 1A~1C とフルに参加させて頂きました。:-P

結果は,辛くも1Cでようやく通過という,なかなか厳しいものでした。
1A,1Bでは1つの問題に時間をかけすぎて,結局時間切れという悲しい状況となり,1Cも通過点ぎりぎりでの通過でした。

今回のダメなパターンは「問題の理解が不十分なままコーディングに入ってしまい,デバッグに時間を取られてた」に尽きます。もう少し要領よくやらないと上は目指せないなと思いました。

さきほど見つけたTopCoderに関する記事に良いことが書いてありました。

  • アルゴリズム設計とそのテストが済むまで,プログラムを書いてはならない。
  • 問題を理解するまで,アルゴリズム設計をしてはならない。
  • 問題文を全て読むまで,問題を理解したと思ってはならない。

当たり前のことですが,今日の反省点として心に刻んでおきたいと思います。

この中で「問題を理解した」と判断を下すことというのが意外と難しく,経験によるところが大きいように思います。今回は,この部分で大きく躓きました。

スポンサーサイト

ICFP飲み会

shinhさんところで案内されていたICFP飲み会に参加してきました。

すごい人たちが集まってるんだろうなぁと思いながら,色々話をさせて頂いてたいへん良い刺激を受けました。何かいろいろ頑張ろうという気になります。
また,とってもインターナショナルな飲み会でもあったので,話の1/3ぐらいしか理解できてない面もあって・・・英会話頑張ろう!と強く思った飲み会でもありました。

たまには会社以外の人とも接点を持つというのは非常に良いことだなと思います。とても楽しみました!

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 );
  }
}

FC2Ad

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