tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

DDCC 2017 決勝

Contest

ブログを最近書かなさすぎで変な広告まで登場する有様なので、渋々記事を書く。

A

まあこれは良いでしょう。

int main(){
	int a;scanf("%d",&a);
	int A=0;
	int B=0;
	for(int i=-100;i<100;i+=a){
		for(int j=-100;j<100;j+=a){
			if(i*i+j*j<=10000&&(i+a)*(i+a)+j*j<=10000&&i*i+(j+a)*(j+a)<=10000&&(i+a)*(i+a)+(j+a)*(j+a)<=10000)A++;
		}
	}
	for(int i=-150;i<150;i+=a){
		for(int j=-150;j<150;j+=a){
			if(i*i+j*j<=22500&&(i+a)*(i+a)+j*j<=22500&&i*i+(j+a)*(j+a)<=22500&&(i+a)*(i+a)+(j+a)*(j+a)<=22500)B++;
		}
	}
	
	printf("%d %d\n",A,B);
}

B

よく考えて解いてないのですが、制約から素因数分解ができないとわかるので、GCDとLCMに収まると思えばこのくらいしか選択肢がありません。

long long p[110000];
long long gcd(long long a,long long b){
	while(b){
		a%=b;
		swap(a,b);
	}return a;
}
int main(){
	int a;
	long long b;
	scanf("%d%lld",&a,&b);
	for(int i=0;i<a;i++)scanf("%lld",p+i);
	long long ret=1;
	for(int i=0;i<a;i++){
		long long g=gcd(b,p[i]);
		ret=ret/gcd(ret,g)*g;
	}
	printf("%lld\n",ret);
}

C

これについて何も書かないとこの記事の存在意義がないので、これについては何か書きます。

もし辺を編集することが全くできないのなら、この問題は簡単で、1回DFSをするだけで良いです。(ある頂点から始めて、今までにたどった重みの和を持ちながら辺をたどっていきます。辺の行く先がすでに通ったことがある頂点だったら、その頂点までの重みの和と今回の和が同じかどうかをチェックします。全部同じだったら全部の閉路について和が0です。)
辺を編集する場合ですが、基本的に編集する代わりにその辺を見なければいいです(全部の頂点に和が計算できていれば、そこの辺のコストは差で計算できます)。ただ、変なたどり方(毎回頂点1からDFSするとか)をすると、その辺が存在しないことで到達不可能な頂点が出てきてしまったりしてまずいので、必ずその見ない辺の行き先からDFSをスタートする必要があります。(行き先からDFSをスタートすると全頂点に値がつけられるというのは、強連結性のおかげです。)

さて、一番本質ですが、この同じ行き先の辺を消すパターン全てを1回にまとめて判定することができます。というのも、別に辺を消す処理が頂点までの和の値とかに影響を与えることはないので、実際にたどってみて「この辺が存在するとマズイ！」って時だけ消したことにすればいいからです。
で、消す辺がどれかとかが重要なのではなく、消す必要がある辺が1個以下であることが大事で、各頂点からDFSをしていき、消すべき辺が1個以下なことが1回でもあったらYESです。そうでなければNOです。

下の実装ではよく整理していないせいで逆辺を辿っていますが、上に書いた解法と何ら変わりありません。辺の向きを全部逆にしただけだと思います。

vector<pair<int,int> > g[310];
vector<pair<int,int> > rev[310];
long long deg[310];
int v[310];
int T;
bool dame=false;
int cnt=0;
void dfs(int a){
	v[a]=1;
	for(int i=0;i<rev[a].size();i++){
		int to=rev[a][i].first;
		if(v[to]){
			if(to!=T&&deg[a]+rev[a][i].second!=deg[to])dame=true;
			else if(deg[a]+rev[a][i].second!=deg[to])cnt++;
			continue;
		}
		deg[to]=deg[a]+rev[a][i].second;
		dfs(to);
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);p--;q--;
		g[p].push_back(make_pair(q,r));
		rev[q].push_back(make_pair(p,r));
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)deg[j]=v[j]=0;
		T=i;
		dame=false;
		cnt=0;
		dfs(i);
		if(!dame&&cnt<=1){
			printf("Yes\n");return 0;
		}
	//	printf("\n");
	}
	printf("No\n");
}

まとめ

まあこんなんで3位で10万円分のパソコンが買えるというのは不思議だと思っているのですが、後から振り返ってみるとCの思考の分量というのは決してやるだけ、無ということはなくて、ただやるべきことが瞬時に見えていた感じがします。Div1Easyみたいな難しくないものを高速で解くのは昔から得意なんですが、それが如実に結果に反映される問題セットでしたね。
Dみたいなのは日本人はみんな苦手でかつ難易度を過小評価されがちな問題なので、セットとしての解かれなさもよく分かります。

それより、何か10万円強くらいのパソコンでおすすめのものがあったら教えてください。切実。