Particle

競技プログラミングについての雑記

SRM 675 Div1 Easy TreeAndPathLength3

この回は個人的に Easy も Med も面白い問題だと思った。

s が小さいとき (497 以下のとき) は、パスグラフでも 500 頂点を超えないようにできる。
そうでないときは、1 頂点 u の周りに 101 個頂点をくっつけた木を考えて、その周りに 頂点を付け足していくとうまく構成することができる。
s が残り 100 以上であれば、u から距離 2 離れた頂点を追加する。このとき、毎回別の頂点に隣接するように追加しなければならないことに注意する。すると、長さ 3 のパスが 100 増えるので、s を 100 減らす。
s が残り 100 未満であれば、前のステップで追加した頂点の先に頂点を s 個パス状に追加する。 1 頂点追加するごとに長さ 3 のパスが 1 つ増える。

ワーストケースは、s = 9999 の場合で、300 頂点になる。

class TreeAndPathLength3 {
	public:
	vector <int> construct(int s) {
		vector<int> res;
		if(s<100){
			rep(i, s+2){
				res.pb(i);
				res.pb(i+1);
			}
			return res;
		}
		rep(i, 101){
			res.pb(101);
			res.pb(i);
		}
		int t = 102;
		while(s>=100){
			res.pb(t);
			res.pb(t-102);
			s -= 100;
			t++;
		}
		while(s){
			res.pb(t);
			res.pb(t-1);
			s--;
			t++;
		}
		return res;
	}
};