Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2012-05-20

Single Round Match 543 11:02 Single Round Match 543 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 543 - nodchipのTopCoder日記 Single Round Match 543 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 EllysXors

  • CodeForcesでやったような・・・
  • その問題の復習をしていた時に1~Nまでのxorを求める方法を聞いた気がする
  • それがあればf(L-1)^f(R)だなぁ・・・
  • ええっと
  • たしか4周期だった気がする
  • 紙に書き出してみよう
  • x%4==0の場合はx
  • x%4==1の場合はx^(x+1)=1
  • x%4==2の場合は1^x=x+1
  • x%4==3の場合は(x+1)^(x+1)=0
  • 以下帰納的に求まる
  • 書いてみる
  • 書けた
  • Submit
  • Passed System Test
class EllysXors {
public:
	ll f(ll x) {
		if (x % 4 == 0) {
			return x;
		} else if (x % 4 == 1) {
			return 1;
		} else if (x % 4 == 2) {
			return x + 1;
		} else if (x % 4 == 3) {
			return 0;
		}
	}
	long long getXor(long long L, long long R) {
		long long result = f(L - 1) ^ f(R);
		return result;
	}
}

Middle 500 EllysRivers

  • DPだよなぁ・・・
  • Lを長さ、Nを川の数と置いて、O(L^{2}N)は自明
  • Lを落とすにはどうすれば良いんだろう・・・?
  • ・・・
  • 更新元を全て舐めずにしゃくとりメソッド風に一度だけ舐めれば良い?
  • 書いてみる
  • 書けた
  • サンプル通った
  • 最大ケースも通った
  • Submit
    • Passed System Test
class EllysRivers {
public:
	double getMin(int length, int walk, vector <int> width, vector <int> speed) {
		int N = width.size();
		static double dp[2][128 * 1024];
		int front = 0;
		int back = 1;
		REP(i, length + 1) {
			dp[back][i] = i / double(walk);
		}

		REP(x, N) {
			fill_n(dp[front], length + 1, DBL_MAX);
			int leftBase = 0;
			dp[front][0] = dp[back][0] + width[x] / double(speed[x]);
			for (int y = 1; y <= length; ++y) {
				// 下から
				dp[front][y] = dp[front][y - 1] + 1.0 / walk;

				// 左から
				double temp = dp[back][leftBase] + hypot(width[x], y - leftBase) / speed[x];
				if (dp[front][y] > temp) {
					dp[front][y] = temp;
				}

				// 左から1マス進む
				while (leftBase < y) {
					temp = dp[back][leftBase + 1] + hypot(width[x], y - leftBase - 1) / speed[x];
					if (dp[front][y] > temp) {
						dp[front][y] = temp;
						++leftBase;
					} else {
						break;
					}
				}
			}

			swap(front, back);
		}

		double result = dp[back][length];
		return result;
	}
}

Hard 1000 EllysDeathStars

  • 問題を読み間違えていたようですorz

Challenge Phase

  • 250で全部回している人を探す
  • ・・・
  • いない
  • 500でTLEしそうな人を探してみる
  • ・・・
  • この人2次元DPの中で2文探索してる
  • 写経して実行速度を試してみる
  • あ・・・先を越された・・・
  • ちなみにTLEでした
  • ・・・

System Test

Class NameMethod NameDifficultyCoding TimeStatusPoints
EllysXorsgetXorLevel One0:08:07.335Passed System Test231.63
EllysRiversgetMinLevel Two0:33:39.264Passed System Test266.14
EllysDeathStarsgetMaxLevel Three0:30:49.586Opened0.00

oxx 497.77 46位 1951->2062 非常に良い成績が取れ、レーティングも大幅に上がりました。久々の2000台、素直に嬉しいです。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20120520
 |