Atcoder Beginner Contest 101 - ykmakuのブログ

問題はこちら。AtCoder Beginner Contest 101 - AtCoder

A - Eating Symbols Easy

ans = 0から始めて、Sの各文字が+なら+1、-なら-1する。

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string s;
	cin >> s;
	int ans = 0;
	for(int i = 0; i < 4; i++){
		if(s[i] == '+') ans++;
		else ans--;
	}

	cout << ans << endl;

	return 0;
}

B - Digit Sums

S(N)を求めるにはNを10で割った余りを足して、Nを10で割る、ということを繰り返す。ループでも書けるがミスしやすい(僕だけ?)上に再帰で書けるし再帰のほうがスマート。

#include <iostream>

using namespace std;

int S(int n){
	if(n<10) return n;
	else return n%10+S(n/10);
}

int main()
{
	int n;
	cin >> n;

	if(n%S(n) == 0) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

C - Minimization

ちょっと考えると数列を全て1にすることを考えれば良いことがわかる。K個の連続した要素を選ばないといけないという条件から、1回の操作で新しく1になる数列の要素の数はK-1個であることがわかる。したがって少なくとも $\lceil(N-1)/(K-1)\rceil$ 回の操作が必要。実はうまく操作を行うとこの回数ですべての要素を1にできる。ってことで入力のうちNとKだけで答えが出力できる。アホなのでceil()の中のdoubleを忘れがち。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <numeric>
#include <cmath>

using namespace std;

int main()
{
	int n,k;
	cin >> n >> k;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}

	cout << ceil((double)(n-1)/(k-1)) << endl;

	return 0;
}

コンテスト中は焦ってわかんなくなったので次のことをした。まず最初の操作はK個の中に1を含んでないといけない。元の数列のうち最初に選んだK個の要素より左側を全て1にするのは左側の要素数をLとしたら $\lceil(L+1)/(K-1)\rceil$ 回でできる。右側も同様。最初に選ぶK個のうち1が何番目に来れば操作回数が最小になるかをループを回して探索する。

焦るのよくない。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int main()
{
	int n,k;
	cin >> n >> k;
	vector<int> a(n+1);
	int p = -1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] == 1) p = i;
	}

	int ans = INF;
	
	for(int i = 0; i < k; i++){
		int res = ceil((double)max(p+i-k,0) / (k-1));
		res += ceil((double)max(n-p-i,0)/(k-1));
		res++;
		if(res<ans) ans = res;
	}

	cout << ans << endl;

	return 0;
}

D - Minimization

難しい。解説をぱっと見た時ほんとに500点か？？？と思ったけど分かれば納得。

$\frac{N}{S(N)}$ がどんな感じの値になるのかよく分からないのでちょっと実験してみると数字の末尾が...999の形が怪しいとわかる。Nが与えられた時にN以上の数ですぬけ数になるもののうち最小のものを求めることを考える。Nの1桁目から順にその桁の数字を9に変えていくことを考える。9以外の場合は？と思うかもしれないが、よく考えるとi桁目の数字を変える場合、9じゃない数字よりも9に変えたほうが良いことが分かる。すぬけ数の桁数は高々15桁なのでNが与えられる度にすぬけ数の候補を15個作る。その中で最小のものを出力する。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

ll S(ll n){
	if(n<10) return n;
	else return n%10+S(n/10);
}

double snuke(pair<ll,ll> p){
	return (double)p.first/p.second;
}

ll f(ll n){

	vector<pair<ll,ll> > res;

	for(int d = 0; d < 15; d++){
		ll x = pow(10,d)*floor((double)n/pow(10,d)+1)-1;
		pair<ll,ll> y;
		y.first = x;
		y.second = S(x);
		res.push_back(y);
	}

	ll m = res[0].first;
	double ms = snuke(res[0]);

	for(int i = 0; i < res.size(); i++){
		if(ms > snuke(res[i])){
			m = res[i].first;
			ms = snuke(res[i]);
		}
	}

	return m;
}

int main()
{
	ll k;
	cin >> k;
	ll a = 1;
	for(int i = 1; i <= k; i++){
		cout << a << endl;
		a = f(a+1);
	}

	return 0;
}

感想

300点問題を10分程度で解けるようになりたい。今回みたいな全完した人が少ない場合、みんなができる問題(A~C)をはやく解く事が大事。解法にたどり着くのも大事だけど速くて正確なコーディングを目指す必要がある。500点はまあちょっとずつ勉強していく感じで。