izumo’s diary

主に競プロの精進記録

AtCoder Beginner Contest 112

競プロ

水色として臨む初めてのABCでした。unratedなので気楽にできると思っていたら気楽にしすぎて大量にWAをくらいました（苦笑）。結果はA, B, Dの3完でした。

使用言語: C++

A - Programming Education

問題
Nで場合分けして出力。入力もNによって変わることに注意する。

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a, b;
	cin>>n;
	if(n==1){
		cout<<"Hello World"<<'\n';
	}
	else{
		cin>>a>>b;
		cout<<a+b<<'\n';
	}
	return 0;
}

B - Time Limit Exceeded

問題

すべての基本”全探索”

N 個の経路について順番に調べる。t_i \leq T なら c_iを見る。これまでの経路のコストより小さかったらコストを c_i に更新する。最初にコストを1000より大きい値にしておくと、調べ終わったときにコストが更新されていなければTLEと判断できる。 

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(n); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, T, c, t;
	cin>>n>>T;
	int ans=1333;
	REP(i, n){
		cin>>c>>t;
		if(t<=T){
			ans=min(ans, c);
		}
	}
	if(ans!=1333){
		cout<<ans<<'\n';
	}
	else{
		cout<<"TLE"<<'\n';
	}
	return 0;
}

C - Pyramid

問題

すべての基本”全 (ry

まず、座標(x_i, y_i)の高度がh_iなので
h_i=0 \iff H-|x_i-C_X|-|y_i-C_y|\leq 0 \iff H \leq |x_i-C_X|+|y_i-C_y|・・・(1)
h_i>0 \iff H-|x_i-C_X|-|y_i-C_y|=h_i \iff H=h_i+|x_i-C_X|+|y_i-C_y|・・・(2)
よって中心座標を固定すると h_i>0 のとき H は一意に定まるので、中心座標を全探索すればよい。
Hの値が確定するまで H の値の範囲を狭め、確定したらという(1), (2)が成立するか調べるという方針で実装したら複雑になってしまいコンテスト中に解けなかった。実は h_i>0 となる i は必ず存在するので次のコードよりもっと簡単に書くことができる。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<(n); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, x[114], y[114], h[114];
	cin>>n;
	REP(i, n){
		cin>>x[i]>>y[i]>>h[i];
	}
	REP(c1, 101){
		REP(c2, 101){
			bool f=false, ok=true;
			int H=1<<30;
			REP(i, n){
				// Hが確定したら等式、不等式が成立するか調べる
				if(f){
					if(h[i]==0){
						if(H>abs(x[i]-c1)+abs(y[i]-c2)){
							ok=false;
							break;
						}
					}
					else if(H!=h[i]+abs(x[i]-c1)+abs(y[i]-c2)){
						ok=false;
						break;
					}
				}
				// Hが確定するまで
				else{
					// Hの範囲を狭める
					if(h[i]==0){
						H=min(H, abs(x[i]-c1)+abs(y[i]-c2));
					}
					// Hが狭めた範囲にない場合は不適
					else if(H<h[i]+abs(x[i]-c1)+abs(y[i]-c2)){
						ok=false;
						break;
					}
					// Hが確定
					else{
						H=h[i]+abs(x[i]-c1)+abs(y[i]-c2);
						f=true;
					}
				}
			}
			if(ok && H>=1){
				cout<<c1<<' '<<c2<<' '<<H<<'\n';
				return 0;
			}
		}
	}
	return 0;
}

別解

すべての基本 (ry

これは解説放送のコメントで見たのだが、h_i \leq H \leq h_i+200 なので中心座標に加えて高さ H も全探索できる。ループの回数は101 \times 101 \times 200 \times N 回で最悪10^8 回くらい。等式と不等式の判定だけなので間に合うらしい (8ms, 速い、速くない？) 。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a, x[114], y[114], h[114];
	cin>>n;
	REP(i, n){
		cin>>x[i]>>y[i]>>h[i];
		if(h[i]){
			a=i;
		}
	}
	REP(c1, 101){
		REP(c2, 101){
			FOR(H, h[a], h[a]+201){
				bool ok=true;
				REP(i, n){
					if(h[i]){
						if(H!=h[i]+abs(x[i]-c1)+abs(y[i]-c2)){
							ok=false;
							break;
						}
					}
					else if(H>abs(x[i]-c1)+abs(y[i]-c2)){
						ok=false;
						break;
					}
				}
				if(ok){
					cout<<c1<<' '<<c2<<' '<<H<<'\n';
					return 0;
				}
			}
		}
	}
	return 0;
}

D - Partition

問題
求める答えを x とおくと a_i=x \times b_i (b_iは整数) と表せる。よって
M= \displaystyle \sum_{i=1}^{N} a_i=x \displaystyle \sum_{i=1}^{N}b_i
となるので xはM の約数であることが分かる。約数は O( \sqrt{M})で求めることができるので、順番に約数を見ていって数列 \{a_i\} を作れるか調べる。

  1. x> \frac{M}{N} のときは明らかに不適。
  2. x \leq \frac{M}{N} のときは a_i=x \ (i=1, …, N-1), \ a_N=M-x (N-1) とすれば \{a_i\} を構成できる。

よって \frac{M}{N} 以下の M の約数のうち最大の数が答え。
冷静に考えればそんなに難しくないのだがC問題を平行して考えていたためこの解法は終了10分前に思いついた。

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define REP(i, n) for(int i=0; i<(n); ++i)

// 約数を求める
vi divisor(int n){
	vi res;
	for(int i=1; i*i<=n; ++i){
		if(n%i==0){
			res.push_back(i);
			if(i!=n/i){
				res.push_back(n/i);
			}
		}
	}
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin>>n>>m;
	if(n==1){
		cout<<m<<'\n';
		return 0;
	}
	int ans=0;
	vi x=divisor(m);
	REP(i, x.size()){
		if(x[i]<=m/n){
			ans=max(ans, x[i]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

別解

すべての (ry

何と約数を列挙しなくても \frac{M}{N} 以下の数について M の約数か調べるだけでもよいらしい。ループの回数は最悪 5 \times 10^8 回くらいなのだが、剰余と等式の判定だけなので間に合うようだ (60ms) 。ジャッジが少し甘いかもしれないが最悪のケース \left(N=2,\ M=999999937\right) をコードテストしても1460msだった。

#include <bits/stdc++.h>
using namespace std;
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin>>n>>m;
	FORR(i, 1, m/n+1){
		if(m%i==0){
			cout<<i<<'\n';
			return 0;
		}
	}
	return 0;
}