Hatena::Grouptopcoder

flowlighTの日記

2011-08-21

*[SRM]SRM 515

| 15:28

このSRMから日記をつけることにしました。

SRM 514には参加していなかったので3週間ぶりのSRM

黄色二人と残りは青二人という非常に平和な部屋でした。

結果

15:28

EasyMediumHardChallengescore
223.580.00Unopened+50.0273.58

順位は良かったけどMediumに手も足も出ない感じだったので悔しい。

Easy RotatedClock

| 15:28

00:00から11:59までのそれぞれに対して時計の針と矛盾するかどうかを考えればよい。10分ほどでsubmitしたがsubmitしてる人が少なすぎて不安になった。問題文の解釈に手間取った人が多かったみたい。

以下ソースコード



#include <iostream>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <memory>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const double EPS = 1E-9;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1 << 30;

string get_clock(int i, int j){
	string res;
        res.push_back((char)('0' + i / 10));
	res.push_back((char)('0' + i % 10));
	res.push_back(':');
	res.push_back((char)('0' + j / 10));
	res.push_back((char)('0' + j % 10));
	return res;
}

bool ok(int i, int j, int h, int m){
	if(j % 2 != 0) return false;
	int angm = 360 * j / 60;
	int angh = 360 * i / 12 + 30 * j / 60;
	for(int k = 0; k < 12; k++){
		if(angm == (m + k * 30) % 360 && angh == (h + k * 30) % 360) return true;
	}
	return false;
}

class RotatedClock {
public:
	string getEarliest(int h, int m) {
		for(int i = 0; i < 12; i++){
			for(int j = 0; j < 60; j++){
				if(ok(i, j, h, m)){
					return get_clock(i, j);
				}
			}
		}
		return "";
	}
}

Medium NewItemShop

| 15:28

さっぱりわからなかったので適当に再帰で書いてそれからもっと良い方法を考えることにした。とりあえず書いたのでsampleを試す。合わない。そのまま時間切れ。

解けている方々の日記を見た感じだと二回以上店に来る客は12人以下なのでこれを利用してbitDPかメモ化再帰を書けばいいっぽい。後で書こう。

Challengeでそのままの再帰で書いているコードをTLEで撃墜した。