Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-14

SRM385 div2 再チャレンジ

21:15

Medium - UnderscoreJustification

wordのセットと文字数wが渡されるので, ちょうどw文字になるようにwordwordの間に空白を挿入して一文をつくる. ただし各word間の空白の数はプラスマイナス1以内でないといけない. 複数の候補があるので, 辞書順に若いものを返す. ちなみに辞書順だと "アルファベット大文字" < "空白(の代わりにこの問題では"_"を用いる)" < "アルファベット小文字" の順になる.

問題はどのword間の空白を一文字ふやすかを求めることです. 実はword数が高々10という制約があるので, 全組み合わせも最大で3桁ほどになるはず(例えばwordが10で5か所選ぶとしても, 9C5 程度)なので全探索しても良いんですが, 今回はgreedyな方法で実装してみました. 方法は, 1.小文字で始まるwordの前には優先して空白を入れる. 2.まだ空白が余っている場合は後ろから空白を挿入していく. というものです.

コードはスマートじゃないし, 変数名がなんか適当ですが, 一応できました.

class UnderscoreJustification {
public:
  string justifyLine(vector <string> words, int width) {
    string ret = words[0];
    int word_length = 0;
    int spaces = words.size() - 1;
    int underscores = 0;
    int rest_underscores = 0;

    for (int i=0; i<words.size(); i++)
      word_length += words[i].size();

    underscores = (width - word_length) / spaces;
    rest_underscores = (width - word_length) % spaces;

    vector <int> space_nums(spaces, underscores);

    for (int i=1; i<words.size(); i++)
      if (rest_underscores > 0 && 'a' <= words[i][0] && words[i][0] <= 'z') {
        space_nums[i-1]++;
        rest_underscores--;
      }

    for (int i=space_nums.size()-1; i>=0; i--)
      if (rest_underscores > 0 && space_nums[i] == underscores) {
        space_nums[i]++;
        rest_underscores--;
      }

    for (int i=1; i<words.size(); i++) {
      string space(space_nums[i-1], '_');
      ret += space;
      ret += words[i];
    }

    return ret;
  }
};

Hard - SummingArithmeticProgressions

x, x+1*d, x+2*d ... x+(k-1)*d という数列がある. 正の整数left, rightとkが与えられるので, 数列の各要素の総和が[left, right]の範囲に収まるものの個数を求めよ.

これは, もしかしたら何か数学的な理論を使ったり漸化式を作ってdpしたりなどを想定した問題だったのかもしれませんが, kが2-5という非常に小さい範囲であることと, 手計算でもすぐに規則性が見つかってしまうという理由で簡単でした. 手で計算してみるとわかるのですが, それぞれのkについて, 求まる数列の総和は以下のようになっています.

  • k=2のときは3以上の整数
  • k=3のときは{6, 9, 12, 15, ...}
  • k=4のときは{10, 14, 16, 18, ...}
  • k=5のときは{15, 20, 25, ...}

よってleftとrightの間に該当する数字がいくつあるかをカウントするだけです. こちらもやはりコードがなんか汚いですが, 解けました.

class SummingArithmeticProgressions {
public:
  int howMany(int left, int right, int k) {
    int ret = 0;
    if (k == 2) {
      if (right >= 3)
        ret = right - max(left, 3) + 1;
    } else if (k == 3) {
      for (int i=6; i<=right; i+=3)
        if (left <= i)
          ret++;
    } else if (k == 4) {
      for (int i=14; i<=right; i+=2)
        if (left <= i)
          ret++;
      if (left <= 10 && right >= 10)
        ret++;
    } else if (k == 5) {
      for (int i=15; i<=right; i+=5)
        if (left <= i)
          ret++;
    }

    return ret;
  }
};