tqk's diary

競プロとか

ABC105 - tqkoh's diary

競プロ AtCoder ABC

超絶初心者緑コーダーのメモ#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の倍数になることがわかります。
その中から例えば上の例だと、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

ABC103 - tqkoh's diary

競プロ AtCoder ABC

自分(参加時茶色コーダー())の解いた方法を載せます。

A問題

A - Task Scheduling Problem
3つの整数を並べ、間の差の和を最小化する問題。意味が分かりにくい。

解法

3つの整数a, b, cを小さい順に並べたとき、d,e,fとなるとすると、答えは
(e-d)+(f-e)=f-d =max(a,b,c)-min(a,b,c)

int a,b,c; cin>>a>>b>>c;
cout << max({ a, b, c }) - min({ a, b, c });

B問題

B - String Rotation
ある文字列Sの一番後ろの文字を一番前に持っていく、という操作を繰り返して文字列Tにできるか判定する問題。

解法

これは、Sを2つつなげた文字列の中にTが含まれているかを検索するだけで判定できる。 (愚直に書いても通った。)

string s, t; cin >> s >> t; s += s;
cout << (s.find(t) != string::npos ? "Yes\n" : "No\n");

C問題

C - Modulo Summation
a_1,a_2,...,a_nが与えられるので、f(x)=(m\ mod\ a_1)+(m\ mod\ a_2)+...+(m\ mod\ a_n) の最大値を求めるという問題。

解法

n=3, a_1=3,a_2=4,a_3=6 のとき、括弧ごとに分けて考えると、
f:id:tako0608:20180723010231p:plain:w300
このように、いつかはどこかで全て0になるところ(例ではf(lcm(3,4,6))=f(12))があるので、そのひとつ前(例ではf(11))が最大値になる。よって答えは
(a_1-1)+(a_2-1)+...+(a_n-1) =(a_1+a_2+...+a_n)-n

int n, in, sum = 0; cin >> n;
rep(i, n) {
    cin >> in; sum += in;
}
cout << sum - n;

D問題

D - Islands War
n個の島が横1列に並んでいて、間にn-1本の橋があり、「a_i 番目とb_i 番目の島が行き来できないようにする」という要望をすべて叶えるために切らなければならない橋の最小値を求める問題。

解法

(ひどい解法です。)
a_i 番目とb_i 番目の島が行き来できないようにする、という要望をa_i からb_i までの線分で表すと、たとえば次のようになる。
f:id:tako0608:20180723022524p:plain
これをすべて切る縦線が求まればいいのだが、この状態だとどこを切ればいいかわからないので、（(a_i,b_i)をa_iについてソートしてあるものを）a_iが同じもののうちでb_iについて降順でソートする。
f:id:tako0608:20180723020246p:plain
こうすることで、上から見ていき、右端が(次の要望の左端)以下の要望(次の図で赤い要望)さえ切ればそれより上はすべて切れることになる。
f:id:tako0608:20180723020822p:plain
よって、(1)左端昇順でソート(2)それごとに右端降順でソート(3)右端が(次の要望の左端)以下の要望の数を数え、それ+1(最後)が答えとなる。
(クソコードは以下にありますが見ないでください。本番中にきれいなコードが書けたことはありません)

Submission #2886100 - AtCoder Beginner Contest 103

学んだことメモ

  • sort()の仕組みが少しわかった。第三引数にどうやってソートするかを示した関数を渡すことで、pairのfirstを比較して並び替える、などができる。（比較関数、という。。。？）例: pair<int, int>の、secondを降順に並べるそれ
bool secgreater(const pair<int, int>& a, const pair<int, int>& b) return a.second > b.second;
  • つかうときは以下のようにする
sort(a, a+n, secgreater);
  • 標準の、intとかの降順ソートの比較関数？は()をつけるようだ
sort(b, b+n, greater<int>());

リンク

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

qiita.com

tqk.hatenablog.jp

ABC103 - tqkoh's diary

競プロ AtCoder ABC

自分(参加時茶色コーダー())の解いた方法を載せます。

A問題

A - Task Scheduling Problem
3つの整数を並べ、間の差の和を最小化する問題。意味が分かりにくい。

解法

3つの整数a, b, cを小さい順に並べたとき、d,e,fとなるとすると、答えは
(e-d)+(f-e)=f-d =max(a,b,c)-min(a,b,c)

int a,b,c; cin>>a>>b>>c;
cout << max({ a, b, c }) - min({ a, b, c });

B問題

B - String Rotation
ある文字列Sの一番後ろの文字を一番前に持っていく、という操作を繰り返して文字列Tにできるか判定する問題。

解法

これは、Sを2つつなげた文字列の中にTが含まれているかを検索するだけで判定できる。 (愚直に書いても通った。)

string s, t; cin >> s >> t; s += s;
cout << (s.find(t) != string::npos ? "Yes\n" : "No\n");

C問題

C - Modulo Summation
a_1,a_2,...,a_nが与えられるので、f(x)=(m\ mod\ a_1)+(m\ mod\ a_2)+...+(m\ mod\ a_n) の最大値を求めるという問題。

解法

n=3, a_1=3,a_2=4,a_3=6 のとき、括弧ごとに分けて考えると、
f:id:tako0608:20180723010231p:plain:w300
このように、いつかはどこかで全て0になるところ(例ではf(lcm(3,4,6))=f(12))があるので、そのひとつ前(例ではf(11))が最大値になる。よって答えは
(a_1-1)+(a_2-1)+...+(a_n-1) =(a_1+a_2+...+a_n)-n

int n, in, sum = 0; cin >> n;
rep(i, n) {
    cin >> in; sum += in;
}
cout << sum - n;

D問題

D - Islands War
n個の島が横1列に並んでいて、間にn-1本の橋があり、「a_i 番目とb_i 番目の島が行き来できないようにする」という要望をすべて叶えるために切らなければならない橋の最小値を求める問題。

解法

(ひどい解法です。)
a_i 番目とb_i 番目の島が行き来できないようにする、という要望をa_i からb_i までの線分で表すと、たとえば次のようになる。
f:id:tako0608:20180723022524p:plain
これをすべて切る縦線が求まればいいのだが、この状態だとどこを切ればいいかわからないので、（(a_i,b_i)をa_iについてソートしてあるものを）a_iが同じもののうちでb_iについて降順でソートする。
f:id:tako0608:20180723020246p:plain
こうすることで、上から見ていき、右端が(次の要望の左端)以下の要望(次の図で赤い要望)さえ切ればそれより上はすべて切れることになる。
f:id:tako0608:20180723020822p:plain
よって、(1)左端昇順でソート(2)それごとに右端降順でソート(3)右端が(次の要望の左端)以下の要望の数を数え、それ+1(最後)が答えとなる。
(クソコードは以下にありますが見ないでください。本番中にきれいなコードが書けたことはありません)

Submission #2886100 - AtCoder Beginner Contest 103

学んだことメモ

  • sort()の仕組みが少しわかった。第三引数にどうやってソートするかを示した関数を渡すことで、pairのfirstを比較して並び替える、などができる。（比較関数、という。。。？）例: pair<int, int>の、secondを降順に並べるそれ
bool secgreater(const pair<int, int>& a, const pair<int, int>& b) return a.second > b.second;
  • つかうときは以下のようにする
sort(a, a+n, secgreater);
  • 標準の、intとかの降順ソートの比較関数？は()をつけるようだ
sort(b, b+n, greater<int>());

リンク

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

qiita.com

tqk.hatenablog.jp