kojingharangの日記

Codeforces Round #129 Div1 A - Little Elephant and Interval

22:48 |

• 整数 A, B が与えられる。A≦X≦B な整数 X で、X を10進表記したときに最初と最後の桁が同じものの個数を求める問題。
• 1≦A, B≦10^18

• 1～x の範囲で条件にあうものの個数を計算する f(x) を書いて f(B) - f(A-1) すればよさげ
• 1桁ずつ見ていけばいいのでは
• x が N 桁として N-1 桁以下のものは [1-9]???[1-9] の形なので簡単そう
• N 桁のやつは最上位が x のやつ（これに大ハマリ）とそれ未満のやつに分けるかも
• naive なリファレンスを書いて一致を確認するがどうにも合わない

• 気づいたら90分...
• リファレンスと高速版で 10000 まで一致してることを確認してるので提出後の精神状態は良好
• Accepted
• 上位陣は5分くらいの模様。簡潔なのが多いなぁ

ll ff(ll d) {
	if(d==0) return 0;
	if(d==1) return 1;
	ll ans=1;
	REP(i, d-2) ans*=10;
	return ans;
}

ll ref(ll v) {
	ll co=0;
	for(int i=1;i<=v;i++) {
		ll msd=i;
		while(msd/10>0) {msd/=10;}
		if(msd==i%10) co++;
	}
	return co;
}

ll f(ll v) {
	if(v<10) return ref(v);
	if(v==0) return 0;
	ll msd=v, co=0;
	while(msd/10>0) {msd/=10;co++;}
	ll msdd=msd;
	REP(i, co) msd*=10;
	ll t=v, di=0;
	while(t>0) {t/=10;di++;}
	ll X = 0;
	int xok=0;
	{
		ll mm = (v-msd)/10;
		while(msd+(mm*10+msdd) > v && mm > 0) {
			mm--;
		}
		X = msd+(mm*10+msdd);
		if(X<=v) xok = 1;
	}
	ll vv= xok ? (X-msd)/10 +1 : 0;
	ll lower=0;
	REP(i, di) lower += 9*ff(i);
	ll ans= vv+(msdd-1)*ff(di)+lower;
	return ans;
}

int main() {
	//REP(i, 10000) {
	//	ll ra=ref(i);
	//	ll fa=f(i);
	//	if(ra!=fa) {cout<<"ERR"<<i<<" "<<ra<<" "<<fa<<endl;return 0;}
	//}
	
	ll L,R;
	while(cin>>L>>R) {
		cout<<f(R)-f(L-1)<<endl;
	}
	
	return 0;
}

ツイートする

Codeforces Round #129 Div1 B - Little Elephant and Cards

22:48 |

• 10^5 個までの表を向いたカードがあって表裏にそれぞれ 10^9 までの整数が書いてある。
• カードの半分以上が同じ数字になるようにするには最小で何枚ひっくり返せばいいか。

• 半分以上揃う数字はせいぜい 4 つくらいしかない
• map で出現個数を数えて、あてはまるものについて「全体の半分 - すでに表をむいてる枚数」の最小を求める。
• 表裏同じ数字の場合は１回だけカウントするところで 1WA
• 表の枚数も map で数えたが count(ALL(F), c) でも大丈夫だと思う

• Accepted

#define INF (1LL<<60)

int main() {
	ll N;
	while(cin>>N) {
		ll half=(N+1)/2;
		map<ll, ll> hi;
		map<ll, ll> hiF;
		VI F(N), B(N);
		REP(i, N) {
			cin>>F[i]>>B[i];
			hi[F[i]]++;
			if(F[i]!=B[i]) hi[B[i]]++;
			hiF[F[i]]++;
		}
		//cout<<F<<B<<endl;
		//cout<<hi<<endl;
		VI cand;
		FOR(e, hi) {
			if(e->second >= half) cand.PB(e->first);
		}
		//cout<<cand<<endl;
		ll ans = INF;
		REP(i, cand.size()) {
			ll c = cand[i];
			//ll rest = half - count(ALL(F), c);
			ll rest = half - hiF[c];
			ans = min(ans, max(0LL, rest));
		}
		
		cout<<(cand.size() ? ans : -1LL)<<endl;
	}
	
	return 0;
}

ツイートする