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

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

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

解いた/挑んだ問題

A問題

問題の概要

プログラミングコンテストを開く上で100点,200点,300点,400点が一問ずつ必要です。
100点,200点,300点,400点問題が各 $A_i$ 個あります。
合計で何回コンテストを開けるでしょうか

制約

$1 \leq A_i \leq 100(1 \leq i \leq 4)$
入力はすべて整数

どのように考えたか

各コンテストの問題数の最小値を出力

結果

1発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,c,d;
	cin >> a >> b >> c >> d;
	cout << min({a,b,c,d}) << endl;
	return 0;
}

A問題らしい問題だった

ACまでの時間

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

f:id:iiiimmmmo:20201213231502p:plain — ABC185_A

B問題

問題の概要

高橋君は、自宅からM回カフェを訪れて自宅に戻ります
カフェiには $時刻A_iに入り時刻B_i$ に出ます
高橋君はスマホのバッテリーがN[mAh]で、外の場合時刻0.5,1.5,2.5ずつつまり時刻n+0.5(nは整数)を迎えるたびに1[mAh]減り、
カフェに滞在している時は時刻n+0.5(nは整数)を迎えるたびに1[mAh]充電されます
ただし、スマホの最大バッテリー容量を超えて充電はされません
高橋君は、家に戻るまでにスマホの充電を維持していられますか

制約

$1 \leq N \leq 10^9$
$1 \leq M \leq 1000$
$1 \leq T \leq 10^9$
$0 < A_1 < B_1 < A_2 < B_2 < A_3 < B_3 < ・・・< A_M < B_M < T$
入力はすべて整数

どのように考えたか

カフェに入る時刻 $A_i$ と出る時刻 $B_i$ を配列に入れておいて、
カフェに入るまでに減ったバッテリーと、カフェから出たときの充電されたバッテリーの状態を管理して
途中で0以下になったらbool型の変数をFalseに落として最後にbool型の変数を見てyes/noを出した

結果

1発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,m,t,a,b,bat,time=0;
	bool ans = true;
	cin >> n >> m >> t;
	bat = n;
	rep(i,m){
		cin >> a >> b;
		int tmp = a - time;
		bat -= tmp;
		if(bat <= 0){ans = false;break;}
		tmp = b-a;
		time = b;
		bat = min(bat+tmp,n);
	}
	int tmp = t - time;
	bat -= tmp;
	if(bat <=0)ans = false;
	//Yes/Noを返す
	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

B問題にしては難しいなと思った

ACまでの時間

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

f:id:iiiimmmmo:20201213233934p:plain — ABC185_B

C問題

問題の概要

長さLの棒を長さが全て正整数の12個に分割するとき、分割方法は何通りありますか

制約

$12 \leq L \leq 200$
$L$ は整数

どのように考えたか

$_{n-1}C_{r-1}$ で求まりそうだと思って実装した

結果

オーバーフローに気づかず、2回WAを出してしまった
・提出したコード

#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<ll, ll>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

void reduce(ll *m, ll *n){
  ll g = gcd(*m, *n);
  *m /= g;
  *n /= g;
}
ll enum_combination(ll n, ll k)
{
  /* C(n,k) = n / k * C(n-1,k-1) というように求める */
  /* 答えがオーバーフローしない範囲の k は、それほど大きくない (k <- n-k の置き換えにより)
     ので、再帰はそれほど深くならない
  */
  if ( n - k < k ) {
    /* n から n-k 個と、n から k 個 の選びかたは同じ */
    return enum_combination(n, n-k);
  } else if ( k == 1 ) {
    return n;
  } else {
    ll a = enum_combination(n-1, k-1);
    /* n * a / k は整数。k の因数は、n, a の両方に含まれている可能性がある */
    reduce(&n, &k);             /* n,k の共通因数をなくす */
    assert( a % k == 0 );
    a /= k;                     /* a,k の共通因数をなくす */
    return a * n;
  }
}

int main() {
	ll a;
	cin >> a;
	if(a == 12){
		cout << 1 << endl;return 0;}
	ll ans = enum_combination(a-1,11);
	cout << ans << endl;
	return 0;
}

オーバーフローにもっと早く気づきたかった

ACまでの時間

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

f:id:iiiimmmmo:20201213234607p:plain — ABC185_C

D問題

問題の概要

左右方向1列にN個のマスが並んでいます。
そのうちの $M$ 個のマスは青色で、 $A_i$ で表されそれ以外は白いマスです。
好きな幅のスタンプをマスを塗る前に作成し、青色のマスを塗らないように連続したマスを赤で塗ります。
途中でスタンプの幅を変えることはできません
なるべく塗る回数を最小化したとき、何回で塗れますか

制約

$1 \leq N \leq 10^9$
$0 \leq N \leq 2 × 10^5$
$1 \leq A_i \leq N$
$A_i$ は互いに異なる
入力はすべて整数

どのように考えたか

連続している白いマスのマス数を配列で管理し、最小の値を出す。
既に赤い色はもう一度塗ってもいいので、白いマス/最小値の繰り上げをカウントする

結果

1発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,m,ans=1000000000,cnt=0;
	cin >> n >> m;
	if(m == 0){cout << 1 << endl; return 0;}
	vector<int>arr(m),gc(m+1);
	rep(i,m)cin >> arr[i];
	sort(all(arr));
	gc[0] = arr[0] - 1;
	rep(i,m-1){
		gc[i+1] = arr[i+1]-arr[i]-1;
	}
	gc[m] = n - arr[m-1];
	rep(i,m){
		if(gc[i] == 0)continue;
		chmin(ans,gc[i]);
	}
	rep(i,m+1){
		cnt += ceil((double)gc[i]/ans);
	}
	cout << cnt << endl;
	return 0;
}

最初最大公約数を求める問題だと思って実装が遅れた

ACまでの時間

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

f:id:iiiimmmmo:20201214000332p:plain — ABC185_D

F問題

問題の概要

長さNの配列があり、各値は $A_i$ です。
M個のクエリ( $T_i,X_i,Y_i)$ が投げられ、 $T_i$ が1の場合は $A_{X_i}をA_{X_i}⊕Y_i$ で置き換え、
$T_i$ が2の場合は $A_{X_i}からA_{Y_i}$ の排他的論理和を出力せよ

制約

$1 \leq N \leq 300000$
$1 \leq Q \leq 300000$
$1 \leq A_i \leq 2^{30}$
$T_i$ は1または2
$T_i = 1なら 1 \leq X_i \leq Nかつ0 \leq Y_i \leq 2^{30}$
$T_i = 2なら 1 \leq X_i \leq Y_i \leq N$
入力はすべて整数

どのように考えたか

セグ木を使った

結果

1発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;}

#define SEG_LEN (1LL << 19LL)

ll seg[SEG_LEN * 2LL];

void add(ll ind,ll v){
	ind += SEG_LEN;
	seg[ind] ^= v;
	while(true){
		ind /=2LL;
		if(ind == 0)break;
		seg[ind] = seg[ind * 2LL] ^ seg[ind * 2LL + 1LL];
	}
}

ll sum(ll l,ll r){
	l += SEG_LEN;
	r += SEG_LEN;
	ll ans = 0;
	while(l < r){
		if(l%2 == 1){
			ans ^=seg[l];
			l++;
		}
		l/=2;
		if(r % 2 == 1){
			ans ^= seg[r-1];
			r--;
		}
		r /= 2 ;
	}
	return ans;
}

int main() {
	ll n,q,a,t,b;
	cin >> n >> q;
	rep(i,n){
		cin >> a;
		add(i+1,a);
	}
	rep(i,q){
		cin >> t >> a >> b;
		if(t == 1){
			add(a,b);
		}else{
			cout << sum(a,b+1) << endl;
		}
	}
	return 0;
}