ABC340
概要
A - Arithmetic Progression
考えてたこと
等差数列とか懐かしいですね。存在する入力しか与えられないからテキトーで問題ない。
提出したもの
int main() {
int a, b, d;
cin >> a >> b >> d;
while (true) {
cout << a << " ";
if (a == b)
break;
a += d;
}
return 0;
}
振り返り
特になし。
B - Append
考えてたこと
毎回reverseしたら流石に計算量足りなそうだなぁと思って文字を追加した回数をカウントすることにしました。
提出したもの
int main() {
int q;
cin >> q;
int cnt = 0;
vector<int> vec;
rep(i, -0, q) {
int a, x;
cin >> a >> x;
if (a == 1) {
vec.push_back(x);
cnt++;
} else {
cout << vec[cnt - x] << endl;
}
}
return 0;
}
振り返り
カウントしなくても文字サイズを取得すれば良いだけだった。
C - Divide and Divide
考えてたこと
最初は2のn乗だから...みたいに考えるのかと思ったけど、制約が10^17だったからそれだとTLE起こすと気づく。再帰でなんとかなりそうって思ったらなんとかなった。
提出したもの
map<ll, ll> m;
ll calc(ll n) {
if (n == 1)
return 0;
if (m.count(n)) {
return m[n];
} else {
m[n] = calc(n / 2) + calc((n + 1) / 2) + n;
return m[n];
}
}
int main() {
ll n;
cin >> n;
ll ans = calc(n);
cout << ans << endl;
return 0;
}
振り返り
制約のおかげで最初の方針がうまくいかないと気づいて逆に正解できた節がある。そもそも2のn乗だから...みたいなことを考えた時点で再帰の方針を考えるべきだった。
D - Super Takahashi Bros.
考えてたこと(1回目)
最小値を取るから各経路に着くまでの最小時間を更新し続けてnの最小時間を出力すれば良いと考えてしたみたいなコードを書く、ただ書きながら9->2->10みたいな経路の時失敗するだろうなぁと思ってたらやはり失敗。
上から順に更新するんじゃなくて、1->2, 1->8だったら2,8を見るように更新された部分を見る必要がありそう...?と考える。
提出したもの
int main() {
int n;
cin >> n;
// vec[i]はステージiに行くまでの最小移動時間
vector<ll> vec(n + 1);
for (int i = 2; i <= n; i++) {
vec[i] = LONG_LONG_MAX;
}
vec[1] = 0;
for (int i = 1; i < n; i++) {
int a, b, x;
cin >> a >> b >> x;
vec[i + 1] = min(vec[i + 1], vec[i] + a);
vec[x] = min(vec[x], vec[i] + b);
}
cout << vec[n] << endl;
return 0;
}
考えてたこと(2回目)
queue使って通った経路そこに放りこんでいけば良いかなぁと思って実装、実装自体は悪くなさそうだけどTLEが解消されなくて解説を覗き見...。
提出したもの
int main() {
int n;
cin >> n;
int a[n + 1];
int b[n + 1];
int x[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> x[i];
}
// vec[i]はステージiに行くまでの最小移動時間
vector<ll> vec(n + 1);
for (int i = 2; i <= n; i++) {
vec[i] = LONG_LONG_MAX;
}
vec[1] = 0;
queue<int> queue;
queue.push(1);
while (queue.size()) {
int now = queue.front();
queue.pop();
if (vec[now] + a[now] < vec[now + 1]) {
vec[now + 1] = vec[now] + a[now];
if (now + 1 != n) {
queue.push(now + 1);
}
}
if (vec[now] + b[now] < vec[x[now]]) {
vec[x[now]] = vec[now] + b[now];
if (x[now] != n) {
queue.push(x[now]);
}
}
}
cout << vec[n] << endl;
return 0;
}
考えてたこと(3回目)
解説見てこれがダイクストラなんだと知る、あと不勉強反省。
実装自体は良さげだけど枝刈りができてなくてTLEそうだからpriority_queueとか色々使ってみる、AC。
提出したもの
int main() {
int n;
cin >> n;
int a[n + 1];
int b[n + 1];
int x[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> x[i];
}
// vec[i]はステージiに行くまでの最小移動時間
vector<ll> vec(n + 1);
for (int i = 2; i <= n; i++) {
vec[i] = LONG_LONG_MAX;
}
vec[1] = 0;
using P = pair<ll, int>;
priority_queue<P, vector<P>, greater<P>> queue;
queue.emplace(0, 1);
while (!queue.empty()) {
ll nowDistance = queue.top().first;
int now = queue.top().second;
queue.pop();
if (nowDistance > vec[now])
continue;
if (nowDistance + a[now] < vec[now + 1]) {
vec[now + 1] = nowDistance + a[now];
if (now + 1 != n) {
queue.emplace(vec[now + 1], now + 1);
}
}
if (nowDistance + b[now] < vec[x[now]]) {
vec[x[now]] = nowDistance + b[now];
if (x[now] != n) {
queue.emplace(vec[x[now]], x[now]);
}
}
}
cout << vec[n] << endl;
return 0;
}
振り返り
ダイクストラ自体を知らなかったのは反省だけど、発想自体は良かったと思う。
感想
勉強不足で反省だけど、知らない状態で方針自体は似てる解法を思いつけたのは偉い。もっと頑張る。