imomoの勉強記録

主に勉強の記録などを残していきます

トップ > ARC振り返り記事 > キーエンス プログラミング コンテスト 2021に参加しました

キーエンス プログラミング コンテスト 2021に参加しました

ARC振り返り記事

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

解いた/挑んだ問題

A問題

問題の概要

長さN の数列a,bがあり、a,bのi番目の数はそれぞれ、a_i,b_iです。
これらの数列を使って新たに長さNの数列cを作ります。
c_kは、1 \leq i \leq j \leq Nを満たすa_{i}b_jの最大値です。
c_1,c_2,...,c_Nを求めて下さい

制約
  • 1 \leq N \leq 2 × 10^5
  • 1 \leq a_i,b_i \leq 10^9
  • 入力はすべて整数
どのように考えたか

制約により、c_0は、a_0b_0のみと分かる
c_1は、a_0b_0,a_0b_1,a_1b_1のいずれかであり、
c_2は、a_0b_0,a_0b_1,a_1b_1,a_0b_2,a_1b_2,a_2b_2となる

これらから、c_i (1 \leq i \leq N-1)はc_{i-1}と、a_k (0 \leq k \leq i)の最大値とb_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,v,n) for(long long i = v; i <= (long long)(n); i++)
#define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--)
#define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--)
#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;
	ll am = 0;
	cin >> n;
	vector<ll>a(n),b(n),c(n);
	rep(i,n)cin >> a[i];
	rep(i,n)cin >> b[i];
	c[0] = a[0] * b[0];
	am = a[0];
	REP(i,1,n-1){
		chmax(am,a[i]);
		c[i] = max(c[i-1],am * b[i]);
	}
	for(auto v:c)cout << v << endl;
	return 0;
}

ノートに書き出してみたら、計算量を削減する方法を簡単に見つけられてうれしかった。

ACまでの時間

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

f:id:iiiimmmmo:20210116231819p:plain
keyence2021_A

B問題

問題の概要

整数が書かれたボールがN個、ボールを入れる箱がK個あります。
ボールを箱に入れると、箱の蓋に、箱の中に入ってるボールの数字以外の最小の非負整数が表示されます。
なお、ボールが一つも入っていない箱は0と表示されます。
全てのボールを箱に入れたとき、箱の蓋に表示される数の総和の最大値を求めて下さい。

制約
  • 1 \leq K \leq N \leq 3 × 10^5
  • 0 \leq a_i < N
  • 入力はすべて整数
どのように考えたか

ボールに書かれている数が1の場合、Ball_1と表すことにする
Ball_0を箱に振り分ける、入らなかった箱は蓋に0と表示される
Ball_1を、Ball_0の入った箱に振り分ける、入らなかった箱は蓋に1と表示される
Ball_2を、Ball_1の入った箱に振り分ける、入らなかった箱は蓋に2と表示される
のように繰り返し、前に入れたボールの数+1を箱に入れることができなかったら、箱の蓋の合計値を出す。

結果

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,v,n) for(long long i = v; i <= (long long)(n); i++)
#define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--)
#define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--)
#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,k,a,N;
	ll ans = 0;
	cin >> n >> k;
	map<ll,ll>mp;
	rep(i,n){
		cin >> a;
		mp[a]++;
	}
	N = n;
	ll v,tmp=0;
	rep(i,N){
		v = min(mp[i],k);
		if(v == 0){
			ans += i*n;
			break;
		}else{
			chmin(v,n);
			tmp = n - v;
			ans += i*tmp;
			n -= tmp;
		}
		if(n == 0)break;
	}
	cout << ans << endl;
	return 0;
}

考えはすぐに浮かんだが、実装でバグらないか心配だった

ACまでの時間

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

f:id:iiiimmmmo:20210116231835p:plain
keyence2021_B

結果

コンテスト結果

ABの2完でした
A.Bだけだが、ノーペナで通せてよかった

f:id:iiiimmmmo:20210116231847p:plain
keyence2021

パフォーマンス、レーティング変動

今回のパフォーマンスは967、前回より400近く上がりました。
レーティングはそれに伴い+34の697となりました。

f:id:iiiimmmmo:20210116232404p:plain
コンテスト成績表
f:id:iiiimmmmo:20210116232425p:plain
キーエンス プログラミング コンテスト 2021を終えた時点でのレーティング

反省点

ARCは冷えてしまうときはがっつり冷えてしまうので、A.Bを解けたと思ってから念入りに確かめてから提出しました。
結果的に温まることができて嬉しいです。
念入りにやりすぎて提出する時間が遅くなってしまったので、次はもっと確認する時間を早めたり、自信を持てるコードを書きたいです。