Codeforces Round#10 B,C

Practiceで解いた奴。

B - Cinema Cashier

問題概要

k列にそれぞれk個の席があるような映画館の座席をチケットの販売員が次のように決定する(kは奇数)。

  • m人の客がチケットを買うとき、m人が同じ列に連続して座れるようにする
  • なるべく中心に近い座席(Σ|xi-cx|+|yi-cy|が最小になる)ように座席を割り当てる(ただしcx,cyはもっとも中央の座席)
  • 中心への近さが同じような座席の選び方が複数ある場合、x座標がもっとも小さい席に割り当てる
  • それでも選び方複数ある場合y座標の最小値がもっとも小さくなるように割り当てる


mのリストが与えられた時に、割り当てる座標のx座標、y座標の最小値、y座標の最大値を出力せよ。その割り当てが不可能な場合-1を出力せよ。

解説

kは最大でも99なので、総当りで調べても十分計算時間は間に合う。
なので左上から席がm個確保できるか全部調べていき、もっとも「中心からの近い」席の座標を返せばよい。


以下のコードでは、

  • 確保する座席が各列中央の席をまたいでいない場合、両端に人がいなければおk
  • 座席が、既に座っているような列中央の席をまたいでいた場合はNG

と判別することでO(n^2)になっている。がもともと間に合う上に、使った座席を記録する部分にO(m)がかかっているので全くの無駄である。

ソースコード
void run()
{
	int n,k,c; cin>>n>>k;
	c=k/2;
	bool seat[99][99]={0};
	
	rep(nn,n)
	{
		int m; cin>>m;
		
		int mind=inf,minx,miny;
		rep(j,k)rep(i,k)
		{
			if(i+m-1>=k||seat[i][j]||seat[i+m-1][j])continue;
			if(i<=c&&c<=i+m-1&&seat[c][j])continue;
			
			int d=abs(j-c)*m; rep(ii,m)d+=abs(i+ii-c);
			if(mind>d)mind=d,minx=j,miny=i;
		}
		if(mind==inf)cout<<-1<<endl;
		else
		{
			cout<<minx+1<<" "<<miny+1<<" "<<miny+m<<endl;
			rep(i,m)seat[miny+i][minx]=1;
		}
	}
}

C - Digital Root

問題概要

自然数nのデジタル根を、一桁になるまで「その数の各桁の和をとる」操作を繰り返した結果であるとする。(例 d(1234)=d(1+2+3+4)=d(1+0)=1)


今、1≦N≦10^6なる整数Nが与えられたとき、

  • 1以上N以下の三つの整数の組(a,b,c)で、
  • a*b≠cかつd(a*b)=d(c)を満たすようなものの総数を求めよ。
解法

任意の自然数a,bに対してd(a)*d(b)=d(a*b)が成り立つことを示す。(☆)
d(n)= n%9 (if n%9 != 0)
d(n)= 9 (otherwise)であるため成り立つ。


よって、d(a)*d(b)=d(a*b)が成り立つようなa,bの数から、1以上N以下の自然数を使って得られる掛け算の総数を引いたものが求める答えとなる。



砕いて言うと、本来の積が等しくないのに、デジタル根同士の積が等しくなってしまう場合の総数を求めたいのである。


更に、元の掛け算が正しければデジタル根同士の掛け算も正しくなるというのが(☆)である。
よって、デジタル根の積の全てのパターンから、正しい掛け算の総数を引けば、デジタル根だけが正しくなってしまっている掛け算の総数が求まるという理屈である。


あとは掛け算のオーバーフローに注意して実装する。

ソースコード
int dist[10];

int memo[1000001];
int d(int n)
{
	if(memo[n])return memo[n];
	int m=n;
	while(m>9)
	{
		int s=0;
		while(m)s+=m%10,m/=10;
		m=s;
		if(memo[m])return memo[n]=memo[m];
	}
	return memo[n]=m;
}

void run()
{
	int n; cin>>n;
	rep(i,n)dist[d(i+1)]++;
	
	
	ll ans=0;
	rep(i,9)rep(j,9)ans+=(ll)dist[i+1]*dist[j+1]*dist[d((i+1)*(j+1))];
	
	int i=1;
	for(;i<=n;i++)ans-=n/i;
	
	cout<<ans<<endl;
}