初回 -> はじめに
ABC105を解きました。
4完です！
C問題は解説を見て解きました。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 2min | - | 8ms |
| B | 4min | - | 6ms |
| C | - | 余り | 5ms |
| D | - | 累積和 | 33ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
今回はC問題が難しくて解けなかったです。悔しい。
とても勉強になりました。
負の値を割るときは切り捨てではなく切り上げになるので、進数表現をするときは注意です。
D問題はZero-Sum Rangesという有名な問題に似ているので、その考え方を使いました。
std::mapは連想配列やhashmapと似た構造です。
keyとvalueがあって、keyを自由に設定できます。
内部的には平衡二分探索木で実装されています。
A - AtCoder Crackers
int n, k;
cin >> n >> k;
cout << (n % k > 0 ? 1 : 0);
均等に分けようとしたときの最大の差は1になりますね。
差が2あるときは、多く分けられた人が少ない人に1つ渡せば差がなくなります。
また、NがKで割り切れるときは差は0になります。
B - Cakes and Donuts
int n;
cin >> n;
for(int i = 0; n - i * 7 >= 0; ++i)
{
if ((n - i * 7) % 4 == 0)
{
cout << "Yes";
return;
}
}
cout << "No";
7の個数を変えながら、条件を満たす4の個数があるかを探索しました。
つるかめ算みたいに数学的に解けると思うのですが、思いつかなかったので愚直に。
C - Base -2 Number
int n;
cin >> n;
string ans = ((n == 0) ? "0" : "");
while(n != 0)
{
ans += (n % 2 == 0 ? '0' : '1');
n -= (n % 2 == 0 ? 0 : 1);
n /= -2;
}
reverse(ans.begin(), ans.end());
cout << ans;
難しかった。思い込みにやられました。
基本的な考え方は10進数をN進数に直すときと同じです。
つまり、Nで割りながら余りを記憶するという処理です。
私はN進数に直すときは割り算が切り捨てられることを利用してひたすらNで割り続けるのですが、今回はそれが使えません。
というのも、負の値を割ったときは切り捨てではなく切り上げになるためです。
例えば、-9を2で割ったときは切り捨てられて-5になってほしいのですが、プログラムでは-4になります。
これは当然といえば当然なのですが、この問題の場合はそれだと困ります。
これを防ぐためにはあまりを引く必要があります。
この部分ですね。
n -= (n % 2 == 0 ? 0 : 1);
こうすることで桁がそろい、想定通りの結果になります。
D - Candy Distribution
ll n, m;
cin >> n >> m;
vector<ll> a(n);
for(ll i = 0; i < n; ++i) cin >> a[i];
vector<ll> sum(a);
for(ll i = 1; i < n; ++i) sum[i] += sum[i - 1];
map<ll, ll> mp;
for(const auto& v : sum) mp[v % m]++;
ll ans = mp[0];
for(const auto& m : mp)
{
ll v = m.second;
ans += v * (v - 1) / 2;
}
cout << ans;
C問題に比べると簡単でした。(※個人差があります。)
Zero-Sum Rangesという有名な問題に似ているので、その考え方を使いました。
部分和がMの倍数になってほしいので、部分和を考えます。
部分和を求めるには累積和が使えますね。
ただ、部分和を求める解き方だと$O(N^2)$となり、今回は制約より時間内に解けません。
ここで知りたいのは部分和がMの倍数かどうかです。
累積和の差が部分和なので、累積和の差がMの倍数なことと部分和がMの倍数なことは同値です。
倍数なのでMODを考えます。
MODの世界では加算と減算が自由にできます。
つまり、累積和にMODを適用することと部分和にMODを適用することは同じですね。
この時、部分和がMの倍数ということはMODを適用した場合には部分和が0になります。
言い換えると、累積和の値が同じになるということだとわかります。
以上より、累積和にMODを適用したとき、値が同じ2数を選んで作る部分和はMの倍数なことがわかります。
あとはその組み合わせを数え上げれば答えがわかります。
ここまでわかれば実装です。
今回は累積和のMODが取りうる範囲がとても広いので、配列は使えません。
そのかわりにstd::mapを使いました。
std::mapは連想配列やhashmapと似たデータ構造ですね。
keyとvalueがあって、keyを自由に設定できます。
内部的には平衡二分探索木で実装されています。
以上です。ありがとうございました。