AtCoder Regular Contest 047 C - N!÷K番目の単語

競技プログラミング

問題

　N(\le 10^5)までの整数による順列はN!個あるが、それらを辞書順に並べたときのK(\le N)個目のものを求めよ。

解法

　先頭からどの数字を置くべきか決定していくが、それを「まだ使っていない数字の中で何番目に小さいものを置くべきか」を求めることによって決定していく。辞書順X番目のものについて、たとえば1文字目は数字を決めると2番目以降は(N - 1)!通りあるため\left\lfloor \frac{X}{(N - 1)!} \right\rfloor + 1を置けば良い。

　ここでX = N! / Kであるから、これを(N - 1)!で割った商はN \div Kの商に等しく、余りはN \% K / K \times (N - 1)!であるという性質がある。これにより2文字目を決定するときは余りの数を用いてN \% K / K \times (N - 2)!と求められる。何を言っているのか理解できていないので解説スライドを参照のこと。

反省

　2時間54分(1WA)でAC。睡眠不足と体調不良でほとんどまともに考察できなかったが、とりあえず2時間を過ぎたあたりで解説スライドを見た。しかし何を言っているのか理解ができず、他の人の提出を見てほぼ写して通したという感じになった。最初の部分もわからないし、それを求めたあともBITを使って二分探索すればいいというのも出てこない考えだと思う。

　0-indexedによるズレが生じるのも面倒で、prev_permutationを使って戻す実装にしてみたところ、K = 1でWAが出るようだ。確かに手元でやってみるとそうなるんだけどさっぱりわからない。そこだけ場合分けしたらなんとか通った(これも他の人の提出で場合分けされていたのでやってみただけ)が、謎である。とにかく難しい問題だった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class BinaryIndexedTree {
public:
    BinaryIndexedTree(ll N) : N_(N), bit_(N + 1, 0) {}
    void add(ll a, ll w) {
        for (ll x = a; x <= N_; x += (x & -x)) {
            bit_[x] += w;
        }
    }
    ll sum(ll a) {
        ll result = 0;
        for (ll x = a; x > 0; x -= (x & -x)) {
            result += bit_[x];
        }
        return result;
    }
private:
    ll N_;
    vector<ll> bit_;
};

int main() {
    ll N, K;
    cin >> N >> K;

    if (K == 1) {
        for (ll i = N; i >= 1; i--) {
            cout << i << endl;
        }
        return 0;
    }

    //残っているものの中で何番目か
    vector<ll> f(N);

    //解説スライドにおける「整数」
    ll p = 1;

    //先頭から決定していく
    for (ll i = 0; i < N; i++) {
        f[i] = (N - i) * p / K + 1;
        p = (N - i) * p % K;
    }

    BinaryIndexedTree bit(N);
    for (ll i = 1; i <= N; i++) {
        bit.add(i, 1);
    }

    vector<ll> ans;
    for (ll i = 0; i < N; i++) {
        //bitの値を使って二分探索をする
        //残っているものの中でx番目の数字 <=> bit.sum(j) = xとなるj
        ll low = 0, eq_high = N;
        while (low + 1 != eq_high) {
            ll mid = (low + eq_high) / 2;
            (bit.sum(mid) < f[i] ? low = mid : eq_high = mid);
        }
        ans.push_back(eq_high);
        bit.add(eq_high, -1);
    }

    //求めたのは0-indexedのN!÷K番目なので1個戻す
    prev_permutation(ans.begin(), ans.end());

    for (ll a : ans) {
        cout << a << endl;
    }
}

AtCoder Regular Contest 046 C - 合コン大作戦

競技プログラミング

問題

　N(\le 150,000)人の男性とM(\le150,000)人の女性が合コンをした。男性は年収がA_i円であり、年収がB_i円以上の女性とカップルになりたいと考えている。女性もまた年収C_jと相手の年収D_jの希望を持っている。これらが同時に満たされるとカップルが成立するとき、最大のカップル数を求めよ。

解法

　男性と女性を混ぜて、男性は年収、女性は希望する相手の年収でソートし、小さい方から見ていく。今考えている人物が女性であれば年収をmultisetに突っ込んでいき、男性であればmultisetの中で希望年収以上であるものを一つ取り出す。この取り出す操作が可能であった回数が答えとなる。

反省

　1時間25分(3WA)でAC。40分を過ぎたあたりで男女を混ぜてそれぞれの値でソートすればいいということに気づいて実装して58分が過ぎたあたりで提出したがWA。自信があったのに取らなくて落胆してしまい、解説スライドを見た。解法は考えていたものと同じようなことが書かれていて、何が間違っているのかわからなくて結構悩んだ。

　一つにはまずmultisetではなくただのsetを使っていたというミスがあるのはわかったけれど、それを修正しても通らず。mapでやっている人が多かったのでそうしてみたがそれでも通らなかった。違う部分にミスがあると判断してコードを見直したところ、ソートするときに余計なものを考慮していたせいで順番がめちゃくちゃになってしまっていた。それを修正してAC。惜しいところまで行っていたので自力で通したかった……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;

    enum {
        //男が後になるようにソートされて欲しいのでこの順番
        FEMALE, MALE
    };
    struct Human {
        ll income, hope, sex;
    };
    vector<Human> humans(N + M);
    for (ll i = 0; i < N; i++) {
        cin >> humans[i].income >> humans[i].hope;
        humans[i].sex = MALE;
    }
    for (ll i = 0; i < M; i++) {
        cin >> humans[N + i].income >> humans[N + i].hope;
        humans[N + i].sex = FEMALE;
    }

    sort(humans.begin(), humans.end(), [&](Human& lhs, Human& rhs) {
        ll l1 = (lhs.sex == MALE ? lhs.income : lhs.hope);
        ll r1 = (rhs.sex == MALE ? rhs.income : rhs.hope);

        return (l1 == r1 ? lhs.sex < rhs.sex : l1 < r1);
    });
    
    ll ans = 0;
    multiset<ll> women_income;
    for (auto h : humans) {
        if (h.sex == MALE) {
            auto pair = women_income.lower_bound(h.hope);
            if (pair != women_income.end()) {
                ans++;
                women_income.erase(pair);
            }
        } else {
            women_income.insert(h.income);
        }
    }

    cout << ans << endl;
}

SRM517 Div1 Easy - CompositeSmash

競技プログラミング

問題

　整数Nをそれぞれ2以上である数字の積に分解する操作が行える。分解して得られる整数はランダムであるとするとき、整数targetを作ることができるかどうか判定せよ。

解法

　気合を入れて場合分けをする。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class CompositeSmash {
public:
    string thePossible(int N, int target) {
        if (N % target != 0) {
            return "No";
        }
        if (N == target) {
            return "Yes";
        }
        auto target_factor = primeFactorization(target);
        if (target_factor.size() != 1) {
            return "No";
        }
        auto top = target_factor.front();
        if (top.second == 1) {
            //targetは素数
            return "Yes";
        } else if (top.second == 2) {
            //Nもtop.firstの累乗ならYes
            auto N_factor = primeFactorization(N);
            if (N_factor.size() == 1 && N_factor.front().first == top.first) {
                return "Yes";
            } else {
                return "No";
            }
        } else {
            return "No";
        }
    }
private:
    vector<pair<ll, ll>> primeFactorization(ll n) {
        vector<pair<ll, ll>> result;
        for (ll i = 2; i * i <= n; i++) {
            ll num = 0;
            while (n % i == 0) {
                n /= i;
                num++;
            }
            if (num != 0) {
                result.push_back({ i, num });
            }
        }

        if (n != 1) {
            result.push_back({ n, 1 });
        }

        return result;
    }
};

SRM516 Div1 Easy - NetworkXOneTimePad

競技プログラミング

問題

　ciphertextsにある任意の数字が、plaintextsのどれかの数字にxorしたものに等しくなるようなキーの数を求めよ。

解法

　各暗号化済みの数字と暗号化前の数字のxorを取るとキーとなり得る数字を求められる。それの登場回数をmapで数えておく。キーとなる数が暗号化済みの数字数と同じ数だけ出てきたらそれはすべてに対してキーになっているということなので計算量はO(NM\log{NM})でこの問題が解けた。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class NetworkXOneTimePad {
public:
    int crack(vector<string> plaintexts, vector<string> ciphertexts) {
        vector<ll> p(plaintexts.size()), c(ciphertexts.size());
        for (ll i = 0; i < plaintexts.size(); i++) {
            p[i] = toLL(plaintexts[i]);
        }

        map<ll, ll> num;
        for (ll i = 0; i < ciphertexts.size(); i++) {
            c[i] = toLL(ciphertexts[i]);
            for (ll j = 0; j < plaintexts.size(); j++) {
                num[c[i] ^ p[j]]++;
            }
        }

        ll ans = 0;
        for (auto p : num) {
            if (p.second == ciphertexts.size()) {
                ans++;
            }
        }

        return ans;
    }
private:
    ll toLL(string binary) {
        ll result = 0;
        for (ll i = 0; i < binary.size(); i++) {
            if (binary[i] == '1') {
                result |= (1LL << (binary.size() - i - 1));
            }
        }
        return result;
    }
};

AtCoder Regular Contest 045 C - エックスオア多橋君

競技プログラミング

問題

　N頂点の木が与えられる。各辺に非負整数のコストがついているとき、頂点aとbを結ぶ単純パスにおいて通る辺のコストを全てxor取っていったものがある整数Xになるような(a, b)の組み合わせが何通りあるか求めよ。

解法

　ある頂点xを根と決めたとき、 a \to bという単純パスとa \to x \to bというパスでは通る辺のコストのxorを取っていった値は等しくなる。なぜなら a \to bという単純パスがもともと頂点xを含むなら自明であるし、含まないときはxから見てa,bの近い方へは往復することになるが、xorなので打ち消すことになるからである。

　よって結局頂点x:から見たxorの値に関して、その値となるパスが何個存在するかを数えていけばいい。そして現在のパスに関してxorの値がvならばX xor vとなるパスの個数を答えに加算していけばO(N\log{N})でこの問題が解ける。

反省

　1時間10分(2WA)でAC。今見ている頂点から先で得られるxor値の個数を数えて伝播させる方法で解けると思って提出したがこれはO(N^2)かかるものでありTLEだった。結局1時間過ぎてしまい、違う解法が思い浮かぶ気がしなかったので解説スライドを見たが、発想としては近そうで遠いものだった。xorの性質を上手く使えていないのでもっとそこに注意を向けるべきだった。

　別解として書いてある「データ構造をマージする一般的なテク」とやらを調べて、なんか使えそうな気がしたのでTLE解の方をいろいろいじってやってみたが答えが合わず断念。しかしこれは知っておく価値が大きそうなテクニックだ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, X;
struct Edge {
    ll to, cost;
};
vector<vector<Edge>> edges;
ll ans = 0;
map<ll, ll> mp;

void dfs(ll curr, ll pre, ll value) {
    ans += mp[value ^ X];
    mp[value]++;
    for (Edge e : edges[curr]) {
        if (e.to == pre) {
            continue;
        }

        dfs(e.to, curr, value ^ e.cost);
    }
}

int main() {
    cin >> N >> X;
    edges.resize(N + 1);
    for (ll i = 0; i < N - 1; i++) {
        ll x, y, c;
        cin >> x >> y >> c;
        edges[x].push_back({ y, c });
        edges[y].push_back({ x, c });
    }

    dfs(1, -1, 0);
    cout << ans << endl;
}

AtCoder Regular Contest 044 C - ビーム

競技プログラミング

問題

　H\times W(H, W\le 10^5)のグリッドにビームが飛んでくる。ビームは時刻tに縦方向あるいは横方向についてあるマスを通るように飛ぶ。高橋君は任意のマスからスタートして上下左右のマスについて単位時間に任意の回数移動できる。全てのビームについての情報がわかっているとき、全てのビームを避ける最小の移動回数を求めよ。

解法

　X軸方向とY軸方向はそれぞれ独立に考えて良い。各軸について、それぞれ時刻iに座標jにいるときの最小移動回数を求めればよいが、これは愚直にDPで求めるとO(T(H + W))かかってしまう。

　各時刻でビームが飛んでくる状況を考えると、そのマスから移動することにより左右のマスに配るようなDPをすればよいことがわかる。隣接マスにもビームが飛んできている可能性があるため、まず各時刻におけるビームが来る座標をソートしておいて、小さい方から見ていき大きい方へ避ける移動、大きい方から見ていき小さい方へ避ける移動をそれぞれ遷移させていく必要がある。これによって各時刻について全ての座標を見る必要がなくなり、飛んでくるビームの本数にのみ依存するようになるので計算量はO(W+H+T)でこの問題が解ける。

反省

　1時間54分(4WA)でAC。1時間考えてもさっぱり歯が立たない感じだったので解説スライドを見た。各軸は独立に考えて良いという発想は、それぞれ行と列を考えてminを取れば全ての座標について求まるのか？ くらいには思っていたが、完全に独立に考えて良いというところまでは至っていなかった。

　解説を読んでからもDPの遷移を書くのが結構大変で、WAをたくさん出してしまった。自分の実装だとソートをする(setを使う)要素があるので計算量はO(W+H+T + Q\log{Q})になっているのかな？ 制約が一段緩くてもこの問題を解けたかどうか……。しかし座標を一つ一つ考えることすらできない制約なわけだから、独立になっていそうと思うのは当たり前なんだろうなぁ。そしてそれを確認するのも上手くできるようにならなくては。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll W, H, Q;
    cin >> W >> H >> Q;

    constexpr ll T_MAX = (ll)1e5 + 1;
    //beams[i][j] := 時刻iに方向jのビームが来る座標
    vector<vector<set<ll>>> beams(T_MAX, vector<set<ll>>(2));
    for (ll i = 0; i < Q; i++) {
        ll T, D, X;
        cin >> T >> D >> X;
        beams[T][D].insert(X);
    }

    constexpr ll INF = INT_MAX;

    ll ans = 0;

    for (ll d = 0; d < 2; d++) {
        //縦方向,横方向それぞれについて考える
        const ll MAX = (d == 0 ? W : H);

        //dp[j] := (時刻iに)座標jにいるときの移動距離の最小値
        vector<ll> dp(MAX + 2, 0);

        //番兵
        dp[0] = dp[MAX + 1] = INF;

        for (ll i = 0; i < T_MAX; i++) {
            //順方向に避ける
            for (auto itr = beams[i][d].begin(); itr != beams[i][d].end(); itr++) {
                dp[*itr + 1] = min(dp[*itr + 1], dp[*itr] + 1);
            }
            //逆向きに避ける
            for (auto itr = beams[i][d].rbegin(); itr != beams[i][d].rend(); itr++) {
                dp[*itr - 1] = min(dp[*itr - 1], dp[*itr] + 1);
            }
            for (ll a : beams[i][d]) {
                dp[a] = INF;
            }
        }

        ans += *min_element(dp.begin() + 1, dp.end() - 1);
    }

    cout << (ans >= INF ? -1 : ans) << endl;
}

AtCoder Regular Contest 043 C - 転倒距離

競技プログラミング

問題

　2つの順列について順序が入れ替わっている数字の組の個数を転倒距離と呼ぶこととする。サイズN(\le 10^5)の順列A, Bが与えられたとき、AともBとも転倒距離が等しい順列があるか判定し、ある場合には1つ挙げよ。

解法

　まず適当な数字の置き換えをしてAが1, 2, \dots, Nという配列になるようにする。これによりAとBがA'( = 1, 2, \dots, N)とB'になったとすると、AとBの転倒距離はB'の転倒数に等しくなる。ある順列の転倒数はマージソートのようなやり方でO(Nlog{N})で求めることができる。( tmaehara氏のスライドなどを参照のこと)

　B'の転倒数が奇数であるとき、AともBとも転倒距離が等しい順列は存在しない。(証明は解説スライドを参照のこと)

　B'の転倒数が偶数であるとき、バブルソートをシミュレーションすればちょうど転倒距離が等しいものを求めることができるが、愚直に行うとO(N^2)かかるため、セグメント木などを使ってO(N\log{N})でシミュレーションできるように高速化することでこの問題が解ける。

反省

　1時間52分(4WA)でAC。転倒数に帰着させて奇数の場合は構築不可というところまでは(感覚的に)わかったが、まず転倒数を高速に求める方法がわからなかったので30分ほど過ぎたあたりで諦めて検索をしてO(N\log{N})で求められることを知った。なんとかそれを30分ほどかけて実装したが、偶数のときに実際に構築する方法がわからず結局解説スライドを見た。

　転倒数はバブルソートと深い関係があるというのはちょっとだけ知っていたが、シミュレーションすればいいという発想に至っていなかった。さらにそれをセグメント木などを使って高速化するということで、コンテストで出されたらなかなか解けそうにない。

　Aを変換したり、最後に答えを変換しなおしたりというのを勘でやってなんか通ってしまったのであまり問題(解法)をしっかり理解できたという気がしない。

　とりあえずセグメント木に加えて転倒数も自作ライブラリに突っ込んでおいた。あまりマージソートを理解していないままなので良いこととは思えないが……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class InversionCount {
public:
    InversionCount(vector<ll> target) : target_(target) {}
    ll count(ll left = 0, ll right = -1) {
        if (right < 0) {
            //rはtarget_.size()で初期化
            right = target_.size();
        }
        if (right <= left + 1) {
            return 0;
        }
        ll mid = (left + right) / 2;
        ll result = 0;
        //左半分を数える
        result += count(left, mid);

        //右半分を数える
        result += count(mid, right);

        //左右またぐ数を数える
        result += merge(left, mid, right);

        return result;
    }
private:
    ll merge(ll left, ll mid, ll right) {
        vector<ll> l, r;
        for (ll i = left; i < mid; i++) {
            l.push_back(target_[i]);
        }
        for (ll i = mid; i < right; i++) {
            r.push_back(target_[i]);
        }
        //番兵
        l.push_back(LLONG_MAX);
        r.push_back(LLONG_MAX);

        ll left_index = 0;
        ll right_index = 0;
        ll result = 0;
        for (ll i = left; i < right; i++) {
            if (l[left_index] <= r[right_index]) {
                target_[i] = l[left_index];
                left_index++;
            } else {
                target_[i] = r[right_index];
                right_index++;
                result += ((mid - left) - left_index);
            }
        }
        return result;
    }

    vector<ll> target_;
};

//1点更新,区間和
class SegmentTree {
public:
    SegmentTree(ll n, ll value) {
        n_ = (ll)pow(2, ceil(log2(n)));
        nodes_.resize(2 * n_ - 1, value);
    }
    void update(ll x, ll v) {
        nodes_[x + n_ - 1] = v;
        for (ll i = (x + n_ - 2) / 2; i > 0; i = (i - 1) / 2) {
            nodes_[i] = nodes_[2 * i + 1] + nodes_[2 * i + 2];
        }
    }

    ll getSum(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) {
            r = n_;
        }
        if (r <= a || b <= l) {
            return 0;
        }
        if (a <= l && r <= b) {
            return nodes_[k];
        }
        ll left  = getSum(a, b, 2 * k + 1, l, (l + r) / 2);
        ll right = getSum(a, b, 2 * k + 2, (l + r) / 2, r);
        return left + right;
    }

private:
    //2のべき乗
    ll n_;
    vector<ll> nodes_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    vector<ll> pos(N + 1, 0), B2(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
        pos[A[i]] = i + 1;
    }
    for (ll i = 0; i < N; i++) {
        cin >> B[i];
        B2[i] = pos[B[i]];
    }

    InversionCount ic(B2);
    ll inversion_count = ic.count();

    if (inversion_count % 2 == 1) {
        cout << -1 << endl;
    } else {
        inversion_count /= 2;
        SegmentTree st(N + 1, 0);
        vector<ll> ans;
        for (ll i = 0; i < N; i++) {
            ll sum = st.getSum(B2[i] + 1, N + 1);
            st.update(B2[i], 1);

            //移動量
            ll v = min(sum, inversion_count);

            inversion_count -= v;
            ans.insert(ans.end() - v, B2[i]);
        }
        assert(inversion_count == 0);

        for (ll i = 0; i < N; i++) {
            cout << A[ans[i] - 1] << " \n"[i == N - 1];
        }
    }
}

AtCoder Regular Contest 042 C - おやつ

競技プログラミング

問題

　N種類のおやつについてそれぞれ値段と満足度が設定されており、各種類について多くとも1つ持っていくことができる。どの1つのおやつについてもそのおやつがなければ合計でP円以下になるとき持っていくことが可能である場合に、満足度の最大値を求めよ。

解法

　あるおやつ集合の中で一番値段が小さいもの一つを除いた値段の和sを考えると、他のおやつを除いた場合は必ずs以下になるため、sがP以下であるかどうかを考えればよい。

　(あるおやつを除いたとして)残りのおやつから値段がP以下となるように満足度を最大化することはDPでできる。

　値段を降順にソートしてからDPテーブルを作れば、答えを求めるときに各おやつに対して同じテーブルを使うことができる。よってO(N\log{N} + NP)でこの問題が解ける。

反省

　1時間28分(6WA)でAC。最初考えた方針がかなり想定解に近かったが、O(N\log{N} + NP\times (\max{a}))というような最悪で100倍遅いものを考えていたし、実装も間違っていてWA。その後もmapを使って高速化できるんじゃないかとか意味不明なことを考え出してTLEやWAなどを次々出していく。結局1時間経ってしまったので解説スライドを見た。1ページ。超短い。見た後も実装にちょっと苦労してしまったがなんとかAC。終わってみれば簡単な問題で、なんでこれが解けないのか。もっと考察で簡単に書けるコードを思い浮かべれれるようにならなければ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, P;
    cin >> N >> P;

    struct Snack {
        ll a, b;
    };

    vector<Snack> snacks(N);
    for (ll i = 0; i < N; i++) {
        cin >> snacks[i].a >> snacks[i].b;
    }

    sort(snacks.begin(), snacks.end(), [&](Snack& lhs, Snack& rhs){
        return lhs.a != rhs.a ? lhs.a > rhs.a : lhs.b > rhs.b;
    });

    //dp[i][j] := i番目まで見てj円以下の場合の最大幸福度
    vector<vector<ll>> dp(N, vector<ll>(P + 1, 0));

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= P; j++) {
            //i番目を持っていかない
            dp[i][j] = max(dp[i][j], (i == 0 ? 0 : dp[i - 1][j]));

            //i番目を持っていく
            ll p = j + snacks[i].a;
            if (p > P) {
                continue;
            }
            dp[i][p] = max(dp[i][p], (i == 0 ? 0 : dp[i - 1][j]) + snacks[i].b);
        }
    }

    ll ans = (snacks[0].a <= P ? snacks[0].b : 0);
    for (ll i = 1; i < N; i++) {
        ans = max(ans, dp[i - 1][P] + snacks[i].b);
    }

    cout << ans << endl;
}

AtCoder Regular Contest 041 C - ウサギ跳び

競技プログラミング

問題

　L(\le 10^9)個のマスが横一列に並んでおり、マスの上にはN(\le10^5)匹のウサギが右か左を向いている。ウサギは向いている方向の一つ前のマスに他のウサギがいなければジャンプしてそのマスへ移動できる。ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を求めよ。

解法

　二匹のウサギが向き合っているとき、後ろに連続して同じ向きで待っているウサギがいる数の多い方のみがジャンプするのが最善となる。その数を数えて貪欲に動かせばO(N)でこの問題が解ける。

反省

　19分59秒(0WA)でAC。理屈から言って解けそうなのはすぐわかったが、何に注目して考えると考えやすい/実装しやすいかというのがちょっとわからなかった。結局i番目のウサギが動くべきかどうかというのを全部最初に求めてしまうのがわかりやすいかと思ったが、コードは結構長くなってしまった。解説スライドでは区間に分けて考えるとあり、これはなかなか実践的な思考法なんだろうなと感じた。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, L;
    cin >> N >> L;

    struct Usagi {
        ll x, follow_num;
        char d;
        bool move;
    };
    vector<Usagi> usa(N);
    for (ll i = 0; i < N; i++) {
        cin >> usa[i].x >> usa[i].d;
        usa[i].move = true;
    }
    

    //右向きウサギについて数える
    ll num = 0;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //左向きウサギについて数える
    num = 0;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //i番目のウサギが動くかどうかについて考える
    //前にいるウサギがこちらを向いており
    //向こうの方が後ろに続くウサギが多かったらこっちは動かない
    for (ll i = 0; i < N - 1; i++) {
        if (usa[i].d == 'R' && usa[i + 1].d == 'L') {
            if (usa[i].follow_num < usa[i + 1].follow_num) {
                usa[i].move = false;
            } else {
                usa[i + 1].move = false;
            }
            i++;
        }
    }

    ll ans = 0;

    //右向きウサギを限界まで動かす
    //行ける一番右のマス
    ll limit = L;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L' || !usa[i].move) {
            limit = usa[i].x - 1;
        } else {
            ans += limit - usa[i].x;
            usa[i].x = limit;
            limit--;
        }
    }

    //左向きウサギを限界まで動かす
    limit = 1;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R' || !usa[i].move) {
            limit = usa[i].x + 1;
        } else {
            ans += usa[i].x - limit;
            usa[i].x = limit;
            limit++;
        }
    }

    cout << ans << endl;
}

AtCoder Regular Contest 040 C - Z塗り

競技プログラミング

問題

　N\times N(N \le 100)のマス目状になっている床を一色に塗ることを考える。一回の塗る操作で、ある整数r,cに対して「i=rかつj\le c」または「i=r + 1かつj \ge c」を満たすような全てのマス(i, j)を塗ることができる。部分的に塗られている初期状態が与えられるので、全てのマスを塗る最小の操作回数を求めよ。

解法

　各行に対して右側からみてまだ塗られていないマスがあったらそこを(r, c)として塗る貪欲法で計算量はO(n^3)でありこの問題が解ける。

反省

　9分4秒(0WA)でAC。特に難しいところもなく。昨日一昨日に比べてこの難易度の差。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<string> S(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = N - 1; j >= 0; j--) {
            if (S[i][j] == '.') {
                //(i, j)で一回塗る
                ans++;

                //i段目が塗られる
                for (ll k = 0; k <= j; k++) {
                    S[i][k] = 'o';
                }

                //i + 1段目が塗られる
                if (i != N - 1) {
                    for (ll k = j; k < N; k++) {
                        S[i + 1][k] = 'o';
                    }
                }
            }
        }
    }

    cout << ans << endl;
}