天下一プログラマーコンテスト2015 予選A : A - 展開図プログラマーコンテスト、B - stepモード

天下一コンに参加。Cに手こずりすぎて微妙な順位。
http://tenka1-2015-quala.contest.atcoder.jp/tasks/tenka1_2015_qualA_a
http://tenka1-2015-quala.contest.atcoder.jp/tasks/tenka1_2015_qualA_b

A - 展開図プログラマーコンテスト

サイコロの展開図において、ある面から初めて隣接面を辿ることを考える。
その際同じ面を2回以上通ることはできない。
この条件のもとで、任意の展開図において経由順に数字を並べたとき、得られる値の最大値を求めよ。

展開図で直接考えると面倒なので、平面上に置かれた立方体で考える。
この立方体上で隣接面を辿るとき、その面が下に来るようサイコロを回転させていくとこれは題意を満たす展開図となる。
当然大きな順に数字を辿るのがよいので654231が解。

void solve() {
	int i,j,k,l,r,x,y; string s;
	cout<<"654231"<<endl;
}

B - stepモード

21～22時の間のPC上でのプログラムの開始時刻S[i]・終了時刻E[i]のログがある。S,Eはミリ秒単位で与えられる。
プログラムの開始・終了時刻はミリ秒換算で小数点以下の数字が存在せず、かつ実行時間は1ミリ秒以上である。

この日、どこかで１度PCの時計が一時巻き戻りが発生した。

• 巻き戻った時間は1000ミリ秒
• 巻き戻りの発生時刻は、ミリ秒換算で小数点以下の数字が存在していた。

ログから各プログラムの実行時間が一意に定まるか求めよ。

まず巻き戻りは発生した可能性のある時刻の範囲(巻き戻り発生時刻及び巻き戻り後の時刻を含む)を求める。
初期状態では24時間全体が可能性があると考える。
S[i]≧E[i]だったらこのプログラム実行中に巻き戻りが起きた可能性があるので、巻き戻り発生範囲は閉区間(S[i]-1000,E[i]+1000)に含まれる。
(巻き戻り発生範囲には、巻き戻り後の時刻も含むので、開始がS[i]-1000となる)

あとは各プログラムの実行時刻がこの巻き戻り時刻を含むかどうかで実行時間を計算できる。

• S[i]≧E[i]なら、実行中に巻き戻りが発生するはずなのでE[i]-S[i]+1000
• 区間(S[i],E[i])に、上記巻き戻り発生範囲が含まれるなら実行中に巻き戻りが発生するはずなのでE[i]-S[i]+1000
• 区間(S[i],E[i])と上記巻き戻り発生範囲が重複する範囲を持たないなら、実行中に巻き戻りが発生していないのでE[i]-S[i]
• それ以外の場合、区間(S[i],E[i])と上記巻き戻り発生範囲が一部重複する範囲を持っているので、実行中に巻き戻りが発生したか確定できず実行時間は一意でない。

int N;
int S[4];
int T[101][2];
int L,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	L=0,R=24*60*60*1000;
	
	scanf("%d",&N);
	
	FOR(i,N) {
		FOR(j,2) {
			scanf("%d:%d:%d.%d",&S[0],&S[1],&S[2],&S[3]);
			T[i][j]=S[0]*60*60*1000+S[1]*60*1000+S[2]*1000+S[3];
		}
		if(T[i][0]>=T[i][1]) {
			L=max(L,T[i][0]-1000);
			R=min(R,T[i][1]+1000);
		}
	}
	
	FOR(x,N) {
		int tt=T[x][1]-T[x][0];
		if(tt<=0 || (T[x][0]<=L && R<=T[x][1])) _P("%d\n", tt+1000);
		else if(R<=T[x][0] || T[x][1]<=L) _P("%d\n", tt);
		else _P("-1\n");
	}
}

まとめ

Bはなんかややこしくて余り面白さを感じられなかったな。