気持ち

たぷなので別解集を書いて精進したつもりになります
ネタバレもあります

別解集ということは想定解をわかっていないといけないですけどそのあたりは目をつぶってください

本質的に異なる解もあればちょっとした実装の差しかない解もあります適当に流し読みして見たいところだけ見てください

さらなる別解を持っている人は教えてくださいたぴ

本編

A

$K$ 人に $N$ 個のクッキーをなるべく公平に配ります一番もらえる人と一番もらえない人の差はいくつでしょう？

全探索

トランプを配るみたいに一枚ずつ配るのが最適なのは経験的にわかると思います
$N,K\leq100$ なのでそれをシミュレーションればいいですね
一枚ずつ配っていって最後の人にきたら最初に戻ればいいです
一番もらえる人は最初の人、一番もらえない人は最後の人なのでその二人の差を計算しましょう

#include<bits/stdc++.h>

int N, K, senbey[111];

int main(){
    using namespace std;
    cin >> N >> K;
    
    for(int i = 0, j = 0; i < N; ++i){ // N 枚のせんべいを配る
        senbey[j]++; // 配る
        ++j;
        if(j >= K)j = 0; // 最後の人になったら最初に戻る
    }
    
    cout << senbey[0] - senbey[K - 1] << endl; // 最初の人と最後の人の差が答え
}

数学的考察

よく考えると、この方法では答えが1か0にしかならないことがわかります。
1になるのは $N$ が $K$ の倍数でないときで、0になるのは $N$ が $K$ の倍数のときです。
これを実装するとより楽かつ高速な実装になります。

#include<bits/stdc++.h>

int N, K;

int main(){
    using namespace std;
    cin >> N >> K;
    if(N % K == 0)cout << 0 << endl; // N が K の倍数のとき
    else cout << 1 << endl; // そうでないとき
    return 0;
}

実装ちょいテク

$N\%K$ が0のとき0を、非0のとき1を出力したいので、こういう時に使えるちょいテクがあります。
論理否定演算子!は変数が0のとき1を、非0のとき0を返してくれるのでこれを2つ並べると0のとき0を、非0のとき1を返すようにできます。

#include<bits/stdc++.h>

int N, K;

int main(){
    using namespace std;
    cin >> N >> K;
    cout << !!(N % K) << endl;
    return 0;
}

あるいはboolに変換すればいいのでstatic_cast<bool>などを使ったり、三項演算子などを使ってもいいです

B

$N$ が与えられるので、 $N=4x+7y$ をみたす非負整数の組 $(x,y)$ が存在するかを判定します

全探索

$N\leq100$ なので、 $x\leq25, y\leq14$ です。あとは(非負なので)この範囲の $(x,y)$ を全探索するといいです。

#include<bits/stdc++.h>

int N;

int main(){
    using namespace std;
    cin >> N;
    for(int x = 0; x < 26; ++x){ // x を全探索
        for(int y = 0; y < 15; ++y){ // y を全探索
            if(N == 4 * x + 7 * y){ // もしうまくいったら
                puts("Yes"); // Yesを出力して
                return 0; // 終了
            }
        }
    }
    puts("No"); // うまくいかなかったのでNo
    return 0;
}

前計算 : constexpr

ところで、答えがYesであるような $N$ は入力によって変わるでしょうか？
これはいいえなので、事前にそのような $N$ を計算しておいて、その判定結果を使ってすぐに答えを出すことができます

#include<bits/stdc++.h>

int N, ans[101];

int main(){
    using namespace std;
    for(int x = 0; x < 26; ++x){
        for(int y = 0; y < 15; ++y){
            if(4 * x + 7 * y <= 100) // 100を超えなかったら
                ans[4 * x + 7 * y] = 1;
        }
    }
    cin >> N;
    puts(ans[N] ? "Yes" : "No");
    return 0;
}

ところでC++にはconstexprというコンパイル時計算機能があるのでそれを使うと以下のようにできます。

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

template<typename Integer, size_t maxN, Integer a = 4, Integer b = 7>
class Ans{
    Integer val[maxN];
public:
    constexpr Ans() : val(){
        for(size_t i = 0; i < maxN; ++i){
            for(size_t j = 0; j < maxN; ++j){
                if(i * a + j * b < maxN)val[i * a + j * b] = 1;
            }
        }
    }
    constexpr Integer operator[](size_t i) const {return val[i];}
};

constexpr auto ans = Ans<uint_fast64_t, 200>();
long long int N;

int main(){
    scanf("%lld", &N);
    puts(ans[N] ? "Yes" : "No");
    return 0;
}

数学的考察

$N$ を4で割ったあまりに注目してみると、 $N+y$ が4の倍数でなくてはならないことがわかります。
また、 $y$ を4減らして $x$ を7増やすことは $y>0$ である限り答えに影響しないので $y$ の値を探索なしでもとめることができました
あとは $N-7y$ が非負であるかを判定すればいいだけです。

以下のコードでは-Nがいい感じになっていることを仮定してい(て、AtCoderではうまく動き)ますが、処理系依存なはずです

#include<bits/stdc++.h>

int N;

int main(){
    using namespace std;
    cin >> N;
    puts(N >= 7 * (-N & 3) ? "Yes" : "No");
    return 0;
}

数学的考察 #2

実験をするなどしてみると、ある程度大きくなるとほとんどの $N$ でYesになるような気がしてきます。
また、上のコードでもわかるように、-N & 3は3以下なので、21以上の $N$ については必ず答えがYesになります。
なので、21未満のところを最初に探索しておいて、その答えを埋め込んでよしなにするといいです。(Noになるのは $N=1,2,3,5,6,9,10,13,17$ のところです)

#include<bits/stdc++.h>

int N;

int main(){
    using namespace std;
    cin >> N;
    puts((140910 >> N) & 1 ? "No" : "Yes");
    return 0;
}

C

整数 $N$ を負二進数(negabinary)に直してください。

想定解法

下の位から決めていきます。
一番下以外の桁は1でも0でも偶数ぶんしか変わらないので、1桁目は奇数なら1で、偶数なら0です。
それを $N$ から引くと $N$ の負二進法展開の下1桁だけ0にしたものが得られます。
これを $N=0$ となるまで繰り返すと各桁の値がわかります。

注意点が2つあって、これは下から桁を求めているので、上下反転するような措置をどこかで取る必要があるのと、初めから0のときに何も出力されないので注意しましょう

先頭に追加

一番素直ですが、実は計算時間が長くかかってしまう場合があります(今回の場合桁数が多くならないので大丈夫です)

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

int N;
string s;

int main(){
    cin >> N;
    if(!N)puts("0");
    while(N){
        s = (N & 1 ? "1" : "0") + s;
        N -= N & 1;
        N /= -2;
    }
    cout << s << endl;
    return 0;
}

文字列反転

比較的素直で、これは $O(\log N)$ で高速です

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

int N;
string s;

int main(){
    cin >> N;
    if(!N)puts("0");
    while(N){
        s.push_back((N & 1) + '0');
        N -= N & 1;
        N /= -2;
    }
    reverse(s.begin(), s.end());
    cout << s << endl;
    return 0;
}

再帰関数

一番技巧的ですが、文字列を変数として持つ必要がないなどの利点もあります

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

int N;

void negabin(int N){
    if(!N)return;
    negabin(-(N - (N & 1)) / 2);
    putchar(48 + (N & 1));
}

int main(){
    cin >> N;
    if(!N)puts("0");
    else{
        negabin(N);
        puts("");
    }
    return 0;
}

上の桁から決める

$i$ 桁以内で表現できる範囲を計算することを考えます。
$i-1$ 桁以内で $[l, r$ ] を表現できるとき、 $i$ 桁では $[l,r$ \cup [l+(-2)ⁱ,r+(-2ⁱ)]] の範囲が表現できます。
証明は省略しますが、 $[l,r$ ] と [tex:[l+(-2)ⁱ,r+(-2ⁱ)]] は共通部分はなく、ちょうど整数の連続な範囲になります。
なので、これを下から40個くらい計算しておいてその範囲を外れるたびその上の桁を1にしておくといいです。

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

int N;
vector<pair<long long, long long>> range;

inline long long digit(int i){ // i 桁目を求める これを作っておくと楽です
    return (1LL << i) * (i & 1 ? -1 : 1);
}

int main(){
    range.emplace_back(0, 1);
    for(int i = 1; i < 40; ++i){ // i 桁以下で表現できる範囲を計算します
        range.emplace_back(range.rbegin()->first + (i & 1 ? digit(i) : 0), range.rbegin()->second + (i & 1 ? 0 : digit(i)));
    }
    cin >> N;
    bool f = false; // 上の桁がずっと0ならfalse
    for(int i = 39; i >= 0; --i){
        if(range[i].first > N || range[i].second < N){
            putchar('1');
            f = true;
            N -= digit(i + 1);
        }else if(f){
            putchar('0'); // 上に何かあるので0を出力する
        }
    }
    cout << N << endl; // 一番下の桁
    return 0;
}

ところで、 $i$ 桁で表現できる範囲の上限と下限は二進法で表すと綺麗な形になっているので、いい感じの式で $O(1)$ で計算することができます。省略するので、みなさんで考えて見てください。

数学的考察

2進数で2桁ごとに区切って考えてみると、00 $\mapsto$ 00, 01 $\mapsto$ 01,10 $\mapsto$ 110,11 $\mapsto$ 111なので、下から見ていって、偶数桁目が立っていればその上の桁に1を足すをするといいことがわかります。
さらに考えると、偶数桁目のbitに全て1を足して、そのあと偶数桁目のbitを全て反転することで上の操作が一気に行えることがわかります。

eiyaさんがツイートしていた解法も整理するとこれになります

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

long long N, x = 733007751850;

int bin(long long d){
    if(d){
        bin(d >> 1);
        return printf("%lld", d & 1);
    }
}

int main(){
    cin >> N;
    N ? bin((N + x) ^ x) : puts("0");
}

D

基本的に解説の考え方と同じ方針での解法しか無いように思います...

連想配列(ハッシュマップ)

この方針だと配列を取る必要はありません(連想配列を取る必要はありますが)

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

long long int N, M, a, S, ans;
unordered_map<long long, long long> m;

int main(){
    cin >> N >> M;
    m[0] = 1;
    for(int i = 1; i <= N; ++i){
        cin >> a;
        S += a;
        S %= M;
        ans += m[S]++;
    }
    cout << ans << endl;
    return 0;
}

ソートしてえい

連想配列が思い浮かばなくてもソートしてえいをすると通ります
ソートすると同じ数は隣り合っているので、隣の数が自分と違ったら自分がはじめてこの数字になったところであることがわかります。

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

long long N, M, a[101010], ans;

int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; ++i){
        cin >> a[i];
        a[i] += a[i - 1];
        a[i] %= M;
    }
    sort(a, a + N + 1);
    for(int i = 1, j = 1; i <= N; ++i){
        if(a[i] != a[i - 1])j = 0;
        ans += j++;
    }
    cout << ans << endl;
    return 0;
}

競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

AtCoder Beginner Contest 105 別解集

気持ち

本編

A

全探索

数学的考察

実装ちょいテク

B

全探索

前計算 : constexpr

数学的考察

数学的考察 #2

C

想定解法

先頭に追加

文字列反転

再帰関数

上の桁から決める

数学的考察

D

連想配列(ハッシュマップ)

ソートしてえい