Coding Memorandum

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

スポンサーサイト

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

GCJ 2012

GCJで初のTシャツ圏内!ちょっとうれしい。最近,ショートラウンドものから遠ざかっていたのだけど,かなりの健闘を見せました。

まだまだ問題によって得意不得意の波が大きいので,来年以降も安定的にTシャツ圏内に入れるように実力をつけていきたいなぁと思うところです。

スポンサーサイト

Google Code Jam 2010 Qualification Round

Google Code Jam への参加も2回目となり,だいぶ手馴れた感があります。Code Jam用のC++スケルトンコードも熟れてきました。

今回は予選ということで手を抜いてメモを取らずに頭の中で考えることとしたら,条件の考慮の抜け漏れが出てしまい,正解へ辿り着くまでに何回かのチャレンジを必要としてしまいました。英語を読み進めることに必死となり,読み取った条件が頭の中から抜けていってしまう傾向があるようです。次回のラウンドからは,しっかりとメモ上で検討を進めようと思います。

問題A

問題Aは,問題文の解釈に時間を取られました。初めは,Snapperがlightの機能を持っていると思い込んでしまい,問題文の解釈に苦しみました… "The light is plugged into the Nth Snapper"が目に入ってこなかったようです。
私の採った解法は,まずN番目のSnapperが初めてONになるまでを考えました。NがONになるには,n番目(1<=n<=N)がONになる必要があり,n番目がONになるには,n-1番目がONになってから2^(n-1)回のsnapが必要です。すなわちΣ 2^(n-1)回となります。そしてN番目のSnapperが一度ONとなった後に再度ONとなるのは,2^N 回後となります。こんな考えで実装してみました。
後ほど,2chに「1行で書ける」とあったので考え直してみたら,Σ 2^(n-1) = 2^N-1であり,そこから2^N回毎ということは,「snap回数 % 2^N = 2^N-1」が成立すればよいことに気づきました。

問題B

問題Bは,数学的なひらめきが必要そうでしたがすぐにひらめかず,またlongを解くには多倍長演算が必要であったので,パスしました。多倍長演算は「プログラミングコンテストの数学」の中で準備しておこうと思っていたのですが,面倒になって後回しとしていました。こんなことなら確認しておけば良かったと・・・

問題C

問題Cは,ローラーコースターの乗車をR回試行すれば良さそうですが,愚直に毎回乗れる人数を算出すると時間切れになりそうなので一工夫必要です。乗れる人数は,どのグループが先頭になるかで決定的な値となるため事前に計算しておきます。このようにすれば試行ループの内側は配列参照と加算で済み,ループ回数Rの最大値は10^8なので,十分に間に合います。

Round1-Aは,5/22(土) 10:00 から。今年はなるべく早いRoundでの勝ち抜けを目指します。

Google Code Jam 2009 Round1

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

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

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

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

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

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

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

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。