TCO 2013 Round 2B 本番

TCO 本番 DP

実況風

Coding

Easy (250)

とりあえずkiwiとgrapeのオフセットを全探索。
さて、ループ内では最小のところをどうにか高速に求めなければいけないわけだが…
なんていうか、なんとなくなのだけれども、
xとyの最小の差は(±xとyのオフセット差 mod gcd(x, y)) とかな気がする。 (±の両方で求めて、minを取る)
これを全てのペアに対して求めてminを取る。
ということがなんとなく思いついたので、それを書いた。
ドキドキしつつ、少し見なおしてSubmit

Medium (500)

Easyをもう少しテストしてから開くべきだったか、とか思いつつ読む。
最初全然わからない。2^n的な状態でさえわからない。
まず、今までのシークエンスが与えられた時に特定する方法を考えてみた。
それは(dp[シークエンスの何番目までで] = ある都市にいることがありえるか？のbitmask)というDPがわかる。
それを、ゲーム形式でできないだろうか？
これは単純にそのままの形でできないだろうか？
はじめに、
初めにいた都市を全探索し、その都度dpするものを書いてみた。
ここで必然的に[本当はこの都市にいる]という状態を追加した。
後から思うと、この回り道のおかげで状態が正しく決められたという、幸運な偶然に思える。
もしどこにもいる可能性がなくなったら現在の時間-1で終了。
さらに、ここは少しややこしかったのだが、
もし、可能性のある場所が1つだけになったら、そこは当てられる、ということでその状態を0(空、どこも可能性がないこと)にする。そして、もし全ての場所が空か1つだけになっていたら、現在の時間で終了。
バグらせながら、残り10分程度になりながら、書けた。
さて、このdpではループ判定ができない。なのでTimeLimitギリギリまでやることにした。しかしこの実装では遅すぎた。
まずbit演算で済ましたりして少し速くなったがまだ遅い。
なんとなく、初めにいた都市を全探索する必要は無いのではないかと思い、そのループを外してみる。それは上手く動いた。
その実装では1000回+程度回せるようだった。
もっといくケースもありそうな気がすごくした。このdpをうまく行列累乗できないかとか考えてた。しかしわからない。
残り時間がかなり迫ってくる。
残り20秒程度、1010回回すものをSubmit。記念Submitだな、と思った

Challenge

しない。できない

SystemTest

どうせMed落ちるよな、Easy落ちないでくれ、Med落ちたら暫定200位程度かー…
"The system tester has completed its testing"
さて、Easy落ちないでくれ…
Easy通ってた良かった…？！Med通ってる！！！！！！本当かよ？(何度も見なおして)…
まあ、良かった

結果

Easy: 230.24/250
Medium: 190.05/500
Challenge: 0/0 = +0
Division Place: 34/1214
Rating: 1996→2150

問題に対するコメント

Easy

ループさせなくても、ある場合分けでできるらしい

Medium

writerさんによると、なんか変なグラフの最長経路になるらしい。あんまりわかってはいない。
Practice System Test によると、最大で219回回るケースがあった。回数には少しだけ余裕があったが、高速化をしていなかったら駄目だっただろう

コメント

まあ、通ったから良かったものの、時間ギリギリではあるし、考え方は微妙なところもあったと思う。
さて、赤圏内なわけだが…
次のSRMで赤になってみせる！！！！！！！！ ！！！！！！！！！ ！！！！！！！！！！！！！！！！！！！！！！

コード

Easy
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define INF 0x3f3f3f3f
using namespace std;
template<typename T>T gcd(T x, T y){if(y==0)return x;else return gcd(y,x%y);}
struct FruitTrees {
	int maxDist(int apple, int kiwi, int grape) {
		int r = 0;
		int ak = gcd(apple, kiwi), ag = gcd(apple, grape), kg = gcd(kiwi, grape);
		rep(i, kiwi) rep(j, grape) {
			int k = (j - i) + kg * 3000;
			int x = INF;
			x = min(x, i % ak);
			x = min(x, ak - i % ak);
			x = min(x, j % ag);
			x = min(x, ag - j % ag);
			x = min(x, k % kg);
			x = min(x, kg - k % kg);
			r = max(r, x);
		}
		return r;
	}
};
Medium
#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;   
typedef vector<string> vs; 
const int MAXT = 1010;	//no hope (このコメントを添えて提出した)
struct ScotlandYard {
	int n;
	vs g[3];
	int maxMoves(vector <string> taxi, vector <string> bus, vector <string> metro) {
		n = taxi.size();
		g[0] = taxi, g[1] = bus, g[2] = metro;
		static ll nexts[55][3];
		mset(nexts, 0);
		rep(j, n) rep(x, 3) rep(k, n) if(g[x][j][k] == 'Y')
			nexts[j][x] |= 1LL << k;
		static ll dp[MAXT+1][55];
		int r = INF;
		mset(dp, 0);
		rep(first, n) dp[0][first] = (1LL << n) - 1;
		rep(t, MAXT) {
			ll uni = 0;
			rep(pos, n) uni |= dp[t][pos];
			if(uni == 0) {
				r = t - 1;
				break;
			}
			rep(pos, n) {
				int x = 0;
				rep(i, n) x += dp[t][pos] >> i & 1;
				if(x == 1) dp[t][pos] = 0;
			}
			uni = 0;
			rep(pos, n) uni |= dp[t][pos];
			if(uni == 0) {
				r = t;
				break;
			}
			rep(pos, n) if(dp[t][pos]) {
				rep(x, 3) rep(i, n) if(g[x][pos][i] == 'Y') {
					ll d = 0;
					rep(j, n) if(dp[t][pos] >> j & 1)
						d |= nexts[j][x];
					dp[t+1][i] |= d;
				}
			}
		}
		return r == INF ? -1 : r;
	}
};