SRM 542 - agwの日記

Single Round Match 542 Round 1 - Division II

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

250に10分。残り時間を500に費やしたが解けずに終わった。

チャレンジ1回失敗。レートは866から830へ。白コーダー。

	Problem	Status	Points
250	WorkingRabbits	Opened	226.07 - 25
500	PatrolRoute	Opened
1000	StrangeDictionary	Unopened

250に10分。226.07ポイント
残りの65分を500に費やす
- 解けなかった
チャレンジに一回失敗。-25ポイント
レートがどんどん下がっていく...
次回の目標
- 2問通す

WorkingRabitts

http://community.topcoder.com/stat?c=problem_statement&pm=11936&rd=14734

10分。実装はすぐ出来たが、チャレンジを失敗した。

入力を行列と捉える
- 対称行列
  - つまり、a_i,j = a_j,i
- 対角成分が0である

上三角行列の合計を足し込み、要素数を数え上げる

その結果から答えを算出する

実装は以下(システムテスト済)。

class WorkingRabbits {
public:
  double getEfficiency(std::vector<std::string> profit) {
    double P = 0, Q = 0;

    for (int i = 0, size = profit.size(); i < size; i ++)
      for (int j = i + 1; j < size; j ++) {
	P += profit[i][j] - '0';
	Q += 1;
      }

    return P / Q;
  };
};

チャレンジに失敗した
- 以下の計算を理解せずにチャレンジしてしまった

    double ans = (double) sum / (ln*ln-ln);

行列の要素数から対角成分の要素数を引いたものを計算している

つまり、2Q
また、行列の全要素を足し込むと、2Pとなる
- - 対角成分が全て0であるからだ

この値を2で割ったものを使っている人もいた
- これはもちろんQと等しくなる

さて、今回のような2重ループを考えてみよう

  for (int i = 0; i < size; i ++)
    for (int j = i + 1; j < size; j ++)
                   :

これまでこの計算量を計算するときは、以下のように[1, w-1]の総和を取っていた

1からnまでの総和は以下として求めることができる

そのため、1からw-1までの総和は以下として求めることができる

さらに計算すると

これは行列の要素数から対角成分の数を引いて2で割ったものに等しい(図は再掲)

目から鱗

同様に1からwまでの総和を求めてみよう

数列として考えれば、1からw-1までの総和にwを足してやればよい
- 図的に考えれば、先ほどの大きさに対角成分の数を足してやればよい

行列の全要素数から1からw-1までの総和を引くという考え方もできる

何れの場合も計算結果は以下となる

PatrolRoute

http://community.topcoder.com/stat?c=problem_statement&pm=11934&rd=14734

65分費やして解けなかった。

ある矩形の中で条件を満たす3点を取る。経路の長さは最大で以下となる(矩形の幅をw、高さをhとする)

ここから発展することなく終了してしまった
条件を満たす3点からなるバウンディングボックスが同じ大きさであれば、その経路の長さは上の式で求めることができる
- 逆にバウンディングボックスの大きさを決めてやり、3点の選び方を考えればよい
まずバウンディングボックスの大きさを決める
- 経路の長さを計算する
- 計算した経路の長さが条件を満たしている場合、3点の組み合わせを考える
- さらにその大きさのバウンディングボックスが領域全体に何組み合わせ配置できるか考える

ABCの順列はどう考えればよいだろう
- 同一の経路とみなすべきか、別々の経路として数え上げるべきか

問題に記載されているが、英語力が足らず理解することができない

Two routes are considered to be different if there is a place that
belongs to one of them, but does not belong to the other one.

最初の例で考えてみよう
- 3 x 3の領域でA、B、Cと配置する
- 重複した経路を数え上げるのであれば、Aを9箇所から選び、Bを残りの4箇所から選ぶので合計36通り(AとBの位置が決まればCの位置は決まることに注意)
- この例の実際の答えは6だ
  - 36通りを₃P₁で割ったものだ
  - つまり、ABCの順列は考えなくてよく、同一の経路とみなす

ではAを角に置こう。BはAと同一のx、y座標に置けない

Bを角に置く。Cはもう縁に置けない

この戦略の場合、対角を選ぶ組み合わせが2通り、Cを選ぶ組み合わせが(w - 2) x (h - 2)通り

再びAを角に置こう。今回はB、Cとも角に置かないようにしよう
- BとCは左右上下の縁に置かなければならない
- 内側に置いてはいけない
  - B、Cの何れかを内側に置いた場合は、残った点を角に置かなければならない
    - そうしないとバウンディングボックスが小さくなってしまう

残った縁にCを置く

この戦略の場合、角を選ぶ組み合わせが4通り
- Bが左右の縁にある場合、Cは上下の縁に置かれる
- Bが上下の縁にある場合、Cは左右の縁に置かれる
  - 経路が重複することを加味すると組み合わせは以下のように計算できる

最後に、大きさw、hのバウンディングボックスは以下の組み合わせ分配置できる

実装は以下(システムテスト済)。

#define MOD 1000000007


class PatrolRoute {
public:
  int countRoutes(int X, int Y, int minT, int maxT) {
    long long c = 0;

    for (int w = 3; w <= X; w ++)
      for (int h = 3; h <= Y; h ++) {
	int t = 2 * (w - 1) + 2 * (h - 1);
	
	if (minT <= t && t <= maxT) {
	  long long t;
	  
	  t  = 2 * (w - 2) * (h - 2);
	  t += 4 * (w - 2) * (h - 2);

	  t *= (X - w + 1) * (Y - h + 1);
	  
	  c = (c + t) % MOD;
	}
      }

    return c;
  };
};