ABC081 「C - Not so Diverse」
考察と解法
- 個数の少ない種類のボールを取り除く方法が得する。
- 取り除く種類数は$max(0, 入力の種類数-K)$個となる。
コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
map<int, int> mp;
while (N--) {
int a;
cin >> a;
mp[a]++;
}
vector<int> v;
for (auto x : mp) {
v.push_back(x.second);
}
sort(v.begin(), v.end());
int cnt = max(0, (int)mp.size()-K); // 種類の個数
cout << accumulate(v.begin(), v.begin()+cnt, 0) << endl;
return 0;
}
accumulate関数
- 上位陣はこの関数使ってたので僕も使ってみた。
-
accumulate(最初のイテレータ, 最後のイテレータ, 初期値)といった使い方をするとその範囲の値の和を返してくれる。count()と同じような使い方 - 和だけでなく、積とかも計算できたりする
- 初期値の型には気を付ける。オーバーフローとか、浮動小数点数とか。今回も
0LLとかで初期化した方が安全だったかもしれない - 公式リファレンス以外にこのブログが分かりやすかった。
感想
- 適当な実装してWA出してしまった
-
accumulate関数、便利だな...コーディング量が減って楽できる。
ABC082 「Good Sequence 」
考察と解法
- 数aがb個あるとする。
- $a<b$なら$b-a$個取り除く必要がある
- $a>b$ならb個すべてを取り除く必要がある
コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N;
cin >> N;
map<ll, ll> mp;
while (N--) {
ll a;
cin >> a;
mp[a]++;
}
ll ans = 0;
for (auto x : mp) {
if (x.first <= x.second) {
ans += x.second - x.first;
} else {
ans += x.second;
}
}
cout << ans << endl;
return 0;
}
感想
- 4が2個あるとき、どう頑張っても4を4個にできない。なので、2個取り除いて4を消し去るという発想を出すのが遅れた。
ABC083 「Multiple Gift 」
考察と解法
- $A_i < A_{i+1}$かつ$A_{i+1} = nA_{i}$になるようにする。数列を長くするためには$A_{i+1}$ができるだけ小さくなるようにしたい。$n=2$のときがこの条件を満たす最小の値となる。よって、毎回2倍していくのが最適解となる。
コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll X, Y;
cin >> X >> Y;
ll ans = 0;
while (X <= Y) {
ans++;
X*=2;
}
cout << ans << endl;
return 0;
}
- 僕はこんなコードを書いちゃったわけだがwhileで書いた方が楽そう
ABC084 「Special Trains 」
考察と解法
- 問題文を要約すると、上の図のように各駅から目的地までの最短時間を求めたい。
- 全体像が分かったところで、部分的なところを考える。
- 駅$j$→$j+1$の最短移動時間が分かればよさそう。
- 駅$j$→$j+1$の移動時間は「駅$j$を出発する時刻 + 駅$j+1$へ移動する時間」となる。
- 駅$j$を出発する時刻は、$S[j]+F[j] \times k$となる($k$は適当な整数)。出発する時刻は現在時刻$t$以上である必要があるので、$S[j]+F[j] \times k \geq t$とする。$k$が何になるかを求めたいので、$k \geq \frac{t-S[j]}{F[j]}$という式に変形する。$k$は右辺を切り上げた数値となるので、$k=\frac{(t-S[j]+F[j]-1)}{F[j]}$となる。$k$はマイナスの値になる場合もあるので、その時は$k=0$にする。
- 駅$j+1$へ移動する時間は$C[j]$である
- 以上から、駅$j→j+1$の移動時間は$S[j]+F[j]\times k + C[j]$で、$k=max(0,\frac{(t-S[j]+F[j]-1)}{F[j]})$となる。
コード
#include <bits/stdc++.h>
using namespace std;
int N;
int C[555], S[555], F[555];
int main() {
cin >> N;
for (int i = 0; i < N-1; i++) {
cin >> C[i] >> S[i] >> F[i];
}
for (int i = 0; i < N; i++) { // 駅iを始点とする
int t = 0; // 現在時刻
for (int j = i; j < N-1; j++) {
// 駅jから駅j+1までにかかる時間を計算
int k = max(0, (t - S[j] + F[j] - 1) / F[j]);
t = S[j] + F[j]*k + C[j];
}
cout << t << endl;
}
return 0;
}
- 一応$k$をループで求めてもACできる。コード
- $k$を求める計算量がどれだけになるかはよくわかんないけど、数学を使えばループ処理を$O(1)$にできるってすごい不思議。なんで$O(1)$になったの！？！？！？って感じがする。数学しゅごい...
感想
- この問題、問題文を読み取るのがまず難しい。コンテスト中(バチャじゃない)は問題文を何回も読み直した記憶。結局解けなかったんだけど。
- 問題文から式を作るっていう発想と式を変形して求めたい数値を計算するという発想が必要だった。この発想コンテスト中になかなか思いつかない...
- この問題は「駅$j$→$j+1$の移動時間」が何になるかを求めればOKということが分かればコンテスト中に解けたのかも。何を重点的に考えるか？本質を見極めたい。
- 解説見てもわからなかった問題がわかったのでまあ良しとしよう...
ABC085 「Otoshidama 」
考察と解法
- 10000円札をa枚、5000円札をb枚、1000円札をc枚とすると以下の2つの式が作れる
- $a+b+c=N$
- $10000a+5000b+1000c=Y$
- a, b, cを全探索すれば答えが求まるが、TLEになってしまう。そこで、式変形して$c=N-a-b$にすることで計算量を1つ落とす
コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N, Y;
cin >> N >> Y;
for (int a = 0; a <= 2000; a++) {
for (int b = 0; b <= 2000; b++) {
int c = N - a - b;
int sum = 10000*a + 5000*b + 1000*c;
if (c >= 0 && c <= N && sum == Y) {
printf("%d %d %d\n", a, b, c)
return 0;
}
}
}
printf("%d %d %d\n", -1, -1, -1);
return 0;
}