Hatena::Grouptopcoder

cou929のTopCoder日記

2011-05-08

Google Code Jam 2011 Qual

21:08

A, B, C を提出. small, large ともに通ったので無事 round1 に進むことができました.

いつもは C++ なんですが. 今年は python でやっています. まあどっちにしろ一般的な言語です.

A. Bot Trust

シミュレーションするだけです. 計算量も問題なし.

T = int(raw_input())

for test_num in range(1, T + 1):
    ret = 0
    line = raw_input().split()
    N = int(line[0])
    seq = []

    for i in range(1, len(line), 2):
        seq.append((line[i], int(line[i+1])))

    cur_pos = {'O': 1, 'B': 1}
    others_duration = 0
    others_color = seq[0][0]

    for i in seq:
        color = i[0]
        dst = i[1]
        time = abs(cur_pos[color] - dst) + 1

        if others_color == color:
            ret += time
            others_duration += time
        else:
            if time > others_duration:
                diff = time - others_duration
                ret += diff
                others_duration = diff
            else:
                ret += 1
                others_duration = 1

        others_color = color
        cur_pos[color] = dst

    print "Case #{0}: {1}".format(test_num, ret)

B. Magicka

英語ゲー. Example も不親切だし, small input が combines / opposes 最大 1 のものなので, ちゃんと問題文をよく読んで実装しないといけません.

それを除くと, 実装はやや面倒ですが普通にシミュレーションするだけの問題です. 計算量も問題なし.

def check_comb(last, seq):
    for i in seq:
        if last == i[0]:
            return i[1]
    return False

def check_oppos(target, seq):
    for i in seq:
        if target.count(i) > 0:
            return True
    return False

T = int(raw_input())

for test_num in range(1, T + 1):
    line = raw_input().split()
    combs = {}
    oppos = {}
    spells = ""
    ret = []

    # parse
    idx = 0
    C = int(line[idx])

    i = 0
    while i < C:
        i += 1
        idx += 1
        seq = line[idx]
        if combs.has_key(seq[0]):
            combs[seq[0]].append((seq[1], seq[2]))
        else:
            combs[seq[0]] = [(seq[1], seq[2])]
        if combs.has_key(seq[1]):
            combs[seq[1]].append((seq[0], seq[2]))
        else:
            combs[seq[1]] = [(seq[0], seq[2])]

    idx += 1
    D = int(line[idx])

    i = 0
    while i < D:
        i += 1
        idx += 1
        seq = line[idx]
        if oppos.has_key(seq[0]):
            oppos[seq[0]].append(seq[1])
        else:
            oppos[seq[0]] = [seq[1]]
        if oppos.has_key(seq[1]):
            oppos[seq[1]].append(seq[0])
        else:
            oppos[seq[1]] = [seq[0]]

    idx += 1
    N = int(line[idx])
    spells = line[idx + 1]

    # proccess spells
    for s in spells:
        if len(ret) < 1:
            ret.append(s)
        else:
            cur = s
            # check combine
            last = ret[-1]
            if combs.has_key(cur):
                res = check_comb(last, combs[cur])
                if res:
                    cur = res
                    ret.pop()

            # check opposite
            if oppos.has_key(cur) and check_oppos(ret, oppos[cur]):
                ret = []
            else:
                ret.append(cur)

    print "Case #{0}: [{1}]".format(test_num, ", ".join(ret))

C. Candy Splitting

まずは small 用に全探索を書きました. 組み合わせの列挙にはビットを使いました.

import math

T = int(raw_input())
seq = []
ret = -1

def calc(pat1, pat2, sum, n):
    global seq
    global ret

    if n >= len(seq):
        if pat1 == pat2:
            ret = max(ret, max(sum, reduce(lambda x, y: x + y, seq) - sum))
        return

    calc(pat1 ^ seq[n], pat2, sum + seq[n], n + 1)
    calc(pat1, pat2 ^ seq[n], sum, n + 1)

for test_num in range(1, T + 1):
    ret = -1
    N = int(raw_input())
    seq = map(int, raw_input().split())
    total = reduce(lambda x,y: x+y, seq)

    for i in range(1, 2 ** N - 1):
        pat1 = 0
        pat2 = 0
        sum = 0

        for j in xrange(N):
            if i >> j & 1:
                pat1 ^= seq[j]
                sum += seq[j]
            else:
                pat2 ^= seq[j]

        if pat1 == pat2:
            ret = max(ret, max(sum, total - sum))

    ret = ret if ret != -1 else 'NO'
    print "Case #{0}: {1}".format(test_num, ret)

当然ですが large では 2 ^ 100 のループになってしまうので間に合いません.

はじめは dp で計算量を削減するのかと思い検討していたんですが全然できそうにありません. 小さいインプットで問題を手で解いていると,

  • 'NO' にならないのは入力のすべての xor が 0 になる場合
  • A xor B = 0 は A = B
  • よって一番小さいキャンディーセットをパトリックにあげるのが最適な戦略 (パトリック哀れ)

ということに気づきました. 実装後, 念のため全探索で解いた small のアウトプットと diff をとってみたところ一致したので安心して submit. 無事通りました.

T = int(raw_input())

for test_num in range(1, T + 1):
    N = int(raw_input())
    seq = map(int, raw_input().split())
    total = reduce(lambda x,y: x+y, seq)
    patrick_total = reduce(lambda x,y: x^y, seq)
    mini = min(seq)

    if patrick_total != 0:
        ret = 'NO'
    else:
        ret = total - mini

    print "Case #{0}: {1}".format(test_num, ret)

D. Goro Sort

できませんでした. そもそも期待値が出てきた時点で苦手意識が...

詳しくは公式の Contest analytics をどうぞ.

RuteRute2012/07/09 20:46Your cranium must be prtoecting some very valuable brains.

fzxitclfdifzxitclfdi2012/07/10 15:37DcsUB7 <a href="http://idndroelcvuo.com/">idndroelcvuo</a>

zglklfrsfzglklfrsf2012/07/10 21:3376nula , [url=http://ywddkghthnac.com/]ywddkghthnac[/url], [link=http://crdgakptayms.com/]crdgakptayms[/link], http://piqgffcdpjdz.com/

yhomaosajyhomaosaj2012/07/12 11:546nlduI <a href="http://qxqdvckgxidk.com/">qxqdvckgxidk</a>

otqvghxhcotqvghxhc2012/07/12 17:26FaJSvG , [url=http://yjempfikcskq.com/]yjempfikcskq[/url], [link=http://znebtdrnhbru.com/]znebtdrnhbru[/link], http://labvpfdclfqz.com/

2010-12-15

SRM 490 div1 Easy (リハビリ)

00:01

Easy - Starport

ひさびさ. リハビリがてら easy を解いてみました.

宇宙港に M 単位時間ごとに宇宙船がつく. 港では N 単位時間ごとにテレポーテーションが行われる. 港についた船は次のテレポーテーションまで待って, 転送される. 到着時間とテレポーテーション時間が同時刻だった場合, その船は即座に転送される. 船がテレポーテーションを待つ時間の期待値を求めよ.

船の待ち時間を順に書きだすと, ループする数列になること. 1ループ分で計算をすれば期待値が求められること. 1ループの長さは高々 N であること (i 番目の船の待ち時間は N - (i*M % N) なので). ループの最後の時刻は N と M の最小公倍数になることには気が付きました. しかしここまでをストレートに実装したとすると, N, M は [1, 1000000000] の範囲の値をとるので, N = 1000000000, M = 1 のようなケースで TLE してしまいます. 数列の和を求める方法がわかればよかったんですが, 思いつかなかったのでとりあえず実装. 面倒なので lcm は適当.

  double getExpectedTime(int N, int M) {
    double ret = 0;
    long long lcm = N * M;
    long long total = 0;
    long long counter = 0;
    int i;

    for (i=1; i*M<=lcm; i++) {
      total += (i*M % N == 0) ? 0 : (N - i*M % N);
      counter++;
    }

    ret = (double)total / (double)counter;

    return ret;
  }

予想通りワーストケースで TLE でした.

ここで諦めて editorial. 自分が気づけなかった事実は, "数列の1ループの要素数は lcm / M" になるということ. また明らかに数列の要素は等間隔にならんでいます. ここで数列の順序を昇順にソートしたものは単なる等差数列になるので, これを要素数で割れば期待値になります. lcm と gcd の関係 (lcm(a, b) = a / gcd(a, b) * b) も用いると, 次のように求められます.

lcm と gcd の関係より数列1ループの要素数を以下のように表す
lcm(N, M) = N / gcd(N, M) * M
lcm(N, M) / M = N / gcd(N, M) * M / M
(要素数) = N / gcd(N, M)

よって数列の要素の間隔は gcd(N, M) ということになる. 

次のような 初項 0, 公差 gcd(N, M), 
(最後の項は "(N/gcd(N, M) - 1) * gcd(N, M)") 
の等差数列の和を求める. 
(簡略化のため gcd(N, M) = x とする)

[0, 1*x, 2*x, ...,  (N/x-1)*x] = (N/x) * (0 + (N/x-1)*x) / 2 = (N/x) * (N - x) / 2)

これを要素数 N/x で割る.

(N/x) * (N - x) / 2) / N/x = (N - x) / 2

よって答えは N - gcd(N, M) / 2 の1行です. gcd は作りおきしてあるユークリッドの互除法の関数を使い回します.

class Starport {
public:
  int gcd(const int _a, const int _b) {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b) {
      int tmp = a % b;
      a = b;
      b = tmp;
    }

    return a;
  }

  double getExpectedTime(int N, int M) {
    return (N - gcd(N, M)) / 2.0;
  }
};

2010-09-02

SRM 480 div1 (リハビリ)

00:16

とても久々なのでとりあえず250をやってみる.

Easy - InternetSecurity

ngワードの辞書が与えられる. ある文章に閾値以上のngワードが含まれていると, その文章は危険と認定される. またその際, その危険な文章の全単語がngワードとして辞書に追加される. これを危険な文章が見つからなくなるまで繰り返し, 検出した危険な文章のセットを返す.

アルゴリズムとしては毎回ふつうに探索しているだけなのですが, なぜかシステムテストが通らない. 赤い人のコードをみてみても大筋では同じことをやっているようにしか見えないので, どこかでしょうもないバグを埋め込んでいるか, なにか問題を勘違いしているのかもしれません.

フラグの立て忘れでした. これは情けない.

class InternetSecurity {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
    int i, k;
    int n = address.size();
    vector <string> ret;
    vector <vector <string> > keywords;
    vector <bool> is_danger(n, false);
    vector <int> result_indexes;
    set <string> dangerous_set;

    for (i=0; i<n; i++)
      keywords.push_back(split(keyword[i], " "));

    for (i=0; i<dangerous.size(); i++)
      dangerous_set.insert(dangerous[i]);

    while (1) {
      bool exist = false;

      for (i=0; i<n; i++)
        if (!is_danger[i]) {
          int counter = 0;

          for (set <string>::iterator j=dangerous_set.begin(); j!=dangerous_set.end(); j++)
            if (find(keywords[i].begin(), keywords[i].end(), *j) != keywords[i].end())
              counter++;

          if (counter >= threshold) {
            exist = true;  // このフラグを立て忘れていた
            result_indexes.push_back(i);
            is_danger[i] = true;
            for (k=0; k<keywords[i].size(); k++)
              dangerous_set.insert(keywords[i][k]);
          }
        }

      if (!exist)
        break;
    }

    sort(result_indexes.begin(), result_indexes.end());
    for (i=0; i<result_indexes.size(); i++)
      ret.push_back(address[result_indexes[i]]);

    return ret;
  }
};

2010-07-08

SRM 475 div1

21:20

ひさびさのSRM. 一問も解けず rating は 1507 -> 1420.

Easy - RabbitStepping

うさぎがr羽いて, n (r <= n) マスの一直線のセルがある. うさぎをセル上に配置する. セルは3色に色分けされていて, それぞれ動作が異なる. セルの色に応じてうさぎを移動させ, ひとつのセルに2羽うさぎが乗るとその2羽は取り除かれる. また毎ターンごとにセルの右端が除かれる. のこり2セルになるまでこの操作を繰り返したときの, のこったうさぎの数の期待値を求めよ.

うさぎの配置の仕方は, セル数nからうさぎの数rを選ぶ場合の数 nCr となります. セル数の上限が17なので, 17 C 8 = 24310 がうさぎの配置パターンの最大数です. それぞれについて最大で17ステップの処理が行われます. このオーダーならばうさぎの配置パターンについてシミュレーションをして期待値を求めればよさそうです.

うさぎの配置パターンの列挙方法ですが, いま冷静になると next_permutation 一択なんですが, 本番では再帰でがんばってました. で, その部分がおそらく原因で, ローカルでは大丈夫だったんですがサーバでは謎の例外が出て, システムテストに落ちてしまいました. 以下は next_permutation を使った修正版です.

うさぎのシミュレーションをしているのはcalc()という関数. ふつうに愚直にやっています. もうすこし綺麗に書きたい(特にうさぎを移動させている部分)ものですが, これをバグ無く一発でかけたのは少し嬉しかったです.

class RabbitStepping {
public:
  string field;

  int calc(vector <int> &_rabbits) {
    vector <int> rabbits = _rabbits;
    int ret = 0;
    int i, j;
    int n = field.size();
    string f = field;
    vector <int> before(n, -1);

    for (i=0; i<n-2; i++) {
      vector <int> tmp = rabbits;
      vector <int> tmp_before(n, -1);

      for (j=0; j<f.size(); j++) {
        if (rabbits[j] == 1) {
          if (j == 0) {
            tmp[j]--;
            tmp[j+1]++;
            tmp_before[j+1] = j;
          } else if (j >= f.size() - 2) {
            tmp[j]--;
            tmp[j-1]++;
            tmp_before[j-1] = j;
          } else {
            if (f[j] == 'W') {
              tmp[j]--;
              tmp[j-1]++;
              tmp_before[j-1] = j;
            } else if (f[j] == 'B') {
              tmp[j]--;
              tmp[j+1]++;
              tmp_before[j+1] = j;
            } else if (f[j] == 'R') {
              if (i == 0) {
                tmp[j]--;
                tmp[j-1]++;
                tmp_before[j-1] = j;
              } else {
                tmp[j]--;
                tmp[before[j]]++;
                tmp_before[before[j]] = j;
              }
            }
          }
        }
      }

      for (j=0; j<f.size(); j++)
        if (tmp[j] > 1) {
          tmp[j] = 0;
          tmp_before[j] = -1;
        }
      rabbits = tmp;
      before = tmp_before;

      f = f.substr(0, f.size()- 1);
    }

    for (i=0; i<rabbits.size(); i++)
      ret += rabbits[i];

    return ret;
  }

  double getExpected(string _field, int r) {
    field = _field;
    int counter = 0, rabbitnum = 0;
    vector <int> v(field.size(), 1);
    int i;

    for (i=0; i<field.size()-r; i++)
      v[i] = 0;

    do {
      counter++;
      rabbitnum += calc(v);
    } while (next_permutation(v.begin(), v.end()));

    return (double)rabbitnum / (double)counter;
  }
};

2010-06-26

SRM 473 div2 (過去問)

13:34

またもやアルゴリズム問題をやるのは久々です. やはりしばらくやらないと, 全然できなくなってしまいます. そろそろ再開させたいところです.

Easy - OnTheFarmDivTwo

鶴亀算を解くだけの問題. 探索範囲が小さいので, コンピュータらしく全探索でさくっとやりました.

class OnTheFarmDivTwo {
public:
  vector <int> animals(int heads, int legs) {
    vector <int> ret;
    int i;

    for (i=0; i<=heads; i++) {
      if (i * 2 + (heads - i) * 4 == legs) {
        ret.push_back(i);
        ret.push_back(heads-i);
        break;
      }
    }

    return ret;
  }
};

Medium - SequenceOfCommands

2次元平面上を動くコマンドが与えられる. コマンドを無限に繰り返したとき, 軌跡がループしているかどうかを判定せよ.

シミュレーションしてループを検出します. ループの検出には, コマンドの1ターンごとに, 初期位置に帰ってきているかどうかを調べます. 何ターンのコマンドをシミュレートするかについては, このコマンド体系では90度単位でしか曲がれないので, 最大4ターンまで調べればいいことになります.

つまらないバグで時間を費やしてしまいました. 今回のようにif文を列挙する場合は, ありえない値をハンドリングする(switch分のdefaultにあたる部分)ようにすれば, コードの間違いを発見しやすいのではないかと思いました.

class SequenceOfCommands {
public:
  string whatHappens(vector <string> commands) {
    string ret = "unbounded";
    int curx = 0, cury = 0;
    int dir = 0;  // N:0, E:1, S:2, W:3
    string command;
    int i, j;
    vector <pair <int, int> > path;
    
    for (i=0; i<commands.size(); i++)
      command += commands[i];

    for (i=0; i<4; i++) {
      for (j=0; j<command.size(); j++) {
        if (command[j] == 'S') {
          if (dir == 0)
            cury++;
          else if (dir == 1)
            curx++;
          else if (dir == 2)
            cury--;
          else if (dir == 3)
            curx--;
        } else if (command[j] == 'R') {
          dir = (dir + 1) % 4;
        } else if (command[j] == 'L') {
          if (--dir < 0)
            dir = 3;
        }
      }
      if (curx == 0 && cury == 0) {
        ret = "bounded";
        break;
      }
    }

    return ret;
  }
};

MarineideMarineide2012/07/10 10:43You've imrpesesd us all with that posting!

jzaxfxwjzaxfxw2012/07/12 13:042FEYpn <a href="http://tjkastiekpwv.com/">tjkastiekpwv</a>