Hatena::Grouptopcoder

cou929のTopCoder日記

2010-01-31

SRM 432 div1 (過去問)

21:58

Easy - LampsGrid

グリッド上にライトが置かれている. 行ごとにひとつずつスイッチがついている. スイッチを切り替えると, その行のライトのオンオフが切り替わる. K回スイッチを切り替えたとき, 一行全てがオンになっているような行は, 最大何行あるか.

ある行を全てオンにできるとします. この場合, その行と同じ並びの別の行も, 同様に全てオンになっているはずです. これを利用します. 各行毎に見ていき, その行を全てオンに出機るか調べます. できるのであれば, 同じ並び方の行がいくつあるか数え, その最大値を返します. ある行を全てオンにできるかどかの判定は, まず0の数を数え, その数がK以下で, なおかつ (K - (0の数)) が偶数である場合(一列に対して偶数回スイッチを入れると元に戻るため)可能であると判定できます.

editorialでとても短いコードが紹介されていて感動しました. それを基に書き直したのが以下です. stlのcount()を使っています. 思えばstl::algorithmはsortやreverseくらいしか使っていませんでした. countやaccumlateも使うべきところで使わなきゃなあと感じました.

class LampsGrid {
public:
  int mostLit(vector <string> initial, int K) {
    int ret = 0;

    for (int i=0; i<initial.size(); i++) {
      int num = count(initial[i].begin(), initial[i].end(), '0');
      if (num <= K && (K - num) % 2 == 0)
        ret = max(ret, count(initial.begin(), initial.end(), initial[i]));
    }

    return ret;
  }
};

2010-01-28

SRM 433 div1 (過去問)

10:24

Easy - MagicWords

MagicWordはある単語の文字の位置をスライドさせても, 元と同じになるような単語. 辞書と整数Kが与えられる. 辞書の単語のすべての並び方について, その並び方で単語を連結して一単語にし, その単語のMagicWordの数がKであるものの数を求める.

単語数が最大8, 各単語の長さが最大20, よって全てを探索しても 8! * 20 * 8 = 6451200 となり, 間に合いそうです. ストレートに全探索のコードを組んでみたところ, ワーストケースで非常に時間がかかってしまっていたので, mapでメモ化を入れました. システムテストでは最大約1秒掛かっているケースがありました.

この文章を書いていて気づいたんですが, intのvector "pos" は最初から昇順に並んでいるので, ソートする必要なかったです.

class MagicWords {
public:
  map <string, int> memo;

  bool isMagic(string &str, int pos) {
    int len = str.size();
    for (int i=0; i<len; i++)
      if (str[i] != str[(i+pos)%len])
        return false;
    return true;
  }

  int count(vector <string> S, int K) {
    int ret = 0;
    vector <int> pos;
    for (int i=0; i<S.size(); i++) pos.push_back(i);
    sort(pos.begin(), pos.end());

    do {
      string str;
      int magic = 0;
      for (int i=0; i<S.size(); i++) str += S[pos[i]];
      if (memo.find(str) != memo.end()) 
        magic = memo[str];
      else
        for (int i=0; i<str.size(); i++) if (isMagic(str, i)) magic++;
      memo[str] = magic;
      if (magic == K) ret++;
    } while (next_permutation(pos.begin(), pos.end()));

    return ret;
  }
};

2010-01-27

SRM 434 div1 (過去問)

09:10

Easy - FindingSquareInTable

2次元配列が与えられる. 各要素は[0-9]. 配列のインデックスが等差数列になるように要素を選んで数字を作る. 出来上がった数字のうち, 正の整数の2乗になっている最大値を求める.

テーブルから生成されうるすべての数字を4重ループで全て求めて, それぞれ平方になっているかを調べます. 計算量がいまいちわからなかったんですが, この方法だと, 10x10のテーブルで各要素につき約500強回のループになっていたんで, 10*10*500で十分に間に合っています. ちなみに最初この計算量が非常に大きくなると間違えて見積もってしまって, かなり時間をロスしました.

class FindingSquareInTable {
public:
  int findMaximalSquare(vector <string> table) {
    int ret = -1;
    int n = table.size(), m = table[0].size();

    for (int i=0; i<n; i++)
      for (int j=0; j<m; j++)
        for (int k=-9; k<10; k++)
          for (int l=-9; l<10; l++) {
            if (k == 0 && l == 0) continue;
            int cur = 0;
            int next_x = i, next_y = j;
            while (0 <= next_x && next_x < n && 0 <= next_y && next_y < m) {
              cur = cur * 10 + table[next_x][next_y] - '0';
              int checker = (int)sqrt(cur);
              if (cur == checker * checker) ret = max(ret, cur);
              next_x += k, next_y += l;
            }
          }

    return ret;
  }
};

2010-01-25

SRM 435 div1 (過去問)

10:49

Easy - CellRemoval

2分木が与えられる. ただひとつのセルが死んでいる. 死んでいる子ノードも死んでいると見なされる. 生きているリーフの数を求めよ. ただし木は1次元配列parentで表現されていて, parent[i] にはノードiの親が入っている.

配列parentから葉(誰にも参照されていない要素)をみつけ, そこから木をルートの方へたどっていき, 死んだセルにぶつからなければカウントするという方法で十分です. 配列parentの大きさは高々50なので, メモ化などの工夫も必要ありません.

class CellRemoval {
public:
  int ret;
  vector <int> parent;
  int deletedCell;

  int r(int pos) {
    if (pos == -1) {
      ret++;
      return 0;
    } else if (pos == deletedCell) {
      return 0;
    }

    r(parent[pos]);
    return 0;
  }

  int cellsLeft(vector <int> _parent, int _deletedCell) {
    ret = 0;
    parent = _parent;
    deletedCell = _deletedCell;
    int leafs[parent.size()];
    memset(leafs, 0, sizeof(leafs));

    for (int i=0; i<parent.size(); i++)
      if (parent[i] != -1)
        leafs[parent[i]]++;

    for (int i=0; i<parent.size(); i++)
      if (leafs[i] == 0)
        r(i);

    return ret;
  }
};

2010-01-24

SRM 436 div1 (過去問)

15:35

Easy - BestView

いくつかの高さが違うビルが一直線上にならんでいる. ビルの屋上に登って他のビルを見る. もっとも多く他のビルが見えるビルからは, いくつのビルが見えるかを求める.

これは全探索で大丈夫です. ビルAからビルBが見えるかどうかを調べるには, AとBの間にあるビル全ての高さを調べる必要があります. よって計算量は, ビルが50棟あるケースで, だいたい 50 * (1 + 2 + ... 50) = 6万くらい なので全く問題ありません.

class BestView {
public:
  int numberOfBuildings(vector <int> heights) {
    int ret = 0;

    for (int i=0; i<heights.size(); i++) {
      int counter = 0;
      for (int j=0; j<heights.size(); j++) if (i != j) {
          int left = min(i, j), right = max(i, j);
          double ratio = (double)(heights[left] - heights[right]) / (double)(left - right);
          bool visible = true;
          for (int k=left+1; k<right; k++)
            if (heights[k] >= heights[left] + ratio * (k - left)) {
              visible = false;
              break;
            }
          if (visible) counter++;
        }
      ret = max(ret, counter);
    }

    return ret;
  }
};

2010-01-23

SRM 437 div1 (過去問)

14:27

Easy - TheSwap

整数nが与えられるので, 各桁の数字をk回swapした際の最大値を返す.

はじめgreedyにやっていたんですが同じ数字が複数あるケースでfailed system test. たとえば5366を一回スワップするケースを考えると, 5と末尾の6をスワップするのがベストです.

5366 -> 6365 

しかしここで5366を2回スワップするケースを考えます. 上記のアルゴリズムだと 6635となりますが, 最適解は 6653 です.

5366 -> 6365 -> 6635
5366 -> 6356 -> 6653  // optimal

よって今回は全探索してしまうのが正解です. k = 10 の制約があるので間に合うようです. やけにkが小さいなあとは思っていたんですが, 上のような罠には気づきませんでした.

ちなみに計算量は n が最大 1,000,000 k が最大 10 なので, (7C2) ^ 10 = 約16.6兆 となって少し大きいです. よってメモ化しないと間に合いません. メモ化でどのくらい計算量が削減できるのか, 今はちょっとどう考えていいかわからないので, もしこれがコンテスト中だったとしたらサーバでテストしてみる必要があると思います.

class TheSwap {
public:
  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  map <pair <int, int>, int> memo;

  int r(string digits, int k) {
    int ret = -1;
    int n = toInt(digits);

    if (k == 0)
      return n;

    if (memo.count(make_pair(n, k)))
      return memo[make_pair(n, k)];

    for (int i=0; i<digits.size(); i++)
      for (int j=i+1; j<digits.size(); j++) {
        if (i == 0 && digits[j] == 0) continue;
        swap(digits[i], digits[j]);
        ret = max(ret, r(digits, k-1));
        swap(digits[i], digits[j]);
      }

    memo[make_pair(n, k)] = ret;
    return ret;
  }

  int findMax(int n, int k) {
    int ret = 0;
    string digits = toStr(n);

    if (digits.size() == 1 || digits.size() == 2 && digits[1] == '0') return -1;

    ret = r(digits, k);
    
    return ret;
  }
};

2010-01-22

SRM 459 div1 (過去問)

18:49

Medium - NumberPyramids

こんな感じのパスカルの三角形っぽいピラミッドを考える.

   15
  6 9
 3 3 6
2 1 2 4

ピラミッドの一番てっぺんの数字と高さが与えられるので, 何とおりのピラミッドができるか求める.

テストケース1から, baseLength の高さのピラミッドを作るには, top が 2^(baseLength) 以上でないといけないことが分かります. このことと topが最大1,000,000であることを利用して, こんな感じでピラミッドが作ることが不可能なケースを場合分けすることができます.

if (baseLength > 20) return 0;
if ((1 << (baseLength-1)) > top) return 0;

正しいピラミッドでは, (ピラミッドの頂点の値) と (ピラミッドの底辺の数字それぞれに二項係数をかけて総和をとったもの) が等しくなります. このことに気づくための手がかりは, ピラミッドの成り立ちがパスカルの三角形と似ていることから連想することでしょうか (僕は自力では思い付けていません).

この事実を利用すると,

nC0 * a[0] + nC1 * a[1] + ... + nCn * a[n] == top

となるような数列 {a[0], a[1], ..., a[n]} が何通りあるかを求める問題に変わります.

この小問題にはナップザック問題風のdpでアプローチします. topを袋の容量, (nCm*a[m]) をそれぞれのアイテムのようにして考えます.

以下のコードはいろいろな人のコードをみながら書いたものなのですが, まだいまいち完全には理解出来ていないです.

class NumberPyramids {
public:
  long long combination(int n, int r)
  {
    int i, j;
    long long result[r+1], tmp[r+1];

    for (i=0; i<=r; i++) {
      result[i] = 0;
      tmp[i] = 0;
    }

    result[0] = 1;

    for (i=1; i<=n; i++) {
      tmp[0] = 1;

      for (j=1; j<=r; j++)
        tmp[j] = result[j-1] + result[j];

      for (j=0; j<=r; j++)
        result[j] = tmp[j];
    }

    return result[r];
  }

  int count(int baseLength, int top) {
    if (baseLength > 20) return 0;
    if ((1 << (baseLength-1)) > top) return 0;

    int ret = 0;
    int prime = 1000000009;
    int binoms[20];
    int dp[top+1];
    int copy[top+1];

    for (int i=0; i<=top; i++) dp[i] = 1;
    dp[0] = 0;

    for (int i=0; i<baseLength; i++)
      binoms[i] = combination(baseLength-1, i);

    for (int i=0; i<baseLength-1; i++) {
      memset(copy, 0, sizeof(copy));

      int num = binoms[i];
      for (int k=num; k<=top; k++)
        copy[k] = (dp[k - num] + copy[k - num])% prime;

      for (int j=0; j<=top; j++)
        dp[j] = copy[j];
    }

    ret = dp[top];
    return ret;
  }
};

2010-01-19

SRM 459 div1 (寝坊)

04:12

仮眠をとっていたら28分寝過ごしてしまって参加できませんでした. とりあえずeasyだけ解きました.

Easy - Inequalities

"X (不等号) (数字)"という式が複数与えられるので, できるだけ多くの式を満たすようにする. Xは実数, 負の値もとりうる. (数字)は正の整数.

右辺の数字が[0, 1000]で整数のみなので, Xについて[-1, 1001]の範囲を0.5きざみですべて調べるだけで大丈夫です.

class Inequalities {
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;
  }

  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

  int maximumSubset(vector <string> inequalities) {
    int ret = 0;

    for (double i=-1; i<=1001; i+=0.5) {
      int satisfy = 0;
      for (int j=0; j<inequalities.size(); j++) {
        vector <string> res = split(inequalities[j], " ");
        double num = (double)toInt(res[2]);
        if (res[1] == "=") {
          if (i != num) continue;
        } else if (res[1] == "<") {
          if (i >= num) continue;
        } else if (res[1] == "<=") {
          if (i > num) continue;
        } else if (res[1] == ">") {
          if (i <= num) continue;
        } else if (res[1] == ">=") {
          if (i < num) continue;
        }
        satisfy++;
      }
      ret = max(ret, satisfy);
    }

    return ret;
  }
};

2010-01-18

SRM 438 div1 (過去問)

00:34

Easy - UnluckyIntervals

昨日たてた方針を実装. luckySetの各要素のまわりn個だけを調べるようにしました. 仮定が正しかったようで, 無事ローカルのテストが通ったのでサブミット. しかしシステムテストで落ちます. 原因は luckySet の要素の差が1だった場合, それぞれの値が-1になってしまっていました. この点を修正して再提出. 無事通りました.

class UnluckyIntervals {
public:
  vector <int> getLuckiest(vector <int> luckySet, int n) {
    vector <int> ret;
    set <pair <long long, long long> > candidates;
    
    luckySet.push_back(0);
    sort(luckySet.begin(), luckySet.end());

    for (int i=0; i<luckySet.size()-1; i++) {
      candidates.insert(make_pair(0, luckySet[i+1]));
      if (luckySet[i+1] - luckySet[i] == 1) continue;
      long long left = luckySet[i] + 1, right = luckySet[i+1] - 1;
      long long len = right - left + 1;
      long long lim = min(len/2, (long long)n-1);
      for (long long j=0; j<=lim; j++) {
        long long c = len - j - 1;
        for (int k=0; k<j; k++)
          c += (len - k - 1) - (j - k) + 1;
        candidates.insert(make_pair(c, left + j));
        candidates.insert(make_pair(c, right - j));
      }
    }

    int j=0;
    for (set <pair <long long, long long> >::iterator i=candidates.begin(); i!=candidates.end() && j<n; i++, j++)
      ret.push_back(i->second);

    if (ret.size() < n) {
      int N = n - ret.size();
      for (int i=0; i<N; i++)
        ret.push_back(luckySet[luckySet.size()-1]+i+1);
    }
    
    return ret;
  }
};

2010-01-17

SRM 438 div1 (過去問)

00:09

Easy - UnluckyIntervals

問題文は省略.

luckySet 内の要素の範囲に含まれるすべての整数について lucky 度を計算, ソートし, 上からn個を取り出すというストレートな方針をたてました. lucky 度の計算結果を配列に格納しようとしたんですが, この配列のサイズが最大1000000000までになってしまうので, 大きいインプットではメモリ不足でsegment faultします. また, このアプローチでは lucky 度の計算はO(1)でできるのでまあ大丈夫だろうと考えていたんですが, これもよく考えると luckySet の要素は最大1000000000までいくので, メモリが大量にあったとしても時間的に厳しいかなと, あとにして思います.

代替案として, 同様にすべての整数について lucky度を計算し, 今度はその上位n個だけを保存できないか考えました. ただこの方法では上位n個の要素を保持するために, 毎回ソートのような処理が入ってしまうので, 計算時間が厳しそうです.

ここでギブアップしてtopcoder部の方々のブログに助けを求めました. lucky 度は lucky number に近いほど高く遠いほど低くなるということに自分は気づいていませんでいた. この事実を利用すると, lucky number の周囲n個ずつのみを調べてソートすればいいので, 時間と空間の大幅な節約になります. luckySet の要素数は最大50, nは最大100なので, 計算すべき要素は最大 10000 で済みます.

またチャレンジポイントとして, {2} というケースに気づいていなかったので, ここは間違えていた可能性があります. luckySetをソートするという点はきづけたので, ここはよかったです.

以下は修正前のコードです. ローカルテスト4でセグフォルトします. 修正は次回行います.

class UnluckyIntervals {
public:
  vector <int> getLuckiest(vector <int> luckySet, int n) {
    vector <int> ret;
    vector <pair <int, int> > s;

    luckySet.push_back(0);
    sort(luckySet.begin(), luckySet.end());
    int counter[luckySet[luckySet.size()-1]+1];
    memset(counter, 0, sizeof(counter));


    for (int i=0; i<luckySet.size()-1; i++) {
      int left = luckySet[i] + 1, right = luckySet[i+1] - 1;
      int len = right - left + 1;
      for (int j=0; j<=len/2; j++) {
        int c = len - j - 1;
        for (int k=0; k<j; k++)
          c += (len - k - 1) - (j - k) + 1;
        counter[left + j] = c;
        counter[right - j] = c;
      }
    }

    for (int i=1; i<=luckySet[luckySet.size()-1]; i++)
      s.push_back(make_pair(counter[i], i));
    sort(s.begin(), s.end());
    
    int lim = min(n, (int)s.size());
    for (int i=0; i<lim; i++)
      ret.push_back(s[i].second);

    if (ret.size() < n) {
      int N = n - ret.size();
      for (int i=0; i<N; i++)
        ret.push_back(luckySet[luckySet.size()-1]+i+1);
    }
    
    return ret;
  }
};

2010-01-16

Member SRM 458 div1 (過去問)

21:44

Medium - NewCoins

top submissionを見ながら. dp[i]には"iが最小のコインだったとき必要な枚数"を保存します. 例えば, j (jはiの倍数) のコインで price の商品を買う場合, price / j + price % j / i 個のコインが必要です. これをdpで上から計算して行きます.

class NewCoins {
public:
  int minCoins(vector <int> price) {
    int dp[100001];
    memset(dp, 0, sizeof(dp));

    for (int i=100000; i>=1; i--) {
      for (int j=0; j<price.size(); j++)
        dp[i] += price[j] / i;

      for (int j = i+i; j<=100000; j+=i) {
        int tmp = dp[j];
        for (int k=0; k<price.size(); k++)
          tmp += price[k] % j / i;
        dp[i] = min(dp[i], tmp);
      }
    }

    return dp[1];
  }
};

2010-01-15

Project Euler

00:27

f:id:cou929:20100116002718j:image

なんとなくProject Eulerに手を出してみました.

About - Project Euler

問題は全部で200問以上あるようです. 回答は結果だけをはりつけ, コードの提出はありません. 問題に正解できると, その問題の解説とforumにアクセス出来るようになります.

とりあえず問題1と2を解いてみました. といっても非常に簡単な問題なので, いちいち書く必要もないかもしれないです.

Problem 1

no title

1000以下の自然数のうち, 3か5の倍数の総和を求めよ.

そのままです. perlのワンライナーでやりました.

% perl -le '$ret = 0; for ($i=0; $i<1000; $i++){if ($i % 3 == 0 || $i % 5 == 0) {$ret += $i;}} print $ret;'

Problem 2

no title

最初が1, 2からはじまるフィボナッチ数列において, 要素の大きさが4,000,000のもののうち, 偶数である要素の総和を求める.

これもそのままです.

% perl -le '$ret=2; @pre=(1,2); while(1){$new=$pre[0]+$pre[1]; if ($new >= 4000000) {last;} if($new%2==0){$ret+=$new;} $pre[0]=$pre[1]; $pre[1]=$new;} print $ret;'

とりあえず雰囲気はわかりました. これから暇なときにやっていこうかと思います.

2010-01-14

Member SRM 458 div1

03:43

250だけできました. div1で367位, ratingは1230 -> 1286 (+56). 悪くない結果ですが, 250が解けた時点で自分の中で満足しちゃってたのが良くなかったです.

Easy - BouncingBalls

直線上にボールがいくつかおいてある. ボールは半径0でそれぞれ線に沿って右か左にのみ移動する. 等速直線運動で移動し, べつのボールにぶつかったときは方向だけ反転させまた同じ速度で移動する. ボールの位置と時刻Tが与えられるので, 衝突の回数の期待値を求めよ.

重要な点は, ボールはすべて等速直線運動であるということです. よって, 2つのボールが互いに互いの方向へ移動しているとします. ボール間の距離が2T以下ならこれらのボールは衝突します. ボールの間に別のボールがあっても関係ありません. またボールの数は高々12なので, 2^12 = 4096 通りだけ調べればいいことになります. よってすべての場合を全探索して, 前述の方法でボールの衝突回数を調べればokです.

class BouncingBalls {
public:
  double expectedBounces(vector <int> x, int T) {
    double ret = 0;
    sort(x.begin(), x.end());

    for (long long i=0; i<(1 << x.size()); i++) {
      long long tmp = i;
      for (int j=0; j<x.size(); j++)
        if ((tmp >> j) & 1)
          for (int k=j+1; k<x.size(); k++)
            if (!((tmp >> k) & 1))
              if ((double)(x[k] - x[j]) / 2.0 <= (double)T)
                ret++;
    }

    ret /= (1 << x.size());
    return ret;
  }
};

Medium - NewCoins

わかりませんでした. 眠いので明日やります.

Hard - ModuloFourDivisor

開けてません.

challenge phase

250が解けたことでわりと満足しちゃってたので, あまり参加しませんでした. もっと上を狙っていかないとだめです.



SRM 440 div1 (過去問)

10:17

Easy - IncredibleMachine

ボールを坂道のてっぺんに置いて, 初速0で転がす. 坂の角度が変わる点がx, yの座標で与えられる. ボールは時刻0に転がり始め, 時刻Tに地面につく. 重力加速度を求めよ.

連立方程式をたて, バイナリサーチで求めます. 連立方程式は高校レベルの物理の力学と, 解の公式を思い出せれば問題ないはずです.

class IncredibleMachine {
public:
  vector <vector <double> > planes;  // length, sin(alpha)
  double calcTimes(double g) {
    double ret = 0;
    double initial_velocity = 0;
    double acceleration = 0;
    double time = 0;

    for (int i=0; i<planes.size(); i++) {
      acceleration = g * planes[i][1];
      time = (-initial_velocity + sqrt(initial_velocity*initial_velocity + 2 * acceleration * planes[i][0])) / acceleration;
      initial_velocity = initial_velocity + acceleration * time;
      ret += time;
    }

    return ret;
  }

  double gravitationalAcceleration(vector <int> x, vector <int> y, int T) {
    double ret = 0;
    double left = 0, right = 1e20, mid = 0;
    planes.clear();
    
    for (int i=0; i<x.size()-1; i++) {
      vector <double> tmp(2, 0);
      tmp[0] = sqrt((x[i] - x[i+1]) * (x[i] - x[i+1]) + (y[i] - y[i+1]) * (y[i] - y[i+1]));
      tmp[1] = abs(y[i] - y[i+1]) / tmp[0];
      planes.push_back(tmp);
    }

    for (int i=0; i<1000; i++) {
      mid = (left + right) / 2;
      double t = calcTimes(mid);
      if (t < T)
        right = mid;
      else
        left = mid;
    }

    ret = mid;
    return ret;
  }
};

2010-01-13

SRM 441 div1 (過去問)

16:32

Easy - PerfectPermutation

数列AとBの関係は次のように定義されている.

  1. B[0] = 0
  2. B[i] = A[B[i-1 (iの範囲は[1, A.size()-1])

また数列Aはpermutationである([0, A.size()-1] までの数の並べ替えになっている). 数列Pが与えられるので, 次の条件を満たす数列Qを求め, PとQの差を返す.

  • Qに対する配列Bもpermutationになっている
  • PとQの差が最小
    • 差の定義はP[i], Q[i]の値が違う要素の個数


ひらめきが重要な問題です. 以下の2つの事実に気がつく必要があります.

  1. 数列Aの数字がループしていれば, 数列Bはpermutationである
  2. ループが閉じている2つの数列をつなぐには, 数字のswapが一回必要

1に関して, 数列のある要素を次のインデックスと考え数列をどんどんたどっていくことができます. たとえば{2, 0, 1}は

index element
    0       2  -> 次は 2
    2       1  -> 次は 1
    1       0  -> 次は 0

このようにループしています. このような数列に対するBはpermutationになっています.

2に関して, 閉じた2つのループは, それぞれの中から1つずつ要素をとりだし, それをswapすればつながります.

以上の事実を用いると, 与えられた数列のなかにいくつのループがあるかを数えるだけで答えが求まります.

ふつうに探索してもケース数が多すぎて間に合いません. 上記の事実に気がつく必要があるんですが, ぼくはひらめくことができませんでした. このひらめきの力は, もっといろいろな問題を解いたり, あるいはアルゴリズムに限らずいろいろな開発を経験することでしかつかないんじゃないかなと思いました. 地道に継続するしかないです. まだまだ"やわらか頭脳"には遠いですね.

no title

class PerfectPermutation {
public:
  vector <int> P;
  int visited[50];

  int dfs(int pos) {
    if (visited[pos] == 0) {
      visited[pos] = 1;
      dfs(P[pos]);
    }
    return 0;
  }

  int reorder(vector <int> _P) {
    int ret = 0;
    P = _P;
    memset(visited, 0, sizeof(visited));

    for (int i=0; i<P.size(); i++)
      if (visited[i] == 0) {
        dfs(i);
        ret++;
      }
    
    if (ret == 1) ret--;
    return ret;
  }
};

2010-01-12

SRM 444 div1 (過去問)

01:14

Easy - UnfoldingTriangles

'.', '#', '/'からなるグリッドが与えられる. '.'は空白, '#'は真っ黒なセルで, '/'は左下が黒く塗りつぶされた三角形を表している. '/'を unfoldLimit 個 '#' に変化させられる. この条件のもとで最大の三角形のサイズを求めよ.

方針としては straightforward な探索です. ループで1セルずつ, そのセルが直角三角形の直角の部分(三角形の右下)だと仮定し, その場合の最大サイズを求めます. この計算結果全体の最大値を返します.

実装は少々面倒です. まずループを書きやすくするために, gridを反転させます. 反転させたグリッドを1セルずつ操作します. 各セルについて, 三角形の長さを1から大きくしていき, その長さで三角形が成り立っているかを調べます. 三角形の判定は, 1)三角形の中に空白は存在してはいけない 2)斜辺は必ず'/' 3)斜辺じゃない辺に接するセルは'#'であってはいけない 4)三角形の中にある'/'の数が unfoldLimit 以下である. この4つの条件で調べます. すべてを満たすものが有効な三角形です. また今回は2重ループを抜けるためにgotoを使ってみました.

class UnfoldingTriangles {
public:
  vector <string> grid;

  bool isInRange(int x, int y) {
    if (0 <= x && x < grid.size() && 0 <= y && y < grid[0].size())
      return true;
    return false;
  }

  int solve(vector <string> _grid, int unfoldLimit) {
    int ret = 0;
    grid = _grid;

    for (int i=0; i<grid.size(); i++)
      reverse(grid[i].begin(), grid[i].end());
    reverse(grid.begin(), grid.end());

    for (int cur_row=0; cur_row<grid.size(); cur_row++) {
      for (int cur_col=0; cur_col<grid[cur_row].size(); cur_col++) {
        int limit = min(grid.size() - cur_row, grid[0].size() - cur_col);
        int max_size = 0;
        for (int length=1; length<=limit; length++) {
          int ulim = unfoldLimit;
          bool isValid = true;

          // loop as a triangle shape
          for (int i=0; i<length; i++)
            for (int j=0; j<length-i; j++) {
              char cur_grid = grid[cur_row + i][cur_col + j];
              // '.' grid not allowed
              if (cur_grid == '.') {
                isValid = false;
                goto ENDLOOP;
              }
              // hypotenuse grids must be '/'
              if (j == length-i-1 && cur_grid != '/') {
                isValid = false;
                goto ENDLOOP;
              }
              // grids which shares a side with triangle must not be '#'
              if (i == 0)
                if (isInRange(cur_row + i - 1, cur_col + j) && grid[cur_row + i - 1][cur_col + j] == '#') {
                  isValid = false;
                  goto ENDLOOP;
                }
              if (j == 0)
                if (isInRange(cur_row + i, cur_col + j - 1) && grid[cur_row + i][cur_col + j - 1] == '#') {
                  isValid = false;
                  goto ENDLOOP;
                }
              // grids which is in triangle and equal to '/' must be unfolded
              if (cur_grid == '/' && j < length-i-1)
                ulim--;
              if (ulim < 0) {
                isValid = false;
                goto ENDLOOP;
              }
            }
        ENDLOOP:
          // update max size
          if (isValid) {
            int cur_size = 0;
            for (int i=1; i<=length; i++) cur_size += i;
            max_size = max(max_size, cur_size);
          }
        }
        ret = max(ret, max_size);
      }
    }

    if (ret == 0) ret = -1;
    return ret;
  }
};

2010-01-11

SRM 445 div1 (過去問)

18:46

Easy - TheNewHouseDivOne

直交座標系での位置がいくつか与えられる. これらの位置とのマンハッタン距離を昇順に並べ, k番目にくる値が最小になるような位置を求め, その時のk番目の距離を返す.

基本的にはグリッド上のすべての点について距離を計算して最短値を探せば大丈夫です. しかし, 問題文は答えを実数で返すよう要求しているのですが, なぜ実数になり得るのかがわかりませんでした. というのも new house の座標は整数しかとらないと思い込んでいたからです. 座標に実数を許すようにすると, 当然ですがマンハッタン距離も実数になる場合が出てくるし, テストケースの筋も通ります. 次に old house の位置と k の値について思いつく限りの状況を考えてみたのですが, 解が 0.5 よりも細かくなることはなさそうという結論になりました. よって [-50, 50] の範囲を 0.5 きざみで探索するアルゴリズムに変更. x, y が50要素ある最大ケースで試してみたところ時間は間に合いそうなのでそのままsubmitしました.

class TheNewHouseDivOne {
public:
  double calcDistance(double x1, double y1, double x2, double y2) {
    return abs(x1 - x2) + abs(y1 + y2);
  }

  double distance(vector <int> x, vector <int> y, int k) {
    double ret = DBL_MAX;

    for (double i=-50; i<=50; i+=0.5)
      for (double j=-50; j<=50; j+=0.5) {
        vector <double> distances;
        for (int l=0; l<x.size(); l++)
          distances.push_back(calcDistance(i, j, x[l], y[l]));
        sort(distances.begin(), distances.end());
        ret = min(ret, distances[k-1]);
      }

    return ret;
  }
};

2010-01-10

Member Beta div1 (過去問)

17:00

Easy - ErdosNumber

論文の著者リストが与えられる. 著者間の距離を(共著者の中の最小距離値 + 1)と定義する. ERDOS氏の距離を0とし, 他の著者の距離を求めよ.

単純なbfsです. グラフを作ったりするのが少し面倒ですが, ストレートに実装すればできます.

class ErdosNumber {
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;
  }

  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  vector <string> calculateNumbers(vector <string> publications) {
    vector <string> ret;
    map <string, int> numbers;
    map <string, int> index;
    typedef map <string, int>::iterator it;
    queue <pair <int, int> > q;

    for (int i=0; i<publications.size(); i++) {
      vector <string> tmp = split(publications[i], " ");
      for (int j=0; j<tmp.size(); j++) numbers[tmp[j]] = (tmp[j] == "ERDOS") ? 0 : INT_MAX;
    }

    int ind=0;
    for (it i=numbers.begin(); i!=numbers.end(); i++, ind++)
      index[i->first] = ind, ret.push_back(i->first);

    int graph[numbers.size()][numbers.size()];
    memset(graph, 0, sizeof(graph));

    for (int i=0; i<publications.size(); i++) {
      vector <string> tmp = split(publications[i], " ");
      for (int j=0; j<tmp.size(); j++)
        for (int k=0; k<tmp.size(); k++)
          if (j != k)
            graph[index[tmp[j]]][index[tmp[k]]] = 1;
    }

    q.push(make_pair(index["ERDOS"], 0));
    while (!q.empty()) {
      pair <int, int> cur = q.front();
      q.pop();
      int cur_pos = cur.first, cur_num = cur.second;

      for (int i=0; i<numbers.size(); i++) {
        if (graph[cur_pos][i] == 1 && numbers[ret[i]] == INT_MAX) {
          numbers[ret[i]] = cur_num + 1;
          q.push(make_pair(i, cur_num + 1));
        }
      }
    }

    ret.clear();
    for (it i=numbers.begin(); i!=numbers.end(); i++, ind++) {
      string tmp = i->first;
      if (i->second != INT_MAX) tmp += " " + toStr(i->second);
      ret.push_back(tmp);
    }

    return ret;
  }
};

2010-01-09

SRM448 div1 (過去問)

20:50

Div1の問題むずかしいなあ…

Easy - TheBlackJackDivOne

ブラックジャックをプレイしている. 現在の手札が与えられる. スコアが21を越すまで何回でもデッキからカードを引ける. カードを引く回数の期待値を求めよ.

まず計算量を見積もろうと思ったんですが, いまいちよくわからなかったので, なんとなく多そうだなと勝手に結論づけ, 全探索のアプローチを捨ててしまいました. これが大間違いで, そのあと別の手法を考えていたんですが全く思いつかず, 時間を無駄にしました. editorialによると, 状態数はだいたい40000なので全探索をするとのこと. なぜ40000なのかはまだわかってません. いちばん時間がかかると思われるテストケースは{2S}などです. なので, まず組んでみてサーバ上でこのテストケースを投げてみるというのが, コンテスト中だったら現実的な対応だと思います.

以下のコードはACRushのtop submissionなどを見ながら書いたものです. 現在のカードの使用状況を表すベクタと現在のスコアを引数にとる再帰関数で探索しています.

なぜ期待値の計算が

ret += (c[i] + 1.0) / total * (r(c, sum + i) + 1.0);

こういうふうになっているのかについては, forumのpivaのpostがわかりやすかったです. 以下引用.

It is possible to express expected value as a recursive function by using the definition of the expected value for discrete random variables. If X is the random variable that represents the number of cards drawn, then:

E[X] = Sum(x * prob(x)) over all possible values of x, that ranges from 1 to 9 in the problem, since he won't ever draw more than 9 cards.

Also notice that prob(x) is the sum of the probabilities of all possible ending hands with x cards drawn. That's why one solution was to backtrack for all possible hands, with each hand contributing (probability of the hand)*(cards drawn) to the expected value.

class TheBlackJackDivOne {
public:
  double r(vector <int> c, int sum) {
    double ret = 0;
    double total = 0;

    if (sum >= 21) return ret;
    for (int i=0; i<c.size(); i++) total += c[i];
    
    for (int i=0; i<c.size(); i++)
      if (c[i] > 0) {
        c[i]--;
        ret += (c[i] + 1.0) / total * (r(c, sum + i) + 1.0);
        c[i]++;
      }

    return ret;
  }

  double expected(vector <string> cards) {
    double ret = 0;
    vector <int> remind(12, 4);
    remind[0] = 0, remind[1] = 0, remind[10] = 16;
    int sum = 0;

    for (int i=0; i<cards.size(); i++) {
      char n = cards[i][0];
      int index = 0;
      if (2 <= n - '0' && n - '0' <= 9)
        index = n - '0';
      else if (n == 'A')
        index = 11;
      else
        index = 10;

      remind[index]--;
      sum += index;
    }

    ret = r(remind, sum);

    return ret;
  }
};

2010-01-08

SRM449 div1 (過去問)

01:04

Easy - MaxTriangle

三角形の二辺の長さが整数A, Bで与えられる. 三角形の3つの頂点がどれも2次元座標系の整数の点に置かれる場合, 三角形の最大の面積を求めよ.

整数A, B それぞれについて, A = x^2 + y^2 となるようなx, yの組み合わせをすべて求めます. この組み合わせの求め方は, int i を0からi*i<20,000,000,00 までループさせ, sqrt(A - i*i) が整数になるかどうかをチェックすれば大丈夫です. iは4万5千回弱なので十分間に合います. あとはこれらのすべての組み合わせ(符号の正負も含めて)について三角形の面積を計算して, 最大値を返します. 三角形の面積の求め方には色いろあるんですが, 今回の場合は以下のwikipediaのページに載っている"3.5 直交座標による式"の方法が便利です.

三角形 - Wikipedia

class MaxTriangle {
public:
  double calcArea(int x1, int y1, int x2, int y2) {
    return abs(((double)x1*(double)y2 - (double)x2*(double)y1)/2.0);
  }

  double calculateArea(int A, int B) {
    double ret = 0;
    int lim = max(A, B);
    vector <pair <int, int> > canA, canB;
    int tmp = 0, remA = 0, remB = 0;

    for (int i=0; i<44722 && i*i<=lim; i++) {
      tmp = i*i;
      remA = A - tmp, remB = B - tmp;
      if (remA >= 0 && sqrt(remA) == (int)sqrt(remA)) {
        canA.push_back(make_pair(i, (int)sqrt(remA)));
        canA.push_back(make_pair(-i, (int)sqrt(remA)));
        canA.push_back(make_pair(i, -(int)sqrt(remA)));
        canA.push_back(make_pair(-i, -(int)sqrt(remA)));
      }
      if (remB >= 0 && sqrt(remB) == (int)sqrt(remB)) {
        canB.push_back(make_pair(i, (int)sqrt(remB)));
        canB.push_back(make_pair(-i, (int)sqrt(remB)));
        canB.push_back(make_pair(i, -(int)sqrt(remB)));
        canB.push_back(make_pair(-i, -(int)sqrt(remB)));
      }
    }

    if (canA.size() == 0 || canB.size() == 0)
      return -1;

    for (int i=0; i<canA.size(); i++)
      for (int j=0; j<canB.size(); j++)
        ret = max(ret, calcArea(canA[i].first, canA[i].second, canB[j].first, canB[j].second));

    return ret;
  }
};

2010-01-07

SRM390 div2 (過去問)

15:45

Easy - FingerCounting

片手で数を数える. 例えば10まで数えるときは, "親指, 人差し指, 中指, 薬指, 小指, 薬指, 中指, 人差し指, 親指, 人差し指" となる. ある指がn回までしか使えないとすると, この方法で最大いくつまで数えられるか.

各指で数える数字を列挙してみると以下になります. (1:親指, 2:人差し指, 3:中指, 4:薬指, 5:小指)

 1  2  3  4  5
---------------
 1  2  3  4  5
    8  7  6
 9 10 11 12 13
   16 15 14
17 18 19 20 21
   24 23 22
...

これを見ると, それぞれの指は次のような数列になっています.

  1. 等差8の数列
  2. 差が6, 2, 6, 2 ... の数列
  3. 等差4の数列
  4. 差が2, 6, 2, 6 ... の数列
  5. 等差8の数列

あとはこの法則に従って求めるだけです.

class FingerCounting {
public:
  int maxNumber(int weakFinger, int maxCount) {
    int ret = 0;
    int rule[5][2] = {{8, 0}, {6, 2}, {4, 0}, {2, 6}, {8, 0}};

    if (maxCount == 0)
      return weakFinger - 1;

    if (weakFinger == 1 || weakFinger == 3 || weakFinger == 5)
      ret = weakFinger + maxCount * rule[weakFinger-1][0] - 1;
    else {
      if (maxCount % 2 == 0)
        ret = weakFinger + (maxCount / 2) * rule[weakFinger-1][0] + (maxCount / 2) * rule[weakFinger-1][1] - 1;
      else
        ret = weakFinger + (maxCount / 2 + 1) * rule[weakFinger-1][0] + (maxCount / 2) * rule[weakFinger-1][1] - 1;
    }

    return ret;
  }
};

Medium - ConcatenateNumber

整数 number と k が与えられる. number をいくつつなげると k の倍数になるか求める. 出来ない場合は -1 を返す.

自力では解けず, editorialを見ました.

まず自分で考えたことから. 一番ナイーブな方法は number % k == 0 になるまで number をつなげていく方法です. しかしテストケース3で明らかなように, 巨大な整数になるので不可能です. またワーストケースでいくつくらいになるかもわかりません. 次に k の方を乗じていき, その結果が number の数字だけで出来ているかをチェックする方法も考えたんですが, あきらかにステップ数が多すぎるので不可能です. 次は number % k の結果の数列の法則性をみつけ, number % k == 0 となるインデックスを探そうと思い, 例えばテストケース3で試してみたのですが, こちらも見つけられませんでした.

35 % 98765 = 35
3535 % 98765 = 3535
353535 % 98765 = 57240
35353535 % 98765 = 94430
3535353535 % 98765 = 60360
353535353535 % 98765 = 11370
35353535353535 % 98765 = 50620
3535353535353535 % 98765 = 25020

ここでギブアップしてeditorialに頼りました. いわく, "b[i]=(b[i-1] * 10m + number) mod k" を b[i] == 0 が見つかるまで繰り返す. こうすれば値が巨大にならずにすむとのこと. 確かにその通りです. そして大きな数の mod を扱う際は, 毎回 mod をとってオーバーフローを防ぐというのは定石でした. 去年の gcj の時に学んだはずなんですが, 活かせなかったです. ちなみにこの法則のジャンルは数論 (number theory) だそうで, あとで押さえておきたいと思います.

【追記】

このテクニックについて説明されている記事です.

no title

【追記おわり】

また見つからない場合(-1を返す場合)をどう検出するかですが, これは mod k の結果のループを検出すればokです. ぼくはストレートにsetをつかってやったのですが, n mod k の値は必ず [0, k) の範囲に入ることから, 単純に [0, k) の範囲をすべてループさせるというのがはやくて良いかもしれません.

class ConcatenateNumber {
public:
  int getSmallest(int number, int k) {
    int ret = 1;
    long long mod = 0;
    set <long long> s;
    long long p = 1;

    if (number % k == 0)
      return 1;

    while (p <= number)
      p *= 10;

    mod = number % k;

    while (mod != 0) {
      s.insert(mod);
      mod = (mod * p  + number) % k;
      ret++;
      if (s.find(mod) != s.end())
        return -1;
    }

    return ret;
  }
};

2010-01-06

TCO2003 Online Round 4 (過去問)

01:34

Medium Jewelry

dpの練習シリーズ. 宝石をfrankとbobの2人にわける. 2人の宝石の価値の総額がおなじになるように, かつfrankの宝石の一番安い値段とbobの宝石の一番高い値段異常になるように分ける. 何とおりの分け方があるか.

次のアルゴリズムを考えたんですが, うまくいきませんでした. 二次元配列を二つ作って, ひとつには要素[i][j]に合計値がiでそれを構成する要素の"最小値"がjとなる組み合わせの数を, もうひとつには要素[i][j]に合計値がiでそれを構成する要素の"最大値"がjとなる組み合わせの数を保存します. iが等しくて 最小値 > 最大値 となるようなセルを探してカウントしていくという方法です. しかし現状テストケース0, 2しか通っていません. 今日はもう眠いので後日続きをやりたいです.

class Jewelry {
public:
  long long howMany(vector <int> values) {
    long long ret = 0;
    int total = 0;
    for (int i=0; i<values.size(); i++) total += values[i];
    sort(values.begin(), values.end());
    long long memo_min[total+1][values[values.size()-1]+1];
    long long memo_max[total+1][values[values.size()-1]+1];
    long long update_min[total+1][values[values.size()-1]+1];
    long long update_max[total+1][values[values.size()-1]+1];
    memset(memo_min, 0, sizeof(memo_min));
    memset(memo_max, 0, sizeof(memo_max));
    memset(update_min, 0, sizeof(update_min));
    memset(update_max, 0, sizeof(update_max));
    int n = total, m = values[values.size()-1];

    for (int i=0; i<values.size(); i++) {
      update_min[values[i]][values[i]]++;
      update_max[values[i]][values[i]]++;
      for (int row=1; row<=n; row++)
        for (int col=1; col<=m; col++) {
          if (memo_min[row][col] > 0) 
            update_min[row+values[i]][col] += memo_min[row][col];
          if (memo_max[row][col] > 0)
            update_max[row+values[i]][values[i]] += memo_max[row][col];
        }
      for (int row=0; row<=n; row++)
        for (int col=0; col<=m; col++)
          memo_min[row][col] = update_min[row][col], memo_max[row][col] = update_max[row][col];
    }

    for (int row=0; row<=n; row++) {
      for (int col=0; col<=min(row, m); col++) {
        if (row == col)
          ret += (memo_min[row][col] / 2) * 2;

        if (memo_min[row][col] > 0) {
          for (int i=0; i<min(row, m); i++)
            if (memo_max[row][i] > 0) {
              if (col > i) {
                ret += memo_min[row][col] * memo_max[row][i];
              }
            }
        }
      }
    }
    return ret;
  }
}

2010-01-05

SRM457 div1 (過去問)

01:16

Medium - TheHexagonsDivOne

7マスの六角形からなるフィールドに2*n個の数字を並べる. 隣り合うマスをa, bとしたとき, a%n != b%n としなくてはいけない. nが与えられるので何とおりの置き方があるか求める. ただし回転させると同じになる並びは同一とみなす.

まずn*2なので, おなじ mod n の値をもつ数字は必ず2つずつあります. 次に回転を同一視するためには, まずは回転を考えずに計算し, 最後に6で割ればokです. また真ん中のマスはすべてのマスと隣り合っているので, 真ん中にある数字をおくとその数字と同じmod nであるもうひとつの数字は使えなくなります. そうなると6マスをどう埋めるかという問題になります. ここまではわかったんですが, では実際どのように6マスの並べ方を求めるか, 良い方法が思いつきませんでした.

forumを見ると, dpで計算する方法や, 高々6マスなので手計算パターンを列挙しで数式を導き出す方法が紹介されていました. とりえずパターン列挙系の方法を実装したのが以下のコードです. 6つのマスの中に, 同じmod nの値のペアがいくつあるかで場合分けしているのがなるほどと思いました. 例えば6つの値すべてが違うmod nの値の場合は0ペアです. この発想の転換はできませんでた.

ただどっちにしろ今回は本番中にはできなかったので, 他の問題への練習という観点から考えると, この解法よりもdpでの解法で解いた方が身になると思います. 余裕があればdpの方法も考えてみたいです.

class TheHexagonsDivOne {
public:
  long long count(int n) {
    long long ret = 0;
    long long N = n;

    if (n < 4) return ret;

    if (n >= 4)
      ret += 4 * 2 * 2 * 2 * 2 * N * (N-1) * (N-2) * (N-3);

    if (n >= 5)
      ret += 18 * 2 * 2 * 2 * 2 * 2 * N * (N-1) * (N-2) * (N-3) * (N-4);

    if (n >= 6)
      ret += 9 * 2 * 2 * 2 * 2 * 2 * 2 * N * (N-1) * (N-2) * (N-3) * (N-4) * (N-5);

    if (n >= 7)
      ret += 2 * 2 * 2 * 2 * 2 * 2 * 2 * N * (N-1) * (N-2) * (N-3) * (N-4) * (N-5) * (N-6);

    ret /= 6;

    return ret;
  }
};

2010-01-04

SRM457 div1

00:02

250がシステムテスト落ち. 500, 1000は開けてません. スコアは0ポイントで, ratingは 1240 -> 1230 (-10) でした.

Easy - TheTriangleBothDivs

"10:30 GMT+9"のような形式で時刻が与えられる. ただし"GMT"意外の部分は"?"となっていてる場合がある. とりうる時刻のうち辞書順で最も若いものを返す. GMTの表記は"GMT-9"から"GMT+9"の範囲で, 0の場合は"GMT+0"となり"GMT-0"とはならない.

アルゴリズム的な難しさは全くないんですが, ふつうにやろうとすると場合分けが多くなってしまってバグりやすくなります. 以下はコンテスト後に全部書き直したコードです. すべての時刻を調べて, 条件にマッチしているものの中から最小のものを探すようにしました.

class TheTriangleBothDivs {
public:
  string fix(string time) {
    string ret = "23:59";
    char s[11];

    for (int h=0; h<24; h++)
      for (int m=0; m<60; m++)
        for (int g=-9; g<10; g++) {
          if (g < 0)
            sprintf(s, "%02d:%02d GMT-%d", h, m, abs(g));
          else
            sprintf(s, "%02d:%02d GMT+%d", h, m, g);

          int i;
          for (i=0; i<time.size(); i++)
            if (time[i] != '?' && time[i] != s[i])
              break;

          if (i == time.size()) {
            sprintf(s, "%02d:%02d", (h-g+24)%24, m);
            ret = min(ret, string(s));
          }
        }

    return ret;
  }
};

ちなみにこれがコンテスト中に書いたひどいコードです. goto とか使ってます. コンテスト後に少し修正したので一応システムテストは通ります.

class TheTriangleBothDivs {
public:
  string fix(string time) {
    string ret
    set <string> candidates;

    for (int h1=0; h1<3; h1++) {
      string can;
      if (time[0] == '?') can += '0' + h1;
      else can += time[0];
      for (int h2=0; h2 < 10; h2++) {
        int left = 0, right = 0;
        if (time[1] == '?') can += '0' + h2;
        else can += time[1];
        if (can[0] == '2' && can[1] > '3') goto END;

        can += ':';
        if (time[3] == '?') can += '0';
        else can += time[3];
        if (time[4] == '?') can += '0';
        else can += time[4];


        if (time[9] == '?' && time[10] != '?') {
          int n = time[10] - '0';
          int hour = (can[0] - '0') * 10 + can[1] - '0';
          int next_hour = (hour + n) % 24;
          if (hour + n < 0) next_hour = 24 - abs(hour + n);
          string tmp = can;
          tmp[0] = next_hour / 10 + '0';
          tmp[1] = next_hour % 10 + '0';
          candidates.insert(tmp);
          next_hour = (hour - n) % 24;
          if (hour - n < 0) next_hour = 24 - abs(hour - n);
          tmp[0] = next_hour / 10 + '0';
          tmp[1] = next_hour % 10 + '0';
          candidates.insert(tmp);
          goto END;
        } else if (time[9] != '?' && time[10] != '?') {
          int n = time[10] - '0';
          if (time[9] == '+') n *= -1;
          int hour = (can[0] - '0') * 10 + can[1] - '0';
          int next_hour = (hour + n) % 24;
          if (hour + n < 0) next_hour = 24 - abs(hour + n);
          string tmp = can;
          tmp[0] = next_hour / 10 + '0';
          tmp[1] = next_hour % 10 + '0';
          candidates.insert(tmp);
          goto END;
        }

        if (time[9] == '?' && time[10] == '?') {
          left = -9, right = 9;
        } else if (time[9] != '?' && time[10] == '?') {
          if (time[9] == '-')
            left = 1, right = 9;
          else
            left = -9, right = 0;
        }

        for (int i=left; i<=right; i++) {
          int hour = (can[0] - '0') * 10 + can[1] - '0';
          int next_hour = (hour + i) % 24;
          if (hour + i < 0) next_hour = 24 - abs(hour + i);
          string tmp = can;
          tmp[0] = next_hour / 10 + '0';
          tmp[1] = next_hour % 10 + '0';

          candidates.insert(tmp);
        }
      END:
        string tmp = can;
        can.clear();
        can += tmp[0];
      }
    }

    for (set <string>::iterator i=candidates.begin(); i!=candidates.end(); i++)
      cout << *i << endl;
    ret = *(candidates.begin());;
  }
};

Medium - TheHexagonsDivOne

開けてません.

Hard - TheSquareDivOne

開けてません.

Challenge phase

"GMT-0"という表記がありえないというのがチャレンジポイントかと思って他の人のコードを読み始めたんですが, みんなコードが長くて読むのが難しくチャレンジできませんでした. 結局システムテストに落ちていた人が何人もいました.

2010-01-03

Member Pilot 2 div1 (過去問)

01:26

Easy - TwistedMatrix

要素が1, 0からなる行列A, Bが与えられる. BはAを一回twistさせてできた行列である. twist は行列中の2x2の部分行列に注目して, その4つの要素を時計回り・反時計回りに回転させる操作である. 与えられる行列A, Bは不完全で, ?となっている要素がある. ?は0か1のどちらかわからない要素である. Bの完全な形を求めよ. 候補が複数ある場合は辞書順で若いものを, 不可能な場合は空の行列を返す.

行列の大きさは最大で30. 回転は必ず一度なので, ワーストケースで 29*29*2 = 1682通りのパターンが有ります. よって全探索で間に合いそうです. すべての位置でAを時計回り・反時計回りに回転させ, Bに合致しているか調べ, しているもののなかから辞書順で最も若いものを返します.

vector <string> (10, (string (10, '1'))) こういう風にするとすべての要素が'1'で大きさが10x10の無名の vector <string> を作ることができて, 初期化などに使えます. これは便利だ.

class TwistedMatrix {
public:
  vector <string> A, B;

  vector <string> rotate(int row, int col, int next) {
    // next is 3 if clockwise direction, 1 if counterclockwise direction
    //
    // rotate clockwise direction
    // next[row][col] = prev[row+1][col];
    // next[row][col+1] = prev[row][col];
    // next[row+1][col+1] = prev[row][col+1];
    // next[row+1][col] = prev[row+1][col+1];
    //
    // rotate counterclockwise direction
    // next[row][col] = prev[row][col+1];
    // next[row][col+1] = prev[row+1][col+1];
    // next[row+1][col+1] = prev[row+1][col];
    // next[row+1][col] = prev[row][col];

    vector <string> ret = A;
    int dir_row[4] = {0, 0, 1, 1};
    int dir_col[4] = {0, 1, 1, 0};

    for (int i=0; i<4; i++)
      ret[row+dir_row[i]][col+dir_col[i]] = A[row+dir_row[(i+next)%4]][col+dir_col[(i+next)%4]];

    return ret;
  }

  bool check(vector <string> &rotated) {
    for (int i=0; i<rotated.size(); i++)
      for (int j=0; j<rotated[0].size(); j++) {
        if (rotated[i][j] == '?')
          if (B[i][j] == '?')
            rotated[i][j] = '0';
          else
            rotated[i][j] = B[i][j];
        else if (B[i][j] == '?')
          continue;
        else if (rotated[i][j] != B[i][j])
          return false;
      }

    return true;
  }

  vector <string> solve(vector <string> _A, vector <string> _B) {
    A = _A, B = _B;
    vector <string> initial(A.size(), (string (A[0].size(), '2')));
    vector <string> ret = initial;
    vector <string> rotated;

    for (int row=0; row<A.size()-1; row++)
      for (int col=0; col<A[0].size()-1; col++) {
        rotated = rotate(row, col, 3);  // clockwise
        if (check(rotated) && rotated < ret) ret = rotated;
        rotated = rotate(row, col, 1);  // counterclockwise
        if (check(rotated) && rotated < ret) ret = rotated;
      }

    if (ret == initial) ret.clear();

    return ret;
  }
}

2010-01-02

SRM451 div1 (過去問)

20:40

Easy - MagicalSource

136974のmagical sourceは1234である. magical sourceとは次のような数字である.

     1234
    12340
+  123400
---------
   136974

nが与えられるので最小のmagical sourceを求めよ.

magical source を 1倍, 11倍, 111倍, ... していったものがnにあたる数字なので, nを1, 11, 111, ... で割っていき, 割り切れたもののうち最小値を返せばできます.

class MagicalSource {
public:
  long long calculate(long long x) {
    long long ret = LLONG_MAX;
    long long denom = 1;

    for (int i=0; i<12; i++) {
      if (x % denom == 0) ret = min(ret, x/denom);
      denom *= 10;
      denom += 1;
    }

    return ret;
  }
};

2010-01-01

SRM453 div1 (過去問)

13:36

明けましておめでとうございます. 今年もがんばります.

Easy - TheBasketballDivOne

n チームのリーグ戦を考える. 各チームの勝ち負け全組み合わせのうち, 最も勝ち数の多いチームの勝ち数が m である組み合わせはいくつあるか.

n の範囲が 2 - 5 なので, 5チームのとき考慮すべき組み合わせが 5^2 - 5 = 20, 各試合ごとに勝ち負けの2パターンしか無いので, 2^20 = 1048576 通りを全探索しても間に合いそうです. 再気を使ってdfs. 勝ち数の数列は重複を許さないのでsetで管理しました.

じぶんは探索に真っ先に再帰を使ったんですが, 赤の人たちはビットなどを使ってうまくループだけで書き, コーディングのスピードアップをしているようでした.

class TheBasketballDivOne {
public:
  int table[5][5];
  int N, M;
  set <vector <int> > seq;

  int calcWins() {
    vector <int> results;

    for (int i=0; i<N; i++) {
      int wins = 0;
      for (int j=0; j<N; j++)
        if (i != j) {
          if (table[i][j] == 1) wins++;
          if (table[j][i] == 0) wins++;
        }
      results.push_back(wins);
    }

    sort (results.begin(), results.end());

    if (results[results.size()-1] == M)
      seq.insert(results);

    return 0;
  }

  int r(int row, int col) {
    int next_row = row, next_col = col + 1;
    if (row +1 == N && col + 1 == N) {
      calcWins();
      return 0;
    }
    if (col + 1 == N) {
      next_row = row + 1;
      next_col = 0;
    }
    if (row != col) {
      r(next_row, next_col);
      table[row][col] = 1;
    }
    r(next_row, next_col);
    table[row][col] = 0;

    return 0;
  }

  int find(int n, int m) {
    memset(table, 0, sizeof(table));
    seq.clear();
    N = n, M = m;

    r(0, 0);

    return seq.size();
  }
};