TechFUL: マスクを買いたい[easy]

問題概要

Tech ちゃんは 24 時間営業の店に行く．

時刻 から時刻 直前まで、お客さんが多いことが分かっている．

Tech ちゃんはお客さんが少ない時間を狙って買い物にいく．

Tech ちゃんが買い物に向かうべき時間を出力せよ．

制約

• 

• Tech ちゃんは必ず買い物に行く．

解法

となる時間 に行かないようにする．

但し、例外として の場合があり、全ての時間に行くことができる．

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

int main() {
    int S, T;
    cin >> S >> T;
    if (S == 0 && T == 24) {
        for (int i = 0; i < 24; ++i) {
            cout << i << " ";
        }
        cout << endl;
    } else {
        for (int i = 0; i < 24; ++i) {
            if (S <= i && i < T) continue;
            cout << i << " ";
        }
        cout << endl;
    }
}

TechFUL: Polygon Cutting

問題概要

正 角形の紙が 1 枚ある．

Tech ちゃんは以下の操作によって紙をいくつかの多角形に切り分ける．

• 多角形 の任意の対角線に沿って紙を切り、2 つの多角形 に切り分ける．

この操作を繰り返したとき、最大で何個の多角形に切り分けることが出来るか求めよ．

制約

• 

解法

操作の回数の最大値は 1 つの頂点から引ける対角線の本数と等しく 回である．

1 回の操作で多角形は 1 つ増えるので、最終的な多角形の個数は 個である．

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

int main() {
    int N;
    cin >> N;
    cout << N - 2 << endl;
}

TechFUL: エレベーター

問題概要

Tech ちゃんが乗るエレベーターは 1 階上がることに、 秒間かかる．

Tech ちゃんがエレベーターに乗り、 秒間経ったときのエレベーターの現在の階数を求めよ．

但し、Tech ちゃんはエレベーターを 1 階から乗り、エレベーターの階に上限はない．

制約

• 

• 

解法

階数は である．

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

int main() {
    int N, S;
    cin >> N >> S;
    cout << S / N + 1 << endl;
}

TechFUL: Improving Binary

問題概要

バイナリ文字列 が与えられる．

文字列の良さとは、1 が連続して並んでいる区間の長さの最大値である．

以下の操作を 回まで行える．

• の文字が 0 である箇所を 1 つ選び、1 に変える．

適切に操作したときの文字列の良さの最大値を求めよ．

問題のリンク

制約

• は 0 または 1 からなる文字列

• 

• 

解法1: 二分探索

について、位置 を始点に右に 1 ができるだけ長く連なるように操作を行う．

最初に文字 0 が現れる位置を とする．

このとき、 が答えである．

例として、S = 001001011, K = 2 の場合をみると

• 位置 0 を始点とした場合、S = 001001011 の位置 0, 1 の 0 を 1 に変えれば、
  S = 111001011 となり、 となる．

• 位置 1 を始点とした場合、S = 001001011 の位置 1, 3 の 0 を 1 に変えれば、
  S = 011101011 となり、 となる．

• 位置 2 を始点とした場合、S = 001001011 の位置 3, 4 の 0 を 1 に変えれば、
  S = 001111011 となり、 となる．

次に の計算であるが、 これは に文字 0 がいくつ存在するか数える配列 を事前に計算しておけば、 二分探索を使用して 時間でできる．

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

string S;
int K;
int cnt[100010];

int main() {
    cin >> S >> K;

    for (int i = 0; i < S.size(); ++i) {
        cnt[i + 1] = cnt[i] + (S[i] == '0');
    }

    int ans = 0;
    for (int i = 0; i < S.size(); ++i) {
        int ok = i, ng = S.size() + 1;
        while (ng - ok > 1) {
            int m = (ok + ng) / 2;
            if (cnt[m] - cnt[i] <= K) ok = m;
            else ng = m;
        }
        ans = max(ans, ok - i);
    }
    cout << ans << endl;
}

解法2: しゃくとり法

上の の値は において が成り立つ．

そのため、 はしゃくとり法を使って全体で 時間で計算できる．

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

string S;
int K;
int cnt[100010];

int main() {
    cin >> S >> K;

    for (int i = 0; i < S.size(); ++i) {
        cnt[i + 1] = cnt[i] + (S[i] == '0');
    }

    int ans = 0, j = 0;
    for (int i = 0; i < S.size(); ++i) {
        while (j <= S.size() && cnt[j] - cnt[i] <= K) {
            j++;
        }
        ans = max(ans, j - 1 - i);
    }
    cout << ans << endl;
}

TechFUL: Xor Rush

ABC147 の Xor Sum 4 と実質同じ問題．

問題概要

長さ の整数列 と長さ の整数列 が与えられる．

を求めよ．

問題のリンク

制約

• 

• 

解法

XOR 系の問題なので を2進数表示して、各桁ごとに考えてみる．

まず、 を2進数表示すると何桁になるか調べる．

これは、制約から より

となり、高々20桁と分かる．

次に、式 (1) を2進数表示を意識して式変形する．

ただし、 を ビット目が である の要素の個数とする．

同様に も定義する．

以上より、 を計算すれば、式 (2) を基に答えを得る．

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];

    long long cntA[20][2] = {}, cntB[20][2] = {};
    for (int d = 0; d < 20; ++d) {
        for (int i = 0; i < N; ++i) {
            cntA[d][A[i] >> d & 1]++;
        }
        for (int i = 0; i < M; ++i) {
            cntB[d][B[i] >> d & 1]++;
        }
    }

    long long ans = 0;
    for (int d = 0; d < 20; ++d) {
        ans += (1LL << d) * (cntA[d][0] * cntB[d][1] + cntA[d][1] * cntB[d][0]);
    }
    cout << ans << endl;
}

TechFUL: Techちゃんとバウムクーヘン泥棒【easy】

問題概要

Techちゃんは好みの男の子にバウムクーヘンを作りたい．

Techちゃんは 個入りのバウムクーヘンを好きな個数だけ自由に作る．

しかし、バウムクーヘンの個数が 個以上のとき、 個未満になるまでカラスの集団が 個ずつ食べてしまう．

男の子は 個のバウムクーヘンを貰うと Tech ちゃんを好きになる．

男の子が Tech ちゃんを好きにさせることが可能か判定せよ．

問題のリンク

制約

• 
• 

解法

Tech ちゃんが 個のバウムクーヘンを作り、

カラスが 個バウムクーヘンを食べたとする．

このとき、 が成り立つ．

これを式変形すると、 という一次不定方程式になる．

この方程式が整数解を持つための必要十分条件は r が gcd(x, m) の倍数を満たすことである．

一次不定方程式については以下の drken さんの記事が参考になる．

qiita.com

この方程式の整数解がどちらも 0 以上になるかを考える．

を を満たす整数解の一つとする．

また、 を となる整数とすると、 より は同符号である．

となるため、 も一次不定方程式の整数解となる．

を十分大きな値にすれば、 はどちらも 以上の整数にすることができる．

よって、 には 以上の整数解 が存在する．

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

int main() {
    long long x, m, r;
    cin >> x >> m >> r;
    cout << (r % gcd(x, m) == 0 ? "Yes" : "No") << endl;
}

TechFUL: スーパー転倒数

問題概要

長さ の順列 が与えられる．

次の 2 つの条件を満たす の組の個数を求めよ．

• 
• 

問題のリンク

制約

• 
• 
• は長さ の順列

解法

数列の転倒数は、その数列をマージソートする過程で計算する．

そのため、スーパー転倒数も数列をマージソートする過程で計算できないか考えてみる．

マージソートの実装や性質については drken さんの記事が参考になる．

qiita.com

スーパー転倒数の計算

をそれぞれ2つの数列 に分割する．

数列 のスーパー転倒数には次の3種類のスーパー転倒が起こる．

• の要素のみで起こるスーパー転倒

• の要素のみで起こるスーパー転倒

• と の要素間で起こるスーパー転倒

1つ目ケースは、 を再び分割して再帰的に計算することができる (2つ目のケースも同様)．

3つ目のケースを考える． それぞれをソートした数列を とする． また、 を の順に対応するように並び替えた数列を とする． と の要素間で起こる転倒数は かつ となる の組の個数に等しい．

これは、次のようなアルゴリズムで計算できる．

1. に設定する．
   とする．
   になったら 5. に移動する．
2. のとき、
   に を追加して 2. に戻る．
3. のとき、
   に の中で より小さい要素の個数を追加する．
   に を追加して 2. に戻る．
   
4. は と の要素間で起こるスーパー転倒数になっている．

操作 4. の で より小さい要素の個数の計算は BIT や セグ木を使用して 時間で計算できる．

計算例

例として、本問のサンプルケース2を扱う． である．

をそれぞれ2つの数列 に分割する．

先程の例で確認してみる． である．

• 

• より

  • 
  • で より小さい要素の個数は 3 より、
  • 

• より

  • 
  • で より小さい要素の個数は 2 より、
  • 

• より

  • 

• より

  • 

• より

  • 
  • で より小さい要素の個数は 1 より、
  • 

• より

  • 
  • で より小さい要素の個数は 1 より、
  • 

• より

  • 

• より終了

以上より、 と の要素間のスーパー転倒数は 7 となる．

これに、 の要素のみのスーパー転倒数と の要素のみのスーパー転倒数を加えることで、 のスーパー転倒数が求まる．

このアルゴリズムは 時間で計算できる．

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

// Binary Indexed Tree
template <class T> struct BIT {
    vector<T> d;

    BIT(int n) { init(n); }
    void init(int n) { d.assign(n + 1, 0); }

    // a: 1-indexed
    inline void add(int a, T x) {
        for (int i = a; i < (int)d.size(); i += i & -i) {
            d[i] = d[i] + x;
        }
    }

    // [1, a]
    // a: 1-indexed
    inline T sum(int a) {
        T res = 0;
        for (int i = a; i > 0; i -= i & -i) {
            res = res + d[i];
        }
        return res;
    }

    // [a, b)
    // a, b: 1-indexed
    inline T sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
};

// 昇順にソートされた数列 v において、v[i] >= x となる最小の i を返す．
int LBP(vector<int>& v, int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

void merge_sort(vector<int>& a, vector<int>& b, int& num) {
    const int n = a.size();
    if (n == 1) return;
    vector<int> a1, a2, b1, b2;
    for (int i = 0; i < n / 2; ++i) {
        a1.push_back(a[i]);
        b1.push_back(b[i]);
    }
    for (int i = n / 2; i < n; ++i) {
        a2.push_back(a[i]);
        b2.push_back(b[i]);
    }

    vector<int> b1_sorted = b1;
    sort(b1_sorted.begin(), b1_sorted.end());

    merge_sort(a1, b1, num);
    merge_sort(a2, b2, num);

    BIT<int> bit(b1.size());
    for (int bb : b1) {
        int pos = LBP(b1_sorted, bb) + 1;
        bit.add(pos, 1);
    }

    int i = 0, j = 0;
    for (int k = 0; k < n; ++k) {
        if (i != a1.size() && (j == a2.size() || a1[i] < a2[j])) {
            a[k] = a1[i];
            b[k] = b1[i];
            int pos = LBP(b1_sorted, b1[i]) + 1;
            bit.add(pos, -1);
            i++;
        } else {
            int pos = LBP(b1_sorted, b2[j]);
            num += bit.sum(pos);
            a[k] = a2[j];
            b[k] = b2[j];
            j++;
        }
    }
}

int main() {
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];
    int ans = 0;
    merge_sort(a, b, ans);
    cout << ans << endl;
}