超絶初心者緑コーダーのメモ#2です

A問題

A - AtCoder Crackers
n個の物をk人に均等に分けたとき、一番多く持っている人と一番少ししかもっていない人の差を求める問題です。

解法

答えは0もしくは1になります。2以上差があると、多く持っている人から少ししかもっていない人に渡せばもっと均等になるからです。また、差が0となるのはnがkでちょうど割り切れるときだけなので、それを判定するだけでいいです。

#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
int main() {
    int n, k; cin >> n >> k;
    cout << (n%k ? "1\n" : "0\n");
}

B問題

B - Cakes and Donuts
4ドルの物と7ドルのものをいくつか買って合計金額がnドルになるものを求める問題です。

解法

全探索すればいいです。(4ドルのものの個数) <= n/4, (7ドルのものの個数) <= n/7 ですが、制約が n <= 100なので普通に25*25とかもう100*100とか全探索しちゃってもいいです。

#include "bits/stdc++.h"
using namespace std;
int main() {
    int n; cin >> n;
    bool f = 0;
    for (int i = 0; i <= n / 4; ++i)for (int j = 0; j <= n / 7; ++j) {
        if (4 * i + 7 * j == n) { f = 1; break; }
    }
    cout << (f ? "Yes\n" : "No\n");
}

C問題

C - Base -2 Number
nの(-2)進数表記を求める問題です。

解法

このように、手計算と同じことをするプログラムを書けばよいです。
-2) -9
-2) 5 　... 1
-2) -2 　... 1
　　1　... 0

#include "bits/stdc++.h"
using namespace std;
int main() {
    long long n; cin >> n;
    string s;
    while (n) {
        if (n % 2)s = '1' + s;
        else s = '0' + s;
        n = ceil((double)n / (double)-2);
    }
    if (s == "")s = "0";
    cout << s << endl;
}

今回は-2進数だったので、割り切れなければ'1'にする、で大丈夫でしたが、-3進数になったりすると、c++の「余りの定義が正負で異なる」という仕様が邪魔をしてくるようになります。どういうことかというと、-5%3が、1とならなければいけないところ-2となります。(pythonなどの言語だとちゃんと1となります。) ただ+3すればいいだけなので問題ないですが。

D問題

D - Candy Distribution
$A_1, A_2, ..., A_n$ の連続した区間の和のうち、mの倍数であるものを数えるという問題です。 $O(N^2)$ から速くできなくて終わりました...

解法

累積和をそれぞれ%m しても変わらないので、問題文の通りに、累積和を求めて、
$A_{i+1}+A_{i+2}+...+A_j = (mの倍数)$ 、すなわち
$S_j\% m - S_i\% m=0 (0\leq i\leq N, i\leq j\leq N)$
を探索すると $O(N^2)$ で、 $N\leq 10^5$ なのでTLEです。 f:id:tako0608:20180812131801p:plain
しかし、実は上の式 $S_j\% m - S_i\% m=0$ を変形すると $S_j\% m = S_i\% m$ となり、
表の $i, j$ 番目の一番下の値が同じ数の区間は、その間の和が $m$ の倍数になることがわかります。(数学をやっている人からしたらこの式が気持ち悪くて最後にmodつけろ、と言いたくなるかもしれませんがプログラムのためなので許して)
その中から例えば上の例だと、0が3個ありますからその中から $i, j$ の2つを選ぶので選び方は ${}_3C_2=3$
通りあることがわかります。同様に1が1個ありますからその中から2つを選ぶ選び方は0通りです。これを足して3が答えです。
実装ですが、表の一番下の値が(0なのは3個), (1: 0個), ...,(k: $B_k$ ) ,..., (m-1: $B_{m-1}$ )という風に値ごとに保存しておいて、最後に
$\displaystyle \sum_{k=0}^{m-1} {}_{B_k}C _2= \sum_{k=0}^{m-1} \cfrac{B_k(B_k-1)}{2}$ を計算すれば答えが出ます。
まずこの考えが思いつかなかったのですが（弱い）、この考えを聞いても「制約が $m\leq 10^9$ なんだから配列が(最大m要素もあって)大きすぎて値ごとに保存するなんて無理じゃないか！」と思いどう実装すればいいかわかりませんでした。これは、「 $N\leq10^5$ なので埋まらない無駄な要素がある」ことを利用して、unordered_mapというデータ構造を使うとできます。これを知らなかったので方法を思いついても解けませんでした。。。

#include "bits/stdc++.h"
using namespace std;
int main() {
    long long n, m, in, s = 0, ans = 0; cin >> n >> m;
    unordered_map<long long, long long> h;
    ++h[0];
    for (int i = 0; i < n; ++i) {
        cin >> in;
        s = (s + in) % m;
        ++h[s];
    }
    for (auto i : h) {
        ans += i.second*(i.second - 1) / 2;
    }
    cout << ans << endl;
}

学んだことメモ

std::unordered_map: a[キー]に値を保存できる配列みたいなやつ。配列だと使うところが少なくて無駄ができるときに有効。要素はpair<const _KTy, _Ty>型になっているので、(要素).firstでキーに、(要素).secondで値にアクセスできる。
ex.

unordered_map<long long, long long> ma;
for (auto i : ma) {//iはmaの要素を遷移する
        ans += i.second*(i.second - 1) / 2;
}

リンク

他にもこんな記事を書いています

qiita.com

tqk.hatenablog.jp

tqk's diary

競プロとか

ABC105 - tqkoh's diary

A問題

解法

B問題

解法

C問題

解法

D問題

解法

学んだことメモ

リンク