けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 047 C - 一次元リバーシ (4Q, 茶色, 300 点)

AtCoder AtCoder300点 ABC-C 茶色diff 気付き系 易しい計算量改善 計算量改善:O(N)で求められる式に変形する オセロ 0と1の問題 for文 条件の言い換え 最適化テク:自明な上界が最適解 NoviSteps4Q 一次元グリッド 最小回数・最小個数を求める 最適化問題

綺麗な言葉で条件を言い換えよう！

問題概要

一列に白色碁石と黒色碁石が合計 N 個並んでいる。

左右のいずれかに白色碁石と黒色碁石を置いていく。このとき、オセロのルールに基づいて石の色がひっくり返る。

すべての色を同色にするのに必要な操作回数の最小値を求めよ。

制約

  • 1 \le N \le 10^{5}

考えたこと

この手の問題では、まずはいろいろなケースを実験してみるとよいだろう。たとえば、

  • "BBWWW"：右から B を打つことで、すべて B になるので 1 回
  • "BBWWWBBB"：右か W を打ち、その後 B を打つことで、すべて B になるので 2 回（1 回ではできない）
  • "BBWWWBBBW"：右から B、W、B の順に打つことで、すべて B になるので 3 回（2 回ではできない）

という感じになる。ここから見えてくることは、もとの盤面で、B と W の変わり目が多ければ多いほど、必要回数が増えるのではないか？？ということだ。もっとちゃんと整理すると、

もとの盤面で、B と W の変わり目が m 箇所あるとき、最小回数 m-1 回であろう

と予想できる。コンテスト本番ならば、この段階でもう提出しても良いと思う。ここでは念のために、簡単に証明してみよう。

最小回数が m-1 回であることの証明

具体的には、次の 2 つを示せば良いです。

  • すべて同色にするためには、少なくとも m-1 回以上必要であること
  • どんな盤面でもかならず m-1 回で同色にできること

前者は、「1 回の操作によって、W と B の変わり目の個数が 2 個以上減少することはない」ことによって示せます。

後者は、たとえば、右側から「右端の碁石と異なる色の石を置いていく」を繰り返すことで実現できます。

コード

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

int main() {
    string S;
    cin >> S;
    int res = 0;
    for (int i = 0; i+1 < S.size(); i++) {
        if (S[i] != S[i+1]) res++;
    }
    cout << res << endl;
}

AtCoder ABC 050 B - Contest with Drinks Easy (6Q, 灰色, 200 点)

AtCoder AtCoder200点 ABC-B 灰色diff NoviSteps6Q for文 関数 数列 クエリ処理問題 易しいクエリ処理問題

for 文を回す処理を M 回やる問題

問題概要

N 個の整数からなる数列 T_{1}, T_{2}, \dots, T_{N} が与えられる。次の M 回のクエリに答えよ。

【クエリ】
整数 P, X が与えられる。 T_{P} を X に変更したときの、 T_{1} + T_{2} + \dots + T_{N} の値を答えよ。（なお、クエリごとに変更は引き継がれない。）

考えたこと

色んな実現方法が考えられるが、ここでは次のような関数を実装することにした。

// T[P] を X に変更したときの T の総和
int calc(vector<int> T, int P, int X) {
    int sum = 0;
    T[P] = X;
    for (int i = 0; i < T.size(); i++) sum += T[i];
    return sum;
}

このような関数化のメリットの一つとして、関数内部で T を変更しても、関数の外では変更されない。（逆に関数の外でも変更されて欲しかったら参照渡しを使おう。）

この関数 calc() を用いて、次のコードのように書ける。

コード

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

int calc(vector<int> T, int P, int X) {
    int sum = 0;
    T[P] = X;
    for (int i = 0; i < T.size(); i++) sum += T[i];
    return sum;
}

int main() {
    int N, M, P, X;
    cin >> N;
    vector<int> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];
    cin >> M;
    for (int _ = 0; _ < M; _++) {
        cin >> P >> X, P--;  // 0 始まりに直す
        cout << calc(T, P, X) << endl;
    }
}

AtCoder ABC 047 B - すぬけ君の塗り絵 2 イージー (6Q, 灰色, 200 点)

AtCoder AtCoder200点 ABC-B 灰色diff NoviSteps6Q 計算幾何 易しい算数と数学 算数と数学 区間の交差 N個の長方形の問題 操作:長方形領域 二次元平面上のN点の問題 数学(図形問題) 易しい図形問題

「白い部分」が常に長方形であることから、その位置を上手に管理しよう。

問題概要

座標平面上で、2 点 (0, 0), (W, H) を対角線とする長方形領域が与えられる。はじめ、全体が白く塗られている。この領域に対して、次の Q 回の操作を行なった。

【操作】
3 つの整数 x_{i}, y_{i}, a_{i} が与えられる。

  • a_{i} = 1 のとき： x \lt x_{i} を満たす部分を黒く塗る
  • a_{i} = 2 のとき： x \gt x_{i} を満たす部分を黒く塗る
  • a_{i} = 3 のとき： y \lt y_{i} を満たす部分を黒く塗る
  • a_{i} = 4 のとき： y \gt y_{i} を満たす部分を黒く塗る

すべての操作を終えたあとの、白い部分の面積を求めよ。

制約

  • 1 \le W, H, N \le 100

考えたこと

白い部分は常に長方形になる！！！

よって、次の 4 つの値を管理することにしよう。

  • lx：白い部分の左端の x 座標
  • rx：白い部分の右端の x 座標
  • ly：白い部分の下端の y 座標
  • ry：白い部分の上端の y 座標

これらの値を適切に更新し、最後は (rx - lx) * (ry - ly) の値を答えれば良い（lx < rx かつ ly < ry の場合のみ）。

コード

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

int main() {
    int W, H, N, x, y, a;
    cin >> W >> H >> N;

    int lx = 0, rx = W, ly = 0, ry = H;
    for (int _ = 0; _ < N; _++) {
        cin >> x >> y >> a;
        if (a == 1) lx = max(lx, x);
        else if (a == 2) rx = min(rx, x);
        else if (a == 3) ly = max(ly, y);
        else ry = min(ry, y);
    }
    if (lx <= rx && ly <= ry) cout << (rx - lx) * (ry - ly) << endl;
    else cout << 0 << endl;
}

AtCoder ABC 046 D - AtCoDeerくんと変なじゃんけん (ARC 062 D) (2Q, 水色, 300 点)

AtCoder AtCoder300点 ABC-D ARC-D 水色diff Greedy:交換しても悪化しない Greedy 最適化テク:操作の流れを単純化する ジャンケン 0と1の問題 NoviSteps2Q 最適化問題 最大スコア ゲーム

一見、 O(N^{2}) の DP に見えたが、その必要はなかった。

問題概要

グーとパーしか出せないジャンケンを N 回する。相手が各回に何を出すかが予めわかっている。ただし、どの時点でも

(それまでに出したグーの回数) \ge (それまでに出したパーの回数)

を満たし続けなければならない。

(勝つ回数) - (負ける回数) の最大値を求めよ。

制約

  • 1 \le N \le 10^{5}

考えたこと

一瞬、次のような DP を考えた。

  • dp[i][j]：最初の i 回のジャンケンで、(グーを出した回数) - (パーを出した回数) = j であるようにしたときの、(勝った回数) - (負けた回数) の最大値

しかし、これでは O(N^{2}) の計算量となってしまう。そして、容易には改善できなさそうだった。

そこで作戦を考えて「実はグーとパーを出す順序はあまり関係ないのでは」という方面の考察をしてみた。そして、この予想はあたった。

ある 2 回で出す手が「パー、グー」であるとき、これを入れ変えて「グー、パー」にしても、次の通り、スコアが変わらないのだ。

  • 相手が「パー、パー」のとき：-1
  • 相手が「パー、グー」のとき：0
  • 相手が「グー、パー」のとき：0
  • 相手が「グー、グー」のとき：1

よって、グーの回数とパーの回数だけが問題なのだ。なるべく多くのパーを出したいので、

  • グーの回数：(N + 1) / 2 回
  • パーの回数：(N - 1) / 2 回

とするのがよいだろう。あとは、最初の (N + 1) / 2 回グーを出して、後半の (N - 1) / 2 回パーを出すとして、勝敗を求めれば良い。

計算量は O(N) となる。

コード

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

int main() {
    string S;
    cin >> S;
    int N = S.size(), res = 0;
    for (int i = 0; i < (N + 1) / 2; i++) {
        if (S[i] == 'p') res--;
    }
    for (int i = (N + 1) / 2; i < N; i++) {
        if (S[i] == 'g') res++;
    }
    cout << res << endl;
}

AtCoder ABC 046 C - AtCoDeerくんと選挙速報 (ARC 062 C) (4Q, 水色, 300 点)

AtCoder AtCoder300点 水色diff ABC-C ARC-C NoviSteps4Q 易しい算数と数学 算数と数学 シミュレーション 切り上げ処理 シミュレーション:繰り返し回数を割り算で求める 愚直シミュレーション 最適化問題 最小コスト 数学(整数問題) 互いに素

問題文の理解が大変かもしれない

問題概要（意訳）

2 つの正の整数 t, a を次のように N 回更新していく。最初、 t = a = 1 である。

i 回目の更新では 2 つの互いに素な正の整数 T_{i}, A_{i} が与えられるので、

  • X \ge t
  • Y \ge a
  • X : Y = T_{i} : A_{i}

を満たすような 2 つの正の整数 X, Y を 1 つ求めて、 t, a をそれぞれ X, Y に置き換える。

最終結果における t + a の値の最小値を求めよ。

制約

  • 1 \le N \le 1000
  • 1 \le T_{i}, A_{i} \le 1000

考えたこと

単純に、毎回 X, Y の値をできるだけ小さく抑えるようにすればよい。そのためには

  • T_{i} x \ge t
  • A_{i} y \ge a

を満たすような最小の x, y を求めて、次のようにすればよい。

  • t を T_{i} \times \max(x, y) の値に置き換える
  • a を A_{i} \times \max(x, y) の値に置き換える

毎回の処理は O(1) の計算量で実行できるので、全体の計算量は O(N) となる。

コード

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

int main() {
    long long N, T, A, res_t = 1, res_a = 1;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> T >> A;

        // Tx >= res_t, Ay >= res_a を満たす最小の x, y を求めて、その最大値をとる
        long long x = (res_t + T - 1) / T;
        long long y = (res_a + A - 1) / A;
        res_t = T * max(x, y), res_a = A * max(x, y);
    }
    cout << res_t + res_a << endl;
}