Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-18

Member SRM455 div2 Medium のループと計算量の証明

17:26

Member SRM455 div2 - cou929のTopCoder日記 - TopCoder部 の続き. 数列Aにかならずループが存在することを証明し, かつその計算量を求めます.

A[i]はそれより前のN個の要素(A[i-N] - A[i-1])に依存しています. このN個の並びが全く同じものが, 数列全体の中で二度出てくるとしたら, Aがループしていることになります. 今回Aの各要素は10でmodをとっているので, [0, 9]の10種類のみです. よってAのN個の要素ととりうる値の種類は10^N通り. このことから, 次のような要素の組を考えた場合, 少なくともA[10^N]の組までには必ず一回は, 全く同じ要素からなる組が存在することになります.

(A[1], A[2], ..., A[N]), (A[2], A[3], ..., A[N+1]), ..., (A[10^N], ..., A[10^N+N])

言い方を変えると, すべてのパターンが 10^N 通りである数列を 10^N+1 個作ったとき, かならず1つは全く同じ数列ができるということです. 今回はNが高々7なので, 10^7 = 10000000 通りとなり, ワーストケースでも時間に間に合うと考えることができます.

ここでは "n個のアイテムをm個の箱に入れる際に, もし n > m だと, 少なくとも一箱は2つ以上のアイテムが入っている箱がある" という事実を使っているんですが, これには Pigeonhole principle という名前がついています.

Pigeonhole principle - Wikipedia

鳩の巣原理 - Wikipedia

上の例だと一見自明な現象にわざわざたいそうな名前を付けているように感じるんですが, ものによってはこの定理を使うことで直感に反する結論が導けることがあって面白いです. wikipediaから引用します.

たとえば「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」。証明してみよう。ふつう、髪の毛の本数は15万本ほどであるから、100万本の髪の毛を持っている人間はいないと考えることができる。ロンドンの人口は100万以上である。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てれば、(約15万に100万以上を割り当てるのだから)少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。

もう1つのきわめて有名な例は、世界中からランダムに6人を集めてくると、その6人から、互いに全員知り合いであるか、あるいは互いに全く知り合いでない3人組を必ず1組は作ることができる、というものである。詳細は、ラムゼーの定理および組合せ数学のラムゼー理論の項を参照。


以上はこちらのforumのスレッドを参考にしました.

Logic to DivII Medium


Member SRM455 div2

06:45

寝坊して参加できませんでした.

Easy - SpidersOnTheGrid

グリッドが与えられ, それぞれのセルには東西南北のいずれかが割り当てられている. freeなセルの個数をカウントせよ.

問題の意味がいまだにつかめません. まず"free cells"の意味がわかりません. また東西南北の方向もあいまいさがあります. 特に南北が2通りの意味にとれてしまうので, きちんとインデックスの数字で示すべきです.

以下は他の人のコードを参考に書いたものです. このコードだと, "free cells" は"そのセルをスタート地点にしない限りは絶対に訪れることができないセル"という解釈になるんですが, これであってるんでしょうか. 本番だと解ける自信がないです.

class SpidersOnTheGrid {
public:
  int find(vector <string> A) {
    int ret = 0;
    bool ok[A.size()][A[0].size()];
    memset(ok, false, sizeof(ok));
    int dirx[4] = {-1, 1, 0, 0}; // NSEW
    int diry[4] = {0, 0, 1, -1};
    string dir = "NSEW";

    for (int i=0; i<A.size(); i++)
      for (int j=0; j<A[0].size(); j++) {
        int k = 0;
        for (k=0; k<4; k++)
          if (A[i][j] == dir[k])
            break;
        int nextx = i + dirx[k], nexty = j + diry[k];
        if (0 <= nextx && nextx < A.size() && 0 <= nexty && nexty < A[0].size())
          ok[nextx][nexty] = true;
      }

    for (int i=0; i<A.size(); i++)
      for (int j=0; j<A[0].size(); j++)
        if (!ok[i][j])
          ret++;

    return ret;
  }
};

Medium - EasySequence

問題文は省略.

ちょっと難しかったです. まずはループが検出されるまで, 数列Aを作っていきます. ループの検出はAの長さが2の倍数の時に, Aの前半と後半を比べることで実現します. その後はAにBが含まれているかをチェックします. このチェックで境界条件を間違えて, 一度システムテストで落ちてしまいました. またこのアルゴリズムは1. Aに必ずループが出現すること, 2. ループが時間内に求まることを前提としていますが, これらは証明していなくて, ほかにアプローチが思いつかなかったので決め打ちで実装しました. そのせいでなんだかまだすっきりしていません.

class EasySequence {
public:
  int find(vector <int> A, vector <int> B) {
    int ret = -1;
    int n = A.size();

    for (int i=0; ; i++) {
      int tmp = 0;
      for (int j=0; j<n; j++)
        tmp += A[i+j];
      A.push_back(tmp%10);

      // loop detection
      if (A.size() % 2 == 0) {
        vector <int> first_half, second_half;
        for (int j=0; j<A.size(); j++)
          if (j < A.size()/2)
            first_half.push_back(A[j]);
          else
            second_half.push_back(A[j]);

        if (first_half == second_half)
          break;
      }
    }

    while (A.size() < B.size())
      A.insert(A.begin() + A.size(), A.begin(), A.end());

    for (int i=0; i<A.size() - B.size() + 1; i++) {
      bool ok = true;
      for (int j=0; j<B.size(); j++)
        if (A[i+j] != B[j]) {
          ok = false;
          break;
        }

      if (ok) {
        ret = i;
        break;
      }
    }

    return ret;
  }
};

通りすがり通りすがり2009/12/21 22:32「蜘蛛は指定された方向に毎秒1セルづつ進みます。1秒後に蜘蛛のいないセルの数は?」

cou929cou9292009/12/21 22:45ありがとうございます.
そうですね. 最初はすべてのセルに蜘蛛がいて, 一秒後にフリーになってるセルですね.