Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

2017-08-15

SRM 719 Div1 500 OwaskiAndTree

20:02 |  SRM 719 Div1 500 OwaskiAndTree - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 719 Div1 500 OwaskiAndTree - kojingharangの日記  SRM 719 Div1 500 OwaskiAndTree - kojingharangの日記 のブックマークコメント

  • 1000頂点までの木が与えられる。頂点0から順に辺で行けるとこを何回でも移動できる。
  • 頂点 i を最初に訪れたときスコアに pleasure[i] in [-10^6, 10^6] が足される。スコアが負になったら自動的に0まで回復する。
  • スコアの最大値を求めよ。
  • DPぽい
  • (頂点, そこにくる直前のスコア) → 最良スコア は無理
  • (頂点, 直前のスコアが0 or 十分大きい) → スコア(?) みたいな感じでいけないか
  • なんかだめだ
  • おわり

(あとで)

これ見たときは「は??」という感想だったが、よーく考えてみると分かった。

必要な考察

  • 問題のルールに従うと、頂点 v0 → v1 → v2 → ... と辿ったときスコアの計算は以下のようになる。

(あ) v0 → 操作A → v1 → 操作A → v2 → 操作A → v3 ... → 操作A

操作A : スコアが負なら 0 にする

  • この値は、以下の計算方法で求まるスコアの最大値と同じになる。

(い) 操作B → v0 → 操作B → v1 → 操作B → v2 → 操作B → v3 ... → 操作B

操作B : スコアを 0 にリセットすることができる

  • 理由: 操作Bのとき、スコアが負ならリセット、正ならリセットしなければ (あ) と一致する
  • さらにこれは以下の最大値と等しい。

(う) 操作B → v0 → 操作B → v1 → 操作B → v2 → 操作B → v3 ... → 操作B ※ただしリセットは高々 1 回だけ

  • 理由: もしあれば、(う) のリセットポイントを (い) の最後のリセットポイントと同じにすれば、最後以外はリセットしなくても同じなので (い) と一致する

ということで

  • 全頂点は「最初に訪れた時リセット前」「最初に訪れた時リセット後」「訪れない」に分類できる。
  • それぞれ BR, AR, NONE と書く。
  • リセットしない場合は最初にリセットすると考えて全頂点が AR or NONE である状態に対応する。
  • 最後にリセットする場合は全頂点が BR or NONE である状態に対応する。
  • あとは、以下を求めていけば max ( f(0, BR), f(0, AR) ) が答えとなる。

f(頂点 v, v の状態) = v 以下のサブツリーのスコアの最大値


(v, AR) = v でリセット後ということはその子ノードは訪れないかリセット後じゃないといけないので pleasure[v] + Σ f(子ノード, AR|NONE)

(v, NONE) = 子ノードも全部 NONE なので 0

(v, BR) = pleasure[v] はどうせリセットされるのでカウントしない。各子ノードは AR でも BR でも NONE でもよいので Σ f(子ノード, BR|AR|NONE)

ほう〜 こんなすっきりとなるのか〜

(accepted in practice)

class OwaskiAndTree {
	public:
	int maximalScore(vector <int> pa, vector <int> pl) {
		int N = pa.size()+1;
		VI br(N);
		VI ar(N);
		// 葉から順に配ると簡潔に書ける ... lhic さんの実装を参考にした
		for(int i=N-1; i>=0; i--) {
			ar[i] += pl[i];
			ar[i] = max(ar[i], 0LL);
			if(i) {
				int pi = pa[i-1];
				ar[pi] += ar[i];
				br[pi] += max(br[i], ar[i]);
			}
		}
		return max(br[0], ar[0]);
	}
};

2017-06-28

Codeforces #412 Mister B and PR Shifts (Div2 D, Div1 B)

18:51 |  Codeforces #412 Mister B and PR Shifts (Div2 D, Div1 B) - kojingharangの日記 を含むブックマーク はてなブックマーク -  Codeforces #412 Mister B and PR Shifts (Div2 D, Div1 B) - kojingharangの日記  Codeforces #412 Mister B and PR Shifts (Div2 D, Div1 B) - kojingharangの日記 のブックマークコメント

  • [1, N] の permutation が与えられる。
  • Σ^{N}_{1} |rotate_right(p, j)[i]-i| の最小値とそのときの j を求めよ。
  • 2≦N≦10^6
  • すごく規則性がありそう
  • N^2 で実装して実験くん
  • N=10で適当な例を試したら広義単調増加→減少となめらかに変わってそうなので三分探索
  • 三分探索初めて書くので非常に怪しい
  • WA

(あとで)

  • N = 1000 くらいでランダムケースを見てみたら全然なめらかに変わってなかった...
  • ちょっとずつずらしたときに某値とその変化量がどれくらい変わるかを最初に O(N) で求めておいて O(N) でちょっとずつずらしていくやり方があるようだ。
  • 書いてみるが超絶ムズい...
  • なんとか通ったけど +1 -1 とか不等号に等号が付くかとか場合分けとか無限にバグる要素ある。

(accepted in practice)

void solve(ll N, const VI& w, ll& minVar, ll& ans) {
	VI varDiff(N+10), deltaDiff(N+10);
	ll var = 0;
	REP(i, N) {
		VI& dd = deltaDiff;
		// 無限にバグるパート
		if(w[i]>i+1) {
			// 最初 -1 で idx1 のときに +1 になる. また idx3 で -1 になる
			dd[0] += -1;

			int idx1 = w[i]-(i+1);
			dd[idx1] += +2;

			int idx3 = N-(i+1)+1;
			dd[idx3] += -2;
		} else {
			// 最初 +1 で idx1 のときに -1 になる. また idx3 で +1 になる
			dd[0] += +1;

			int idx1 = N-((i+1)-w[i]);
			dd[idx1] += +2;

			int idx3 = N-(i+1)+1;
			dd[idx3] += -2;
		}

		{
			// 回転した瞬間に var が調整される
			int idx = N-(i+1)+1;
			ll v = -(N-(w[i]-1)) + (w[i]-1);
			varDiff[idx] += v;
		}
		var += abs(w[i]-(i+1));
	}
	minVar = var;
	ans = 0;
	ll delta = deltaDiff[0];
	RANGE(i, 1, N) {
		var += varDiff[i] + delta;
		delta += deltaDiff[i];
		if(var<minVar) {
			minVar = var;
			ans = i;
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	ll N;
	while(cin>>N) {
		VI w(N);
		REP(i, N) cin>>w[i];
		ll minVar, ans;
		solve(N, w, minVar, ans);
		cout<<minVar<<" "<<ans<<endl;
	}
	
	return 0;
}

おまけ: メモ

/*
方針:

変化量 = 0
varDiff[i]: i 回目の始めに var が変化する分.
deltaDiff[i]: i 回目の始めに変化量が変化する分
var = rot0でのスコア
loop
	var += 変化量 + varDiff[i]
	変化量 += deltaDiff[i]


5
5 4 3 2 1
での想定動作

0
	-1 -1 -1 -1  1
	deltaDiff
	-1  0  0  0  1
1
	-1 -1  1  1 -1
	deltaDiff
	-1  0  2  0 -2
2
	 1  1  1 -1 -1
	deltaDiff
	 1  0  0 -2  0
3
	 1  1 -1  1  1
	deltaDiff
	 1  0 -2  2  0
4
	 1  1  1  1  1
	deltaDiff
	 1  0  0  0  0

sum
	 1  1  1  1  1



12
8
	12 += -5 +1
6
	8 += -3 +1
6
	6 += -1 +1
8
	6 += +1 +1


0
	p   o
	 p o
	  p
	 o p
	o   p

	delta
		0 -1
		1 -1
		2  1
		3  1
		4  1
		sum 1

1
	 p  o
	  po
	  op
	 o  p
	p

	delta
		0 -1
		1 -1
		2  1
		3  1
		4  1
		sum 1

2
	  p o
	   p
	  o p
	po   
	op

	delta
		0 -1
		1  1
		2  1
		3 -1
		4  1
		sum 1

3
	   po
	   op
	p o  
	 p   
	o p

	delta
		0 -1
		1  1
		2 -1
		3  1
		4  1
		sum 1

4
		p
	p  o 
	 po  
	 op  
	o  p

	delta
		0  1
		1 -1
		2 -1
		3  1
		4  1
		sum 1

*/

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;
}