ABC108解き直してみた

表題通りです。ABC108

それでは、

A問題

K以下の偶数の数 × K以下の奇数の数ですね。Kの偶奇で場合分けするといいでしょう。

A.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int k;
    cin >> k;
    if (k%2==0) {
        cout << (k/2)*(k/2) << "\n";
        return 0;
    }
    cout << ((k-1)/2)*((k+1)/2) << "\n";
    return 0;
}

B問題

真面目にやるんだったら、回転行列とか書くんでしょうが、簡単に下図を書けば、十分に一般的です。

B.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int a = x2 - x1;
    int b = y2 - y1;
    int x3 = x2 - b;
    int y3 = y2 + a;
    int x4 = x3 - a;
    int y4 = y3 - b;
    cout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4 << "\n";
    return 0;
}

C問題

「a+bがkで割り切れる」⇔「a%k+b%kがkで割り切れる」ですね。
式の対称性から、
「a%k = b%k = c%k = 0　or　a%k = b%k = c%k = k/2(ただしkが偶数)」
の時だけを拾えば良いです。

C.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    long n,k;
    cin >> n >> k;
    long mod_0 = 0, mod_half = 0;
    for (long i=1;i<=n;++i) {
        if (i%k==0) ++mod_0;
        if (k%2==0 && i%k==k/2) ++mod_half;
    }
    cout << mod_0*mod_0*mod_0 + mod_half*mod_half*mod_half << "\n";
    return 0;
}

なんか、longを使わないと、微妙に桁あふれするようなので、できる限りlongを使って行きましょう。

D問題

これは、コンテスト時にはわかりませんでした。終了後、解説を見たのですが、しばらく考えて、ようやくわかりました。

まず、ノードの数が、20以下なので、

$$
2^r < L
$$
となる最大の$r(<20)$を取ってきて、$r+1$個のノードを作りましょう。なぜ、$2^r$にするのかというと、2進数と関係があります。以下のように、辺を生やしましょう。

ノード$1$からノード$r+1$までのパスの長さは、$2^i$を選ぶか、$0$を選ぶかで、2進数で表現できます。よって、$0, 1, 2, 3, ...,2^r-1$までのパスが一本ずつ構成できます。

さて、ここでノード$i$からノード$r+1$へ長さ$X$の辺を張ったとしましょう。新しく辺を張ったことにより、この辺を通る$X, X+1, ..., X+(2^{i-1}-1)$のパスが一本ずつ新たにできました。この作業により、$2^r<=L$の時に、足りないパスを張って行きましょう。ノード$r$からノード$1$まで、順番に見ていって、もし、$2^r <= L$なら、今いるノード$i$から、$X = L - 2^{i-1}$の辺を張りましょう。これにより、$0, 1, ...,2^r-1$と$X,X+1, ...,L-1$のパスができます。足りないのは、$2^r, ...,X-1$のパスなので、$L$から$2^{i-1}$減らして($L$を$X$にして)次のノードに行きましょう。

D.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    long l;
    cin >> l;
    long r;
    for (r=1;r<=19;++r) {
        if (l < pow(2,r)) {
            break;
        }
    }
    --r;
    vector<vector<long>> ans;
    for (long i=1;i<=r;++i) {
        ans.push_back({i,i+1,0});
        ans.push_back({i,i+1,static_cast<long>(pow(2,i-1))});
    }
    for (long i=r;i>=1;--i) {
        if (l - pow(2,i-1) >= pow(2,r)) {
            ans.push_back({i,r+1,l-static_cast<long>(pow(2,i-1))});
            l -= pow(2,i-1);
        }
    }
    cout << r+1 << ' ' << ans.size() << "\n";
    for (auto each_ans : ans) {
        cout << each_ans[0] << ' ' << each_ans[1] << ' ' << each_ans[2] << "\n";
    }
    return 0;
}