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

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

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

解いた/挑んだ問題

A問題

問題の概要

Nキロまで荷物を載せられるトラックにWキロのレンガはいくつ乗せられるか

制約

$1 \leq N,W \leq 1000$
N,Wは整数である

どのように考えたか

N/Wの小数点以下切り捨てを出力した

結果

一発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,w;
	cin >> n >> w;
	cout << n/w << endl;
	return 0;
}

最初荷物とトラックの積載量を逆にしてて焦った

ACまでの時間

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

f:id:iiiimmmmo:20201219230708p:plain — ABC186_A

B問題

問題の概要

縦Hマス、横Wマスに $A_{ij}$ 個ブロックが置かれている
全てのマスでブロックを同じにするとき、何個ブロックを取り除く必要があるか

制約

$1 \leq H,W \leq 100$
$1 \leq A_{i,j} \leq 100$

どのように考えたか

与えられるブロックの中の最小値*H*Wを与えられたすべてのブロックから引いた

結果

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 h ,w,a,ans=0,tmp=0,mi=100000,sum=0;
	map<int,int>mp;
	cin >> h >> w;
	rep(i,h)rep(j,w){
		cin >> a;
		sum += a;
		chmin(mi,a);
		mp[a]++;
	}
	ans = sum -= mi*h*w;
	cout << ans << endl;
	return 0;
}

少し戸惑ったが、全体から余計な分を引くといいことが分かってから安心して実装できた

ACまでの時間

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

f:id:iiiimmmmo:20201219231343p:plain — ABC186_B

C問題

問題の概要

1以上N以下の数を10進法と8進法で表したとき7が含まれない数の個数はいくつあるか

制約

$1 \leq N \leq 10^5$
Nは整数である

どのように考えたか

1～Nまでを10進数と8進数に変換する過程で7が見えたらカウントせず、それ以外はカウント

結果

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() {
	bool f=false,ff=false;
	int n,cnt=0,t,tt;
	cin >> n;
	REP(i,n){
		f = ff = false;
		t = tt = i;
		while(t){
			if(t%10==7){f = true;break;}
			t/=10;
		}
		while(tt){
			if(tt%8==7){ff=true;break;}
			tt/=8;
		}
		if(!f && !ff)cnt++;
	}
	cout << cnt << endl;
	return 0;
}

最初難しそうと思って敬遠してたら割と簡単だった

ACまでの時間

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

f:id:iiiimmmmo:20201219231847p:plain — ABC186_C

D問題

問題の概要

$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}|A_i - A_j|$ を求めよ

制約

$2 \leq N \leq 2 × 10^5$
$|A_i| \leq 10^8$
$A_i$ は整数である

どのように考えたか

全ての組についての絶対値をとるので数列はソートしても答えは変わらないので絶対値を外してもいいように大きい順にソートする
$A_i - A_i,A_i - A_{i+1},...,A_i - A_n$ は、 $A_i × (N-i) - (A_{i+1}+A_{i+2}+,...,+A_n$ と変わらないので、累積和をとり総和を高速に計算し
$A_iからA_{n-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, 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,a,ans=0;
	cin >> n;
	vector<ll>arr(n),arrsum(n+1,0);
	rep(i,n)cin >> arr[i];
	sort(rall(arr));
	rep(i,n){
		arrsum[i+1] = arrsum[i] + arr[i];
	}

	rep(i,n){
		ll tmp = arrsum[n] - arrsum[i+1];
		ll res = arr[i] * (n-i-1);
		ans += (res - tmp);
	}
	cout << ans << endl;
	return 0;
}