ABC182に参加しました - imomoの勉強記録

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題
結果
- コンテスト結果
- パフォーマンス、レーティング変動
反省点

解いた/挑んだ問題

A問題

問題の概要

あるSNSでは、フォロー数を、2×(フォロワー数)＋100を超えない範囲で増やせる
現在のフォロー数Aとフォロワー数Bが与えられる
いくつ増やせるか出力せよ

制約

$0 \leq A,B \leq 10000$
$B \leq 2 × A + 100$
入力はすべて整数

どのように考えたか

問題文に沿って(2*A + 100) - Bを出力する

結果

一発AC
・提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	int a,b;
	cin >> a >> b;
	cout << (a*2 + 100) - b << endl;
	return 0;
}

A問題にしては難しめだと感じた

ACまでの時間

ACしたのはコンテスト開始から2分後です。

f:id:iiiimmmmo:20201108230105p:plain — ABC182_A

B問題

問題の概要

数列 $A(A_1,A_2,A_3,...,A_N)$ が与えられる
正の整数kのGCD度を数列Aを割り切れる数　と定義する
2以上の整数でGCD度が最大になるものを一つ出力せよ

制約

$1 \leq N \leq 100$
$2 \leq A_i \leq 1000$
入力はすべて整数

どのように考えたか

数列の最大値が1000なので、2から1000まで全探索して、GCD度数が最大のものを出力

結果

一発AC
提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	int n,a,ans,cnt=0,mcnt=0;
	cin >> n;
	vector<int>v(n);
	rep(i,n){
		cin >> v[i];
	}
	FOR(i,2,1001,1){
		cnt=0;
		afor(m,v){
			if(m%i == 0)cnt++;
		}
		if(chmax(mcnt,cnt))ans = i;
	}
	cout << ans << endl;
	return 0;
}

問題の理解までにとても時間がかかった

ACまでの時間

ACしたのはコンテスト開始から8分後です。

f:id:iiiimmmmo:20201108230119p:plain — ABC182_B

C問題

問題の概要

各桁に0が出現しないような正の整数Nが与えられる
Nの桁数をkとして、Nの桁を0以上k未満消して、残った桁を結合して3の倍数を作りたい
3の倍数ができるか判定し、できる場合は作るのに必要な最小の数を出力せよ、できない場合は-1を出力せよ

制約

$1 \leq N \leq 10^{18}$
入力はすべて整数

どのように考えたか

最大でも18桁しかないので、bit全探索をして最小の消す数を求める

結果

二回目でAC
・提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	string s;
	int n,tmp=0,cnt=0,ans=100;
	bool f=false;
	cin >> s;
	n = s.size();
	vector<int>v;
	afor(a,s){
		v.push_back(a - '0');
	}
	afor(a,v)tmp+=a;
	if(tmp%3==0){cout << 0 << endl;return 0;}
	for(int b = 0;b <(1 << n);b++){
		tmp=0;cnt=0;
		rep(i,n){
			if(b & (1<<i)){tmp += v[i];cnt++;}
		}
		if(0 < tmp && tmp%3==0){
			chmin(ans,n - cnt);
			f = true;
		}
	}
	if(f)cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}

消す数と残す数を逆にしてしまっておりミスしてしまった。

ACまでの時間

ACしたのはコンテスト開始から30分後。

f:id:iiiimmmmo:20201108230135p:plain — ABC182_C

D問題

問題の概要

数列 $A(A_1,A_2,A_3,...,A_N)$ が与えられる
最初0の位置にいるロボットが、以下の動作を順に行う

正の向きに $A_1$ 進む。
正の向きに $A_1$ 進み、正の向きに $A_2$ 進む.
正の向きに $A_1$ 進み、正の向きに $A_2$ 進み、正の向きに $A_3$ 進む

～省略～

正の向きに $A_1$ 進み、正の向きに $A_2$ 進み、正の向きに $A_N$ 進む

動作開始から終了時まで、ロボットの座標の最大値を求めよ

制約

$1 \leq N \leq 200000$
$-10^8 \leq A_i \leq 10^8$
入力はすべて整数

どのように考えたか

最初の動作終了後、二番目の動作終了後、三番目の動作終了後・・・N-1番目の動作終了後の座標を配列で藻っておき、ロボットが進む向きで現時点で最大となる値を持っておく。
各動作終了後に、現時点で最大となる値を足した値が現時点で最大なら保持する。

結果

3回目でAC
・提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;
ll pows(ll x, ll n) { ll ret = 1; while (n > 0) { if (n & 1) ret *= x; x *= x; n >>= 1; }return ret; }

int main() {
	ll n, x;
	ll ans = 0, lmax = 0, tmp = 0;
	cin >> n;
	vector<ll>v(n + 1);
	rep(i, n) {
		cin >> x;
		tmp += x;
		chmax(lmax, tmp);
		chmax(ans, v[i] + lmax);
		v[i + 1] += v[i] + tmp;
	}
	if (lmax <= 0)cout << 0 << endl;
	else {
		cout << ans << endl;
	}
	return 0;
}