naoya_t@topcoder

2009-01-07

SRM377 Div1 Easy: SquaresInsideLattice

過去問, 練習 | 23:39 |

8'35''ぐらい。

SRM378 Div1 Easy: TrueStatements

過去問, 練習 | 23:11 |

思いついたのをまっすぐ書いた。3'45''ぐらい。

Passed System Test / 244.98点。

SRM379 Div1 Easy: SellingProducts

過去問, 練習 | 22:39 |

サンプルケースが親切

SRM432 Div1 Medium: GroupedWord

過去問, 練習 | 21:21 |

昨日のSRMの500点問題を解いてみる。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090107

2009-01-06

SRM432

23:04 |

01.06.2009 (今年最初)

DIV	level	問題名	競技中	備考
1	250	LampsGrid	◎	110.63点
1	500	GroupedWord	間に合わず
1	1000

SRM380 Div1 Easy: LameKnight

過去問, 練習 | 20:58 |

SRM432前の準備運動（その２） SRM開始まであと13分・・・ Test Caseは全部通ったのでsubmitしたけどSystem Test落ち

SRM381 Div1 Easy: TheDiceGame

過去問, 練習 | 20:41 |

SRM432前の準備運動に

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090106

2008-12-30

SRM382 Div1 Easy: CollectingRiders

過去問, 練習 | 03:01 |

問題読み違えてた。これ本番に1時間15分で解けるだろうか。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081230

naoya_t@topcoder - [Practice Room]465-480

2008-12-29

SRM383 Div1 Easy: Planks

過去問, 練習 | 23:55 |

Plankとは厚い板のこと。

SRM384 Div1 Easy: Library

過去問, 練習 | 23:39 |

簡単。split()は自前

SRM385 Div1 Easy: UnderscoreJustification

過去問, 練習 | 23:10 |

これは速解き系なんだろうな。

最近、慣れてきたのかコードが汚くなってきた。（スペースの数が減ったりとか）

SRM386 Div1 Easy: CandidateKeys

過去問, 練習 | 17:52 |

(statistics)

問題の意味がなかなか掴めなくて悩む。

サンプルのTest Caseは通るけどシステムテストが通らない←いまここ

後でやり直そう。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081229

2008-12-26

SRM387 Div1 Easy (300points): MarblesRegroupingEasy

過去問, 練習 | 19:55 |

どう解いたらよいのかぱっとは思いつかない。

全てのmarbleをjoker boxに放り込む（move回数はN-1）のが手数としては最大になるのかな、というところまで。あとで考えよう。

SRM388 Div1 Easy: SmoothNumbers

過去問, 練習 | 11:59 |

SRM389 Div1 Easy: ApproximateDivision

過去問, 練習 | 10:11 |

簡単。

SRM390 Div1 Easy: ConcatenateNumber

過去問, 練習 | 09:57 |

SRM391 Div1 Easy: IsomorphicWords

過去問, 練習 | 09:42 |

問題を読み違えていて問題文のTest Caseすら通らず焦る。

SRM392 Div1 Easy: TwoStringMasks

過去問, 練習 | 08:46 |

文字列操作。split()は自前。

split()

Library | 08:51 |

私家版split()関数。

まずはデリミタがintのもの。

省略時には空白をデリミタとして認識する。

#include <string>
#include <vector>
using namespace std;

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim)
        s++;
      else
        break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

次は文字列(string)をデリミタに取るもの。

#include <string>
#include <vector>
using namespace std;

vector<string> split(string str, string delim)
{
  vector<string> result;

  if (str.length() == 0) return result;

  if (delim.length() == 0) {
    int len = str.length();
    result.resize(len);
    for (int i=0; i<len; i++) result[i] = str.substr(i,1);
    return result;
  }

  int since = 0, at;
  while ((at = str.find(delim, since)) != string::npos) {
    result.push_back(str.substr(since, at-since));
    since = at + delim.length();
  }
  result.push_back(str.substr(since));

  return result;
}

自由に使っていいけど無保証。ご利用は計画的に。

おまけ

googletestもつけとくよ。

#include <gtest/gtest.h>

// テストケースを単体の関数として実装する
TEST(SplitTest, Split1)
{
  vector<string> result;

  result = split("", "<>");
  EXPECT_EQ( 1, result.size() );
  
  // "a","<>" => ["a"]
  result = split("a", "<>");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  
  // "a<>b<>c","<>" => ["a","b","c"]
  result = split("a<>b<>c", "<>");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  
  // "a<>b<>c<>","<>" => ["a","b","c",""]
  result = split("a<>b<>c<>", "<>");
  EXPECT_EQ( 4, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  EXPECT_EQ( "" , result[3] );
  
  // "<>a<>b<>c","<>" => ["","a","b","c"]
  result = split("<>a<>b<>c", "<>");
  EXPECT_EQ( 4, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  EXPECT_EQ( "b", result[2] );
  EXPECT_EQ( "c", result[3] );
  
  // "<>a<>","<>" => ["","a",""]
  result = split("<>a<>", "<>");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  EXPECT_EQ( "" , result[2] );
  
  // "a<><>b","<>" => ["a","","b"]
  result = split("a<><>b", "<>");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "" , result[1] );
  EXPECT_EQ( "b", result[2] );
  
  // "<>","<>" => ["",""]
  result = split("<>", "<>");
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "", result[0] );
  EXPECT_EQ( "", result[1] );
  //
  result = split("", "");
  EXPECT_EQ( 0, result.size() );
  
  // 特殊用法 "abc".split('')
  result = split("abc", "");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  // EXPECT_TRUE_EQUAL( 2, 2 );
}

TEST(SplitTest, Split2)
{
  // cout << "test_split()" << endl;
  // dump_vs(result);
  vector<string> result;

  // "" => []
  result = split("");
  EXPECT_EQ( 0, result.size() );
  // "a" => ["a"]
  result = split("a");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // "a b c" => ["a","b","c"]
  result = split("a b c");
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  EXPECT_EQ( "c", result[2] );
  // "a " => ["a"]
  result = split("a ");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // " a" => ["a"]
  result = split(" a");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // " a " => ["a"]
  result = split(" a ");
  EXPECT_EQ( 1, result.size() );
  EXPECT_EQ( "a", result[0] );
  // "a b" => ["a","b"]
  result = split("a b");
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  // "a  b" => ["a","b"]
  result = split("a  b");
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  
  // "a b c",'b' => ["a "," c"]
  result = split("a b c",'b');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a ", result[0] );
  EXPECT_EQ( " c", result[1] );
  
  // "a,b",',' => ["a","b"]
  result = split("a,b", ',');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "b", result[1] );
  // "a,,b",',' => ["a","","b"]
  result = split("a,,b", ',');
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "" , result[1] );
  EXPECT_EQ( "b", result[2] );
  // ",a",',' => ["","a"]
  result = split(",a", ',');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  // "a,",',' => ["a",""]
  result = split("a,", ',');
  EXPECT_EQ( 2, result.size() );
  EXPECT_EQ( "a", result[0] );
  EXPECT_EQ( "" , result[1] );
  // ",a,",',' => ["","a",""]
  result = split(",a,", ',');
  EXPECT_EQ( 3, result.size() );
  EXPECT_EQ( "" , result[0] );
  EXPECT_EQ( "a", result[1] );
  EXPECT_EQ( "" , result[2] );
}

int main(int argc, char** argv)
{
  testing::InitGoogleTest(&argc, argv);

  return RUN_ALL_TESTS();
}

SRM393 Div1 Easy: InstantRunoffVoting

過去問, 練習 | 06:39 |

問題文のルールを素直にコーディングしたら解ける問題。のはずがちょっと手間取り。

SRM394 Div1 Easy: RoughStrings

過去問, 練習 | 05:57 |

TLE

SRM395 Div1 Easy: StreetWalking

過去問, 練習 | 05:19 |

これは速解き問題。Test Caseが親切。（斜め／＼に進んだほうが速いケースとか）

class StreetWalking {
public:
  long long minTime(int X, int Y, int walkTime, int sneakTime) {
    if(X>Y)swap(X,Y);
    long long a=Y-X, b=X, h=a/2, m=a%2;
    long long t = min(b*2*walkTime, b*sneakTime) 
      + min(a*walkTime, h*2*sneakTime+m*walkTime);
    return t;
  }
};