2006 TopCoder Open - Round1 撃墜
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 の各桁を左に回転シフトした結果を a~rotate~ とすると， a * p/q = a~rotate~
- a < 2,000,000,000 (2 billion です．)
条件を満たす a が複数ある場合は，そのうちもっとも小さいものを返します．たとえば，p = 1, q = 4 ならば，答えは a = 102564 になります．
- "102564" の左端の 1 を右にくっつけて， a~rotate~ = 25641
- a * p / q = 102564 * 1/ 4 = 25641 = a~rotate~
ですね．
うーん方針が浮かびませんでした． とりあえず 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 )
スコア 0 です．．．敗退決定です． スコア 0 は，401 位でした． 1 点でもスコアがあったら，400 位以内に入っていたようです．
今日の教訓
- あー勘違い．