2006 TopCoder Open - Round1 撃墜

Hayato Ito

2006 TopCoder Open - Round1 に挑戦． 750 名から 400 名へふるい落とされます．予選と違い，Round1 以降は，通常の SRM と同様の形式です．チャレンジ・フェーズもあります．

ラウンドへの登録時，アンケートがありました．「コンタクト先をスポンサーである NSA(National Security Agency)に教えてもいいかい？」 というものでした． TopCoder はいい就職・転職の機会の場になってますね．実際には，NSA は US 市民でないと勤務できないそうですが．．．

ラウンド本番中，ちょっとした運営側の不手際がありました． 350 点問題を開くと，実際には 500 点問題が， 500 点問題を開くと，実際には 350 点問題が表示されてしまっていたようです．

FirstToLast (code)

500 点問題．最初に Open した問題です．本番中はこれが 350 点問題だと思っていました．．

整数 p, q (1 <= p <= 100, 1 <= q <= 100) が与えられます. このとき，以下の条件を満たす正の整数 a を （存在しない場合は-1 を）返しなさい という問題です．

条件を満たす a が複数ある場合は，そのうちもっとも小さいものを返します．たとえば，p = 1, q = 4 ならば，答えは a = 102564 になります．

ですね．

うーん方針が浮かびませんでした． とりあえず Example Case に通るようにしてから Submit しました．不完全だというのはわかっていましたが，もうあきらめて次の問題に移りました．．

SeparateConnections (code)

実は，こっちが，350 点問題でした．本番中は，500 点問題だと思って取り組んでいました．

ノードが n 個与えられます．各ノード間が通信可能かどうがが，マトリックス形式で与えられます．

ノードが 5 個の場合です．Y が通信可能．N は通信不可能です．

"NYYYY",
"YNNNN",
"YNNNY",
"YNNNY",
"YNYYN"

各ノードは同時に 1 つの他のノードと通信できるとします．2 つ以上とは通信できません．この場合，お互いに通信しているノードのペアを最大いくつ作成できるか？その通信しているノード数（ペア数 x 2 になります）を求めなさいという問題です．

本番中は，思いっきり問題を勘違いしてしまって，Bipertite Matching を使用して解いてしまいました．普通に DP で解くべき問題でした．こんな感じになります．

public class SeparateConnections {

  public int howMany(String[] mat) {
      int N = mat.length;
      int max = 0;
      boolean[] ok = new boolean[1<<N];
      ok[0] = true;
      for (int i = 0; i < (1<<N); i++) {
          if (!ok[i]) continue;
          max = Math.max(max, Integer.bitCount(i));
          for (int n1 = 0; n1 < N; n1++) {
              for (int n2 = n1+1; n2 < N; n2++) {
                  if ( mat[n1].charAt(n2) == 'Y'
                          && (i & (1 << n1)) == 0
                          && (i & (1 << n2)) == 0) {
                      ok[ i | (1 << n1) | (1 << n2)] = true;
                  }
              }
          }
      }
      return max;
  }
}

NumPermutationOrders

1000 点問題．ていうか無理．

結果

System Test の結果です． ( Room Statistics )

Room Statistics

スコア 0 です．．．敗退決定です． スコア 0 は，401 位でした． 1 点でもスコアがあったら，400 位以内に入っていたようです．

今日の教訓