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

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

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

解いた/挑んだ問題

A問題

問題の概要

Dメートル先にある公園に向かって分速Sメートルで走ったとき、T分後にはついているかどうか

制約

$1 \leq D \leq 10000$
$1 \leq T \leq 10000$
$1 \leq S \leq 10000$
入力はすべて整数

どのように考えたか

S*T とDを比較してS*TがD以上かどうか

結果

一発AC
・提出ししたコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(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() {
	int d, t, s;
	cin >> d >>  t >> s;
	bool ans = false;
	if ((t * s) >= d)ans = true;
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

比較的簡単な問題だった

ACまでの時間

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

f:id:iiiimmmmo:20200829232556p:plain — ABC177_A

B問題

問題の概要

文字列S,Tが与えられる
文字列Tが文字列Sの部分文字列になるためにTを最小限いくつ書き換える必要があるか

制約

S,Tは1文字以上1000文字以下
Tの長さはSの長さ以下
S,Tは英小文字のみ含む

どのように考えたか

SとTの文字数の差の数繰り返しを行い
Tの文字分Sから抜き出し、一文字ずつ比較し文字が違うときにカウント
変数ansにカウントとのminをとり結果を出力

結果

一発AC
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(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() {
	string s, ss,t;
	int cnt = 0;
	int ans = 1000000;
	cin >> s >> ss;
	rep(i, s.size() - ss.size() + 1) {
		t = s.substr(i, ss.size());
		cnt = 0;
		rep(j, ss.size()) {
			if (ss[j] != t[j])cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

少しバグりそうで怖かった

ACまでの時間

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

f:id:iiiimmmmo:20200829232724p:plain — ABC177_B

C問題

問題の概要

Ｎ個の整数 $A_1,...,A_N$ が与えられる
$1 \leq i < j \leq N$ を満たす全ての組(i,j)についての $A_i × A_jの和をmod(10^9 + 7)$ で求めよ

制約

$2 \leq N \leq 2×10^5$
$0 \leq A_i \leq 10^9$
入力はすべて整数

どのように考えたか

愚直に二重ループを行うとTLEしてしまうので(1回目)、同類項を纏めるために累積和を使いO(N)で求める

結果

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

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(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() {
	int n;
	ll mod = 1e9 + 7;
	cin >> n;
	vector<ll>As(n+1,0),A(n);
	ll a;
	rep(i, n) {
		cin >> a;
		A[i] = a;
		As[i + 1] = As[i] + a;
	}
	ll ans = 0;
	rep(i, n - 1) {
		ans += (A[i] * ((As[n] - As[i+1]) % mod));
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}