Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

2017-05-21

2017 TCO Round2A 500 DistanceZeroAndOne

11:38 |  2017 TCO Round2A 500 DistanceZeroAndOne - kojingharangの日記 を含むブックマーク はてなブックマーク -  2017 TCO Round2A 500 DistanceZeroAndOne - kojingharangの日記  2017 TCO Round2A 500 DistanceZeroAndOne - kojingharangの日記 のブックマークコメント

  • 頂点 0〜N-1 の無向連結グラフを作りたい。頂点0〜頂点iの最短距離はdist0[i], 頂点1〜頂点iの最短距離はdist1[i]でないといけない。
  • 各辺の距離は 1. 作れるならその一例、作れなければ空を返せ。
  • 2≦N≦50
  • (TCO出忘れたのであとで)
  • 考察
  • 連結なので頂点0からの距離が1の頂点は必ずある。
  • 同じく頂点0からの距離が M なものがあったら dist0 には 1〜M が含まれる。
  • 頂点0 から距離 1 の頂点は頂点0と必ず繋がっている必要がある。(頂点0は1個なので)
  • 頂点0 から距離 2 の頂点は頂点0 から距離 1 の頂点のどれかと繋がっている必要がある。
  • 頂点1からの距離制約があるので、全部繋げてよいとは限らない。
  • 繋げていいやつだけ繋げてどれかと繋がったか判定すればよさそう
  • 繋げていいかどうかは、繋げたとき頂点1の距離制約を破らなければよい。
  • u, v を繋げるとして、u, v の頂点1 からの距離の差の絶対値が2以上のときに繋げると頂点1からの距離の差が1になってしまうのでだめ
  • 元々 1 以下のときはOKなので実際に繋げる
  • 最後にできたグラフをWFしてdist0, dist1と矛盾ないかチェック (これやってなくてWA)
  • Accepted in practice

void add(vector<string>& w, int n0, int n1) {
	w[n0][n1] = w[n1][n0] = 'Y';
}

class DistanceZeroAndOne {
	public:
	vector <string> construct(vector <int> d0, vector <int> d1) {
		ll N = d0.size();
		if(!(d0[0]==0 && d0[1]==d1[0] && d1[1]==0)) return {};

		vector<string> g(N, string(N, 'N'));
		VVI n0(N), n1(N);
		REP(i, N) n0[d0[i]].PB(i);
		REP(i, N) n1[d1[i]].PB(i);
		RANGE(i, 1, N) {
			ll pi = i-1;
			for(int v2 : n0[i]) {
				bool any=false;
				for(int v1 : n0[pi]) {
					if(abs(d1[v1]-d1[v2]) < 2) {
						any=true;
						add(g, v1, v2);
					}
				}
				if(!any) return {};
			}
			for(int v2 : n1[i]) {
				bool any=false;
				for(int v1 : n1[pi]) {
					if(abs(d0[v1]-d0[v2]) < 2) {
						any=true;
						add(g, v1, v2);
					}
				}
				if(!any) return {};
			}
		}
		VVI w(N, VI(N, 1LL<<60));
		REP(i, N) REP(j, N) if(g[i][j]=='Y') w[i][j]=1;
		REP(i, N) w[i][i]=0;
		REP(k, N) REP(i, N) REP(j, N) w[i][j] = min(w[i][j], w[i][k]+w[k][j]);
		REP(i, N) if(d0[i]!=w[0][i]) return {};
		REP(i, N) if(d1[i]!=w[1][i]) return {};
		return g;
	}
};

2017-05-07

AtCoder Grand Contest 014 D - Black and White Tree

09:56 |  AtCoder Grand Contest 014 D - Black and White Tree - kojingharangの日記 を含むブックマーク はてなブックマーク -  AtCoder Grand Contest 014 D - Black and White Tree - kojingharangの日記  AtCoder Grand Contest 014 D - Black and White Tree - kojingharangの日記 のブックマークコメント

  • 木が与えられる。先手は白、後手は黒で塗られてない頂点を順番に塗っていく。塗れなくなったら黒頂点に隣接する頂点を全部黒にする。
  • 白が残ってたら先手の勝ち。最適にプレイしたらどっちが勝つか求めよ。
  • 2≦頂点数≦10^5
  • 葉とその親がどちらも白になったら白が勝つ。
  • という状態を作り出すには、葉である子が 2 個以上ある頂点を最初に白に塗ればいい。
  • 最初にそういうのがなかったら? う〜む
  • 葉である子が 1 個だけの頂点を白に塗ったら、次はその葉を黒にするしかない。
  • ? - 親 - 葉 の親と葉を消していくといい?
  • それ以外のとこに白を塗ることで勝てることはあるんじゃないかとかいろいろもやっとして終わり
  • 帰納法で完全マッチングあり←→後手勝ちが証明できるようだ。
  • ? - 親 - 葉 の親と葉を消せるだけ消して、1頂点になった or 葉である子が 2 個以上ある頂点があったら First, なければまた繰り返し、消えなくなったら Second でよかった
  • solve1 で remove_if は計算量的にやばいかなと思ったが時間は solve2 と同じくらいだった。
  • solve1 は実装だけならできていたかもしれないので、証明がいまいちできない時はそれっぽい実装を進めてしまうというのもありだなぁ特に何回でも試せるコンテストでは。
  • solve2 は実際にはノードを消さないちょい賢い方法。あまり思いつく気はしない。
  • Accepted in practice
ll N;

// ノードを実際に消していく版
// ? - A - B があったとき A, B を消しまくる。葉である子が 2 個以上ある頂点がでてきたら First
// 頂点が 1 個になっても First
// なければまた繰り返し
// 消えなくなったら Second 
string solve1(VVI& g) {
	while(1) {
		ll edges = 0;
		REP(i, N) {
			int cnt=0;
			edges += g[i].size();
			for(int j : g[i]) {
				if(g[j].size()==1) cnt++;
			}
			if(cnt>=2) {
				return "First";
			}
		}
		edges/=2;
		if(edges==0) return "First";

		// i - adj - X =... -> X =...
		bool ch=false;
		REP(i, N) {
			if(g[i].size()==1) {
				int adj = g[i][0];
				if(g[adj].size()==2) {
					int X = g[adj][0]==i ? g[adj][1] : g[adj][0];
					{
						auto en = remove_if(ALL(g[X]), [=](int a) { return adj==a; });
						g[X].erase(en, g[X].end());
					}
					g[adj].clear();
					g[i].clear();
					ch=true;
				}
			}
		}
		if(!ch) break;
	}
	return "Second";
}

// return: このノード以下で完全マッチの相手を探しているノードの個数
ll dfs(int u, int p, VVI& g) {
	ll x = 0;
	for(int v: g[u]) if(v!=p) x += dfs(v, u, g);
	if(x==0) return 1; // need to match ... 子が全部マッチしてるので
	if(x==1) return 0; // matched
	return INF; // 余りが確定したので無理
}

// ノードを消さないスマート版
string solve2(VVI& g) {
	// rest==0 ←→ 完全マッチしている
	ll rest = dfs(0, -1, g);
	string ans = rest ? "First" : "Second";
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	string s;
	while(cin>>N) {
		VVI g(N);
		REP(i, N-1) {
			ll A, B;
			cin>>A>>B;
			A--;B--;
			g[A].PB(B);
			g[B].PB(A);
		}

//		string ans = solve1(g);
		string ans = solve2(g);

		cout<<ans<<endl;
	}
	
	return 0;
}

2017-05-01

Google code jam 2017 Round1C B. Parenting Partnering (DP編)

16:42 |  Google code jam 2017 Round1C B. Parenting Partnering (DP編) - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2017 Round1C B. Parenting Partnering (DP編) - kojingharangの日記  Google code jam 2017 Round1C B. Parenting Partnering (DP編) - kojingharangの日記 のブックマークコメント

  • (あとで)
  • DPでも解けるということでやってみた。なるほど簡潔だ。
// dp[i][j][k][l]
// = 最初の割当が i (0:A 1:B), j+1分終わった時点, A の割当時間が k 分, 最後の割当が l (0:A 1:B) な状態での, 日をまたぐ切り替えを考慮しない最小切り替え回数
int dp[2][1440][721][2];

int INF = 1<<30;

int main() {
	int test_cases;
	cin>>test_cases;
	ll A,B, s, e;
	REP(ttt, test_cases) {
		cin>>A>>B;
		VI tl(1440, -1); // 0: A 1: B -1: none
		REP(i, A) {
			cin>>s>>e;
			RANGE(i, s, e) tl[i] = 0;
		}
		REP(i, B) {
			cin>>s>>e;
			RANGE(i, s, e) tl[i] = 1;
		}
		REP(bi, 2) REP(mi, 1440) REP(ai, 721) REP(ei, 2) dp[bi][mi][ai][ei] = INF;
		REP(bi, 2) REP(ei, 2) dp[bi][0][ei==0][ei] = bi!=ei;
		REP(bi, 2) REP(mi, 1440) REP(ai, 721) REP(ei, 2) REP(nei, 2) {
			int old = dp[bi][mi][ai][ei];
			int nbi = bi;
			int nmi = mi+1;
			int nai = ai + (nei==0);
			int cost = ei!=nei;
			if(nmi<1440 && tl[nmi]!=nei && nai<=720) {
				dp[nbi][nmi][nai][nei] = min(dp[nbi][nmi][nai][nei], old + cost);
			}
		}
		int ans = INF;
		REP(bi, 2) REP(ei, 2) {
			// 日をまたぐ切り替えの考慮
			int lans = dp[bi][1439][720][ei]+(bi!=ei);
			ans = min(ans, lans);
		}

		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

2017-04-30

Google code jam 2017 Round1C B. Parenting Partnering

21:14 |  Google code jam 2017 Round1C B. Parenting Partnering - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2017 Round1C B. Parenting Partnering - kojingharangの日記  Google code jam 2017 Round1C B. Parenting Partnering - kojingharangの日記 のブックマークコメント

  • C,Jが1日のうち半分ずつ子守をする。C,Jそれぞれ子守できない予定(時間帯)が決まっている。
  • 子守役を入れ替える回数の最小値を求めよ。

  • 半分ずつ子守をしなくていいとしたときの最低交換回数 + 半分制約ありで隙間時間を割り当てた時の追加交換回数 でいいだろう
  • 予定と予定の間の隙間時間は、「前 or 次」の予定が「C or J」の 4 種類に分類できる。
  • 前と次の予定がどっちも C である隙間時間(★)に C が子守すると往復で 2 回の追加交換が必要。追加コストを払ってしまえば C, J どちらにどちらでも割り当てられるので、その隙間時間についてコストはそれ以上増えない。
  • J も同じ。
  • それ以外は追加コスト 0
  • なので
  • どちらに割り当てても良い時間の残り RestC, RestJ から
  • ★なものを追加コストがかからないように優先して割り当てる(あとで回数が問題になるので短い順に見る)
  • どちらに割り当ててもよい時間を割り当てる
  • 残りをしかたなく追加コストを払って★から割り当てる
  • という方針でいいだろう
  • ここまではわりとすぐ
  • 隙間を列挙する、最低交換回数を求めるあたりで大ハマリ。
  • sample 実行したら、日の最初と最後が違う人なら交換回数に含めなきゃいけないのに気づく
  • →隙間列挙が場合分けコードでどんどん汚くなりバグりまくって焦る
  • 残り30分であきらめて C に移動
  • small は、掛け算だし最小のやつに fill してけばよかろう→これ以下ならfillするという値で二分探索→ 一発OK
  • 残り15分で戻ってくるがバグバグでだめ
  • (あとで)
  • すっきり再実装、終了15分後にB small+large AC
  • 実装ゲーは相当落ち着いてやらないといかん。
  • 🤔🤔
// 予定
struct Entry {
	ll s, e, type;
};

int main() {
	int test_cases;
	cin>>test_cases;
	ll A,B, s, e;
	REP(ttt, test_cases) {
		cin>>A>>B;
		ll ra = 720, rb = 720; // のこり割当時間
		ll fr = 1440; // どっちに割り当ててもノーペナな枠
		vector<Entry> es;
		REP(i, A) {
			cin>>s>>e;
			ra -= e-s;
			fr -= e-s;
			es.push_back(Entry{s, e, 1});
		}
		REP(i, B) {
			cin>>s>>e;
			rb -= e-s;
			fr -= e-s;
			es.push_back(Entry{s, e, -1});
		}
		VI pa, pb; // dur
		ll N = 1440;
		sort(ALL(es), [](const Entry& a, const Entry& b){return a.s<b.s;});

		ll ans = 0;
		ll M = es.size();
		REP(i, M) {
			ll ni = (i+1)%M;
			if(es[i].e%N != es[ni].s%N) {
				// すきまはっけん
				if(es[i].type == es[ni].type) {
					ll dur = (es[ni].s-es[i].e+N)%N;
					if(es[i].type==1) pa.PB(dur);
					if(es[i].type==-1) pb.PB(dur);
				}
			}
			if(es[i].type!=es[ni].type) ans++;
		}
		
		sort(ALL(pa));
		sort(ALL(pb));

		REP(i, pa.size()) fr -= pa[i];
		REP(i, pb.size()) fr -= pb[i];

		// ペナルティ回避
		REP(i, pa.size()) {
			ll use = min(ra, pa[i]);
			ra -= use;
			pa[i]-=use;
		}
		REP(i, pb.size()) {
			ll use = min(rb, pb[i]);
			rb -= use;
			pb[i]-=use;
		}

		// ノーペナ消費
		{
			ll use = min(ra, fr);
			ra -= use;
			fr -= use;
		}
		{
			ll use = min(rb, fr);
			rb -= use;
			fr -= use;
		}

		// ペナルティ
		REP(i, pb.size()) {
			ll use = min(ra, pb[i]);
			if(use) ans+=2;
			ra -= use;
		}
		REP(i, pa.size()) {
			ll use = min(rb, pa[i]);
			if(use) ans+=2;
			rb -= use;
		}
		assert(ra==0);
		assert(rb==0);

		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

2017-04-18

SRM 712 300 LR

22:28 |  SRM 712 300 LR - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 712 300 LR - kojingharangの日記  SRM 712 300 LR - kojingharangの日記 のブックマークコメント

  • 長さ N の数列 s, t が与えられる。最初と最後はつながっている。
  • 操作 L: 左の要素と現在の要素を足したものを新しい要素の値とする
  • 操作 R: 右の要素と現在の要素を足したものを新しい要素の値とする
  • 操作 L, R を最大 100 回行って s が t になるならその手順、ならなければ "No solution" を返せ。
  • 2≦N≦50, 0≦要素≦10^15
  • 1 0 0 0 から始めるとどうなるか? → 1 1 -> 1 2 1 -> 1 3 3 1 -> 二項係数になる。→特に発展せず
  • 探索してくと意外とすぐ狭まるやつ? →どうもそうでもない
  • 逆から考えると何か分かるか? →わからず
  • 数列の合計は L, R どちらをやっても 2 倍に増える
  • なので 10^15≒2^50 ということで解があるなら 50 回くらいやれば十分。
  • う〜ん
  • (しばらくして)
  • 紙上で A B C D E を LL LR RL RR してどうなるか見てみると LR RL が同じになりそう
  • 実験くん
  • 全部並びとしては同じで、適用結果はLL...LLL の結果を R の数だけ左回転したものになる
  • (気づくのが遅い)
  • Σt = 2^M*Σs のとき、s に L を M 回適用した後の並びを M 回以下の R 回左シフトしたものが t と一致したら R 個の 'R' と M-R 個の 'L' をつなげたやつが答え。
  • Challengeされる
  • 🤔
  • Σs==0 のとき無条件に "No solution" にしていたorz orz
  • Σs==0 でも s==t なら "" を返すんだった。
  • せっかく思いついたのにもったいない.....
  • 🤔
  • Accepted in practice
VI rot(const VI& a, char d) {
	int lr = d=='L' ? -1 : 1;
	int N = a.size();
	VI rv(N);
	REP(i, N) rv[i] = a[(i+lr+N)%N]+a[i];
	return rv;
}

VI rotN(const VI& a, string d) {
	VI rv(a);
	for(auto c : d) rv = rot(rv, c);
	return rv;
}

VI shiftL(const VI& a) {
	int N = a.size();
	VI rv(N);
	REP(i, N) rv[i] = a[(i+1)%N];
	return rv;
}

class LR {
	public:
	string construct(vector<long long> s, vector<long long> t) {
		ll ss = accumulate(ALL(s), 0LL);
		ll st = accumulate(ALL(t), 0LL);
		if(ss>st) return "No solution";
		if(ss==st) {
			return s==t ? "" : "No solution";
		}
		if(ss==0) return "No solution";
		int cnt = 0;
		{
			bool ok = false;
			while(ss<=st) {
				if(ss==st) {
					ok=true;
					break;
				}
				ss*=2;
				cnt++;
			}
			if(!ok) return "No solution";
		}
		VI w(s);
		REP(i, cnt) {
			w = rot(w, 'L');
		}
		bool ok = false;
		int R = 0;
		REP(i, s.size()) {
			if(w==t) {
				ok = true;
				break;
			}
			w = shiftL(w);
			R++;
		}
		if(ok && R<=cnt) {
			string ans(cnt, 'L');
			REP(i, R) ans[i] = 'R';
			assert(t==rotN(s, ans));
			return ans;
		}
		return "No solution";
	}
};