Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-23

SRM456 div2

13:58

div1になることができました!

writerは rng_58 さん. easy, medium が解けて チャレンジに二回成功. ルーム1位, div2全体で18位. raging は 1138 -> 1240 (+102) でついに blue coder になることができました. 今年の目標がぎりぎり達成できてよかったです. ブログの背景もブルーに変えてみました. 次回からはまず250をしっかり解くことを目標にやっていきます.

Easy - AppleWord

正規表現 /^ap+le$/i にマッチするような文字列をapple wordという. 与えられた文字列に対して, ある文字を別の文字に入れ替えることができる. 与えられた文字列をapple wordにするには何回文字を入れ替えればよいか. 不可能な場合は-1.

return が -1になるのは文字長が5未満のとき. あとは最初の文字が"a", 最後の二文字が"el"になっているかを調べ, その間を"p"になるようにします.

class AppleWord {
public:
  int minRep(string word) {
    int ret = 0;

    if (word.size() < 5)
      return -1;

    if (word[0] != 'a' && word[0] != 'A')
      ret += 1;

    for (int i=1; i<word.size()-2; i++)
      if (word[i] != 'p' && word[i] != 'P')
        ret++;

    if (word[word.size()-2] != 'l' && word[word.size()-2] != 'L')
      ret += 1;

    if (word[word.size()-1] != 'e' && word[word.size()-1] != 'E')
      ret += 1;

    return ret;
  }
};

Medium - SilverDistance

将棋の銀将が無限大の盤上に置かれている. スタート, ゴールの座標が与えられるので, 最短何手でゴールまで行けるかを求める.

あまりスマートではないのですが, スタートからゴールまでgreedyに一手ずつ進んでいく方針で組みました. 行けるところまでは斜めに進み, syとgyの差が0になるような左右に進む場合は 右下, 右上, 右下, ... のようにジグザグに進みます. またgx - sx == 0 で gy - sy > 0 のような真下に進まなければいけない場合は, 右下, 左下, 右下, ... のようにジグザグに進みます.

最初bfsで探索するコードを書いてしまって, 時間をロスしました. そういう探索だとTLEします. もっと早く解きたかったです.

class SilverDistance {
public:
  int minSteps(int sx, int sy, int gx, int gy) {
    int ret = 0;
    int curx = sx, cury = sy;
   
    while (!(curx == gx && cury == gy)) {
      int dirx = 0;
      int diry = 0;

      if (gx - curx > 0)
        dirx = 1;
      else if (gx - curx < 0)
        dirx = -1;

      if (gy - cury > 0)
        diry = 1;
      else
        diry = -1;

      if (dirx == 0 && diry == -1)
        dirx = 1;

      curx += dirx;
      cury += diry;
      ret++;
    }

    return ret;
  }
};

Hard - CutSticks

棒が何本か与えられる. 棒を一本取り出して任意の長さで折って2つに分けることができる. 棒を最大C回折って, 降順に並べ, K番目にくる棒の長さを最長にする.

これは解けませんでした. 最も素朴な解法は,

  1. 棒をソート
  2. 最長のものをちょうど半分に折る

これを棒がK本になるまで繰り返すという方法です. ただKはワーストで 1,000,000,050 と大きいので, とてもじゃないけど間に合いません. 別の方法を考える必要があります. 棒の長さの変遷には規則性がありそうなので, それを見つける必要がありそうです.

Challenge phase

500 で真下に進むケースを考えていない人がいたので撃墜しました.