ABC105解説 - 柿食えば　屁をしても一人

まえがき

Unrated になって残念ですね（冷えてたので嬉しかったです）。
A, Bがコンテスト中AC、C, Dが解説ACです。
気合い入れて図とか使って解説するので、適宜追記していきます。
茶色以下でもわかるような解説を目指します。誤り、不明瞭な点があれば何らかの方法で連絡していただけると幸いです。

A問題

N人にK枚ある、せんべいを公平に分けます。

愚直な解放

「N個の配列を作ってK回ループを回して、最大値と最小値との差を求める。」が最も問題文に近い記述ではないかと思います。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,k;
	cin>>n>>k;
	vector<int> a(k);
	for(int i=0;i<n;i++){
		a[i%k]++;
	}
	//https://qiita.com/shirakawa4756/items/f4cc65c6b2b412b10c0c
	int min = *min_element(a.begin(), a.end());
	int max = *max_element(a.begin(), a.end());
	cout<<max-min<<endl;
	return 0;
}

よく考えると、全員に平等に割り切れる時(n%k==0)と、そうでない時に分けることができます。
割り切れない時、1枚ずつ分けてあげると半端な分をもらった人ともらってない人がいる事がわかります。
この時の差は、必ず1枚なので、0か1を出力してあげればよいです。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    if(a%b==0) cout<<"0"<<endl;
    else cout<<"1"<<endl;
    return 0;
}

所感

A問題の割には難しかった。

B問題

いわゆる鶴亀算の変形です。
$4\times x+7\times y = n$ となる $x,y$ の組み合わせが存在するかどうか見てあげればよいです（今気づきました）。
$n \leqq 100$ であることから $x,y$ を全探索しても $O(10^5)$ 程度なので余裕で間に合いますね。

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	for(int x=0;x<100;x++){
		for(int y=0;y<100;y++){
			if(4*x+7*y==n){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout<<"No"<<endl;
	return 0;
}

もちろん、 $y$ の方を右辺に持っていくことで $O(n^2)$ 探索から、 $O(n)$ に圧縮することができます。

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	for(int x=0;(x*4)<=n;x++){
			if((n-4*x)%7==0){
				cout<<"Yes"<<endl;
				return 0;
			}
	}
	cout<<"No"<<endl;
	return 0;
}

C++の負の剰余の計算はやばいという話を聞いたので、for文でif文の中で負の剰余の計算をしない様にします。

所感

なんかもっと複雑な問題と思っており、再帰で4を引くとき、7を引くときのすべての順番を試してました。
よく考えたら、ループ回すだけでよかったんですね。剰余の計算はちょっと怖いので計算量に余裕があるときは上の例がいいのかなと思いました。

C問題

(-2)の進数を実装する問題です。本番中はACできませんでした。
結論から言うと、愚直にn進数の実装をすればよかっただけというオチでした。
まず、10進数の $n$ に対応する (-2) 進数は次のように表現できます。
$a_m \times (-2)^{m} +a_{m-1} \times (-2)^{m-1} + \dots +a_1 \times (-2)^{1}+ a_0 \times (-2)^{0}$
$m=0$ の項に注目して考えます。 $a_0$ が1の時は1, 0の時は0になります。なので、どんな数にかかわらず、奇数の時は1, 偶数の時0になります。
$a_0$ が決まったので、上の式を変形します。

$a_m \times (-2)^{m} +a_{m-1} \times (-2)^{m-1} + \dots +a_1 \times (-2)^{1} =n- a_0 \times (-2)^{0}$
すべての項は2の倍数なので、両辺を (-2)で割ります。nが奇数の時は-1されてるので必ず偶数。
$a_m \times (-2)^{m-1} +a_{m-1} \times (-2)^{m-2} + \dots +a_1 \times (-2)^{0} =n'$
この時の $n'$ に注目して、上と同じように処理をします。
$a_m \times (-2)^{m-1} +a_{m-1} \times (-2)^{m-2} + \dots +a_2 \times (-2)^{1} =n' - a_1 \times (-2)^{0}$
これを両辺が0になるまで繰り返していくと (-2)進数が計算できます。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    stack < int > ans;
    while(n){
        ans.push(abs(n)%2);
        n-=ans.top();
        n=n/(-2);
    }
    if(ans.size()==0) cout<<0<<endl;
    else{
        while(!ans.empty()){
            cout<<ans.top();
            ans.pop();
        }
        cout<<endl;
    }
    return 0;
}

下のbitから出てくるので、stackに投げて逆順に計算しています。

所感

10進数n進数変換であまりを使ってやるのは知っていたんですが、どうしてそういう操作をしているのかよく知っていなかった気がするので良い問題でした。
わかってる人には秒だけど、付け焼き刃の人には難しいという問題だったのではないでしょうかね。

D問題

該当する区間を数え上げる問題です。これも解説ACです。
公式解説にあるように累積和のmodをmapに投げて、数え上げるだけです。公式が割と読みやすいのでそっちを読んでください。
mapを作るところまでは書いてあるのですが、どう数えるかが書いてなかったのでそれについて説明します。
サンプルにあるように、1点でmodがゼロになる点と、ある区間の和のmodがゼロになる点の2パターン許されていることに注意してください。
２点の決め方は、l, rが逆になってはいけないので、n*(n-1)/2で計算します。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    long long int num = 0;
    map<long long int, long long int> mp;
    rep(i, n)
    {
        int temp;
        cin >> temp;
        num += temp;
        if (mp[num % m] == 0)
        {
            mp[num % m] = 1;
        }
        else
        {
            mp[num % m] = mp[num % m] + 1;
        }
    }
    long long int ans=0;
    for(auto itr : mp){
        if(itr.first==0){
            ans+=itr.second;
        }
        if(itr.second>=2){
        ans+=itr.second*(itr.second-1)/2;
        }
    }
    cout<<ans<<endl;
    return 0;
}

特述すべき点は、特にないです。ルールがわかれば実装は簡単でした。

ABCの理解と日本語力の向上のために解説してみましたが、どうだったでしょうか。
別解法もあるよ！っていう方は是非教えてください。