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

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

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

解いた/挑んだ問題

A問題

問題の概要

整数Nが与えられる
$3^A + 5^B = N$ となるような正の整数の組 $(A,B)$ が存在する場合はA,Bを空白区切りで出力
存在しない場合は-1を出力せよ

制約

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

どのように考えたか

配列に $10^{18}を超えない、3^nと5^n$ を入れ、二重ループを回して一致したら配列の添え字+1を出力
そうでない場合、-1を出力

結果

・提出ししたコード

#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 all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    ll n, a, b;
    cin >> n;
    vector<ll>x(37), y(25);
    for (int i = 0; i < 37; i++) { x[i] = ll(pow(3, i+1)); }
    rep(i, 25)y[i] = ll(pow(5, i+1));
    rep(i,37) {
        rep(j, 25)if (0 < (n - x[i]) && (n - x[i]) == y[j]) {
            cout << i+1 << " " << j+1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

powで誤差が生まれることを知らずに提出していました

ACまでの時間

コンテスト中に通すことはできていません

f:id:iiiimmmmo:20201025013754p:plain — ARC106_A

B問題

問題の概要

N頂点Ｍ辺の単純無向グラフが与えられ、i番目の辺は頂点 $c_iと頂点d_i$ を結んでいる
頂点iには値 $a_iが書かれており、次の操作を0回以上行いb_i$ にしたい

頂点xとyを結んでいる辺を1つ選び、

- $a_xを-1し、b_xを+1する$
- $a_xを+1し、b_xを-1する$

制約

$1 \leq N \leq 2 × 10^5$
$0 \leq M \leq 2 × 10^5$
$-10^9 \leq a_i,b_i \leq 10^9$
$1 \leq c_i,d_i \leq N$
与えられるグラフは単純グラフである。すなわち、自己ループや多重辺は存在しない。
入力はすべて整数

どのように考えたか

連結している頂点では、好きに値を足したり引いたり可能なので、連結した頂点の値の和が $a_iとb_i$ で等しければ目標を達成可能
それをUnionFind(ACLのDSU)でmargeし、各頂点(v)の属している代表頂点(l)をmapのkeyとし、map[l]に $a_vを足してb_v$ を引いた
mapのvalueがすべて0の場合目的の達成が可能

結果

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 all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int n, m,c,d;
	bool ans = true;
	cin >> n >> m;
	dsu uni(n);
	vector<ll>a(n), b(n);
	vector<vector<ll>>v(n, vector<ll>());
	vector<pi>p(n);
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	rep(i, m) {
		cin >> c >> d;
		c--, d--;
		//p[i] = pi(c, d);
		//v[c].push\_back(d);
		//v[d].push\_back(c);
		uni.merge(c, d);
	}
	map<ll, ll>mp;
	int q = 0;
	rep(i, n) {
		q = uni.leader(i);
		mp[q] += a[i];
		mp[q] -= b[i];
	}
	for (auto mm : mp) {
		if (mm.second != 0)ans = false;
	}
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}