Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-07-29SRM477 Div1

SRM477 Div1 250 Islands

| 01:44 | SRM477 Div1 250 Islands - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM477 Div1 250 Islands - SRM diary(Sigmar) SRM477 Div1 250 Islands - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→英文が難しい・・・

→ともかく、六角形の区画で海と陸の区切りとなる辺の数を求めればいいらしい。revenueとか普段使わないような変な単語使わないでほしい。。

→とりあえず横幅を2倍にすれば解けそうな気がする

→横幅2倍にして、奇数行を1文字ずらして、海と陸の境界線をカウントする

→サンプル通る→提出

→・・・

→もう少しよく考えてみよう

→む・・よく見たら・・偶数行の最後にパディングするのを忘れている

→でも、サンプル実行でアクセス違反にならないなぁ

→デバッグしてみると、stringのサイズを超えて添字アクセスしても実行時エラーにはならない

→実際にはもっと多くメモリをアロケートしているからなのかな?

→どうしよう・・再提出するか・・・

→まあ・・・多分大丈夫かな・・・・・・・やめとこ

→500へ


チャレンジフェーズ

→突っ込みどころが思い当たらない

→何もせず


システムテスト

→Passed

→よかった。。後で考えるとやっぱり通るか確実でないものを放置するのは危なかった。本来なら再提出ですね。


以下、ソースです。

class Islands { 
public: 
  int beachLength(vector <string> kingdom) { 
    int res=0; 
    int h=kingdom.size(), w=kingdom[0].size(); 
    int w2=w*2+1; 
    int dr[4]={1,0}, dc[4]={0,1}; 
    vector <string> k2; 

    for(int i=0; i<h; i++) { 
      k2.push_back(string()); 
      if(i%2==1) k2[i].push_back('0'); 
      for(int j=0; j<w; j++) { 
        k2[i].push_back(kingdom[i][j]); 
        k2[i].push_back(kingdom[i][j]); 
      }
      //本来ならここにk2[i].push_back('0')のような文を入れる 
    } 

    for(int i=0; i<h; i++) { 
      for(int j=0; j<w2; j++) { 
        for(int l=0; l<2; l++) { 
          int nr=i+dr[l], nc=j+dc[l]; 
          if(nr<0 || nr>=h || nc<0 || nc>=w2) continue; 
          if(k2[i][j]=='#' && k2[nr][nc]=='.') res++; 
          else if(k2[i][j]=='.' && k2[nr][nc]=='#') res++; 
        } 
      } 
    } 
         
    return res; 
  } 
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100729