TCO13 Round 2C

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15653

250に9分。配信されたメッセージで題意を取り間違えていたことに気付くも、正しい実装が出来ず。チャレンジで撃墜された。Room 27。レートは1451から1422に下がった。

	Problem	Status	Points
250	DancingFoxes	Challenge Succeeded	0.00
500	TheMountain	Opened	0.00
1000	WellTimedSearch	Unopened

250に9分
- 題意を取り間違えていた
- メッセージで気付いたが、実装できなかった
- チャレンジで撃墜される
BFSはなかなかの時間で綺麗に書けるようになったと思っていたが、致命的なミスをしていることに気付いた
次回の目標
- 2回連続でEasyを落としているので、通したい

DancingFoxes

http://community.topcoder.com/stat?c=problem_statement&pm=12548&rd=15653&rm=317342&cr=22827765

9分。チャレンジで撃墜された。0点。

題意を取り違えた
- 狐0から狐1までの最短経路の辺の数から1を引いたものが答えだと考え、BFSで実装
- 「assuming that all other foxes cooperate and form pairs for the dances optimally」は気になってはいたがサンプルが通ったので、そのまま提出

メッセージで題意を取り違えていることに気付く

実装を見直すが実装方法が全く思い当たらず、終了。チャレンジが始まった瞬間に撃墜された

終了後、同部屋だった@simeji_tanさんに質問させていただいき、大変明快な解説を頂いた

氷解した。赤コーダーは説明が明瞭だ
@simeji_tanさん、どうもありがとうございました

その後自分なりに考える。この処理も一種のグラフの問題であるのではないかと思った

初めから考えてみよう。狐達の交友関係が隣接行列として与えられる

これはグラフとして図示することが出来る。以下はサンプルの2番のものだ。交友関係がある狐は双方向の矢印で結んだ

狐0から狐1への最短経路は以下の2つだ

グラフの辺の重みに差はないので、1として扱う。つまり、最短経路での辺の数は何れも3だし、距離も3だ

このグラフに限っては以下のように図示したほうが分かりやすいかもしれない

曲がかかるごとに狐はペアを組んで踊ることができる。このとき、狐は交友関係のある狐か交友関係のある共通の狐がいる場合にペアを組むことができる

現在の交友関係では(0, 4)、(0, 3)、(2, 1)、(3, 1)の狐がペアを組むことが出来る。一回ペアを組むと、新たな交友関係が成立される

狐2は狐0と4と交友関係のある共通の狐だ。そのため、狐0と4はペアを組むことが出来る。ペアを組んだ後は、狐0と4に新たな交遊関係が成立される

図示すると以下のようになる

何回かペアを組んでいると、そのうち狐0と1がペアを組めるようになる

つまり、狐0と1がペアを組むまでに必要な最小の踊りの回数を求めるのが今回の問題なのであった

踊るのが常に狐0とのペアだけであれば簡単だ(この場合は提出した実装となる)。しかし、他の友好的な狐達も同じ法則でペアを組み、踊りの回数を最小化してくれる。これが問題を複雑にしている

何れにしても狐0から1への最短経路を求めなければならない
- BFSで実装した

先ほどのような図だと少し分かり辛いので、以下のように図示してみる
- これもグラフだ
- 関心があるのは狐0から1への最短経路の辺の数のみであり、間に何れの狐がいるかは問題ではないが、便宜上記載するようにする

以下の場合、最短経路の辺の数は3

1回目の踊りでは狐0と4がペアを組むとしよう。踊りが終わった後、このペアには交友関係が生まれる

2回目の踊りでは狐4とお互いに交友関係がある狐0と1がペアを組むことができる

そのため、答えは2となる

次に以下の場合を考えてみよう

1回目の踊りでは狐0と4がペアを組むとしよう。また、狐0に友好的な狐7が狐1と交友関係を生むためにペアとなって踊るとしよう。ペアの数は2

この踊りが終わると、以下の図のような新しい交友関係がまた生まれる

2回目の踊りでは狐4とお互いに交友関係がある狐0と7がペアを組むことができ、新たな交友関係が生まれる

続く3回目の踊りでは狐7とお互いに交友関係がある狐0と1がペアを組むことができる。そのため、答えは3

さてここからは更新したグラフを記述する際に、最短経路のみ図示することにしてみる

先ほどの例を再び使おう。以下は初めの最短経路

1回目の踊りでは狐0と4、狐7と1がペアを組み、新たな交友関係が生まれる。その結果の狐0から1への最短経路は以下となる

2回目の踊りでは狐0と7がペアを組む。以下はその結果の最短経路

3回目の踊りで狐0と1がペアを組める。そのため、答えは3

さて、もう最短経路が長い場合も考えてみよう。以下は最短経路の辺の数が9である場合

この場合、狐0と4、狐1と5の2組のペアだけではなく、狐0に友好的な狐6と7がペアを組んで踊っている

更新された最短経路は以下となる

次にペアを組んでいるのは2組だ

これまで狐0と1が踊り狂うばかりであったが、その他のパターンも考えられる。以下は狐1が踊らない例だ

更新された最短経路は以下となる

ここまでをよく観察すると、一回の踊りでペアの数だけ狐が減っていることが分かる

また、一回の踊りで成立する最大のペアの数も狐の数から計算することができることが分かる
- 最短経路の狐の数をn₀としよう

1回目の踊りで組むことのできる最大のペアの数は以下で算出できる

残る狐の数は、現在の狐の数からペアの数を引くことで算出できる

漸化式とすることができそうだ

つまり、この解法はグリーディーのように見えるが、動的計画法であったのだ
- ...と言っても自信がない(間違えているようでしたら、どなたかご指摘ください)

n_iが2となったときのiが答えとなる

ここまでから実装を行った(以下の実装はシステムテストを通る)。

class DancingFoxes {
public:
  int minimalDays(std::vector<std::string> friendship) {
    int size = friendship.size();

    std::queue<int> queue;

    queue.push(0);

    std::vector<int> dist(size, -1);

    dist[0] = 0;

    while (! queue.empty()) {
      int i = queue.front(); queue.pop();

      for (int j = 0; j < size; j ++)
        if (friendship[i][j] == 'Y')
          if (dist[j] == -1) {
            dist[j] = dist[i] + 1;

            queue.push(j);
          }
    }

    if (dist[1] != -1) {
      int c = 0;

      for (int i = dist[1] + 1; i > 2; i -= i / 3)
        c ++;

      return c;
    }
    else {
      return -1;
    }
  };
};

プラクティスルームのシステムテストを1回落とした
- queue.front()ではなくて、queue.back()を使っていた!
- 題意を間違えてこそはいたが、このBFSを2、3分で記述できたのはよかったなー等と考えていた。とんでもなかった。これは痛い...
- 以後気を付けよう

コードリーディングを行った

同部屋だった@simeji_tanさんの実装、また@drken1215さん、@Mi_Sawaさんの実装を読んだ

ご三方共にWarshall-Floyd法で実装していた

特筆すべきこととして、変数k、i、jの順で反復を実装していることが挙げられる
- また吟味、更新する距離は(i, j)の要素のものであった

これはきっとベストプラクティスに違いない。これからは自分もこの順番で実装することにする

Warshall-Floyd法の復習を兼ねて、今一度実装した

実装はこちら(以下の実装はシステムテストを通らないので注意)。

#define INF 2000000000


class DancingFoxes {
public:
  int minimalDays(std::vector<std::string> friendship) {
    int size = friendship.size();

    std::vector<std::vector<int> > dist(size, std::vector<int>(size));

    for (int i = 0; i < size; i ++)
      for (int j = 0; j < size; j ++)
        dist[i][j] = (friendship[i][j] == 'Y') ? 1 : INF;

    for (int k = 0; k < size; k ++)
      for (int i = 0; i < size; i ++)
        for (int j = 0; j < size; j ++)
          dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);

    if (dist[0][1] < INF) {
      int c = 0;

      for (int i = dist[0][1] + 1; i > 2; i -= i / 3)
        c ++;

      return c;
    }
    else {
      return -1;
    }
  };
};