SRM 556 Div I - agwの日記

Single Round Match 556 Round 1

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

250に75分を費やし、全く解けなかった。写経して自信を持って行ったチャレンジが失敗。合計-25.00点。レートは1236から1085へ。緑コーダーに。Room 28。

	Problem	Status	Points
250	XorTravelingSalesman	Opened	0.00
500	LeftRightDigitsGame2	Unopened
1000	OldBridges	Unopened

250に75分費やすも、全く検討付かず。0.00点
写経を行い、自信を持って行ったチャレンジも失敗。合計-25.00点
レートは1236から1085へ
- 早速緑コーダーに落ちてしまった
次回の目標
- 2完する

XorTravelingSalesman

http://community.topcoder.com/stat?c=problem_statement&pm=12175&rd=15178

75分費やすも、全く検討付かず。

全く分からなかった

SRM後、拡張ダイクストラ法(もしくはダイクストラ法の拡張?)を用いることを知った

53番目のシステムテスト(システムテスト #52)を図示してみた

各頂点にはそれぞれ価値が設定されている
- 0番目の頂点から開始する。価値の初期値は728だ
- 0番目の頂点に接続されているのは2番目と4番目の頂点だ
- 2番目の頂点を訪れたときの価値は263となる。現在の価値728と2番目の頂点の価値991の排他的論理和だ

このように頂点を巡り、取得しうる最大の価値を求める問題

拡張ダイクストラ法を使って、グラフを探索する
- グラフを探索し、各頂点に訪れた際の価値を記録していく
- 同じ頂点に異なった価値で複数回訪れることがあることに注意する

辺の重みは全て等しいので、幅優先探索を用いる

0番目の頂点から始める
- そのときの価値は728だ。これを記録する
0番目の頂点から接続されている2番目と4番目の頂点の価値はそれぞれ、991と985だ
- 現在の価値、728との排他的論理和はそれぞれ263と257
- 2番目の頂点の記録を参照する。263は記録されていないので記録して、訪れる
- 4番目の頂点の記録を参照する。257は記録されていないので記録して、訪れる

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

次に2番目と4番目の頂点を考えよう
- 特に4番目の頂点を考える
4番目の頂点の現在の価値は257だ
4番目の頂点から接続されているのは0、1、3、4番目の頂点である
0番目の頂点は価値が728。現在の価値257との排他的論理和は728となる
- 0番目の頂点の記録を参照する。728は記録されているので、訪れない
1番目の頂点は価値が807。現在の価値257との排他的論理和は550
- 1番目の頂点の記録を参照する。550は記録されていないので記録して、訪れる
同様の処理を2番目と3番目の頂点に関しても繰り返す
さらに、現在訪れている2番目の頂点についても同様に処理する

これを繰り返す...

さらに繰り返す...

もっと繰り返す...
- グラフは[1, 50]個の頂点を持つ
- また、{1, ..., 1023}の集合の重複を許す要素の排他的論理和は[0, 1023]に納まる
- つまり、最大50 × 1024回頂点を訪問する

訪問することの出来る頂点がなくなったら、記録されている価値から最大のものを探す
- このテストケースが取りうる最大の価値は998だ

記録する値の総数は最大50 × 1024個だ
- そんなに多くないので大丈夫だ

実装は以下となった(システムテスト済)。キーを工夫して、単一のセットを使用。

class XorTravelingSalesman {
public:
  int maxProfit(std::vector<int> cityValues, std::vector<std::string> roads) {
    int pp = cityValues[0];

    std::queue<int> queue;

    queue.push(cityValues[0] * 100);

    std::set<int> visited;

    visited.insert(queue.front());

    while (! queue.empty()) {
      int p = queue.front() / 100, i = queue.front() % 100; queue.pop();

      pp = std::max(p, pp);

      for (int j = 0, size = cityValues.size(); j < size; j ++)
	if (roads[i][j] == 'Y') {
	  int x = (p ^ cityValues[j]) * 100 + j;

	  if (! visited.count(x)) {
	    visited.insert(x);

	    queue.push(x);
	  }
	}
    }
    return pp;
  };
};

チャレンジが失敗した原因を考察する
bardek氏の実装を写経した
- 自分で用意した後半のテストケースが失敗することを十分確認し、自信を持ってチャレンジをした
  - 何故か失敗した
考えてみるに、どうやらC++のグローバル配列の要素は実行前にデフォルトコンストラクタで初期化されるらしい
- 「どうやら」としているのは詳しい文献が見つからなかったからだ(情けない)
恐らく、TopCoderのシステムテストは1問につき1インスタンスを起動しているのだろう
- 1インスタンスで連続してテストを行った場合、グローバル配列の要素が初期化されない。そのため、自分の環境では失敗するテストケースがあったのだろう
グローバル変数を使うことがあまりなかったので、意識していなかった
- 今後気を付けよう
理解もしていない問題を写経のみでチャレンジすることがそもそもの間違いではある

さて、よい機会であるので、幅優先探索について考察する
以下はアルゴリズムCの第3巻、29章「グラフのアルゴリズム表現と探索」から抜粋した実装だ(p. 21)

int val[maxX]; int id = 0;
visit(int k)
  {
    struct node *t;
    put(k);
    while (!queueempty())
      {
        k = get(); val[k] = ++id;
        for (t = adj[k]; t != z; t = t->next)
          if (val[t->v] == 0)
            { put(t->v); val[t->v] = -1; }
      }
  }
listbfs()
  {
    int k;
    queueinit();
    for (k = 1; k <= V; k ++) val[k] = 0;
    for (k = 1; k <= V; k ++)
      if (val[k] == 0) visit(k);
  }

visit()はグラフの頂点に順に訪れ、各頂点に1から|V|までの番号を割り当てる関数だ

この実装は実に巧妙で、外側の反復の回数は|V|回となる

次の頂点をキューに追加する際、val[t->v]を-1に設定しているところが最大のポイント
- -1を設定することで、頂点がキューに挿入されたことを表していると考えればよい
- これによりキューに未訪問の頂点のみを挿入することを保証している
- これが外側の反復が|V|回となる理由だ

このスタイルに慣れるまで、とても時間がかかった
- 将来訪れるはずの頂点に関する処理の一部をキューに入れる際に行うことがとても気持ち悪かったのだ
- 頂点の処理そのものと頂点への訪問履歴の処理を別のものとして捉えるとよいかもしれない

長い間木のレベル順走査と混同していたのもよくなかった
- 以下はアルゴリズムCの第1巻、4章「木の章」から抜粋した実装だ(p. 55)

traverse(struct node *t)
  {
    put(t);
    while (!queueempty())
      {
        t = get(); visit(t);
        if (t->l != z) put(t->l);
        if (t->r != z) put(t->r);
      }
  }

400番台のSRMを練習していたときに、他の方の幅優先探索の実装を見て衝撃を受けたのがきっかけであった
- 初めは将来訪れるはずの頂点に関する処理の一部をキューに入れる際に行うことに嫌悪感を覚えた
- その後アルゴリズムCを確認し、同様の実装がなされているのを見てぶっ飛んだ

アルゴリズムCでの実装を理解し、閉路があるグラフの探索は根本的な性質が全く違うことを思い知った
- これは、最適な実装なのであった

それまでは木のレベル順の走査の実装を基調とし、より速く動作するようvalの判定処理を直感で挿入し、悪質な亜種を様々生み出していた

例えば以下はキューに入れる直前と頂点の処理をする直前に判定を行い、冗長な処理を行わないようにするよう工夫したつもりの実装だ

void visit(int k)
  {
    struct node *t;
    put(k);
    while (!queueempty())
      {
	k = get(); if (val[k] != 0) continue;	// 処理の直前にチェック
	val[k] = ++id;				// 処理はここで行う
	for (t = adj[k]; t != z; t = t->next)
	  if (val[t->v] == 0)			// キューに入れる前にチェック
	    { put(t->v); }			// 将来訪れるはずの頂点は処理をしない
      }
  }

この実装は大目に見ればまだ許せる

次は頂点の処理をする直前のみ判定を行う実装だ

void visit(int k)
  {
    struct node *t;
    put(k);
    while (!queueempty())
      {
	k = get(); if (val[k] != 0) continue;	// 処理の直前にチェック
	val[k] = ++id;				// 処理はここで行う
	for (t = adj[k]; t != z; t = t->next)
	  { put(t->v); }			// 将来訪れるはずの頂点は処理をしない
      }
  }

この実装はとてもよくない
- 処理の回数こそ|V|回だが、キューに頂点を入れる回数は最大|E|回となってしまう(!)
- |E|は最大で|V|^2となる(各頂点が全ての頂点に接続されている密なグラフを考えるとよい。すぐ後に図示している)
- アルゴリズムCの実装が頂点をキューに入れる回数が|V|回であることを考えると、とても損をしていることが分かる
- 速度が驚くほど遅くなることもないので、特に注意が必要

最後は最悪の例で、頂点をキューに入れる直前のみ判定を行う実装だ

void visit(int k)
  {
    struct node *t;
    put(k);
    while (!queueempty())
      {
	k = get(); val[k] = ++id;		// 処理はここで行う
	for (t = adj[k]; t != z; t = t->next)
	  if (val[t->v] == 0)			// キューに入れる前にチェックする!
	    { put(t->v); }			// 将来訪れるはずの頂点は処理をしない
      }
  }