ながめも

競技プログラミングについて

Codeforces Round #672 (Div. 2) 参加記

コンテスト参加記 Codeforces Div2 XOR DP 数え上げ区間座圧

A. Cubes Sorting

すべての要素が異なり、逆順に並んでいるとき、バブルソートは最大で $N(N-1)/2$ 回の操作が必要になります。そうでないとき、それ未満で終わります。

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];
    rep(i,N-1){
        if(a[i] <= a[i+1]){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

B. Rock and Lever

いつものxorを+と&に変換するやつかと思って式変形して戸惑っていましたが、今回は最上位bitがどうなるかだけに注目すればよいです。　

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];
    sort(all(a));
    vector<ll> cnt(64, 0);
    rep(i,N){
        for(int k = 63; k >= 0; k--){
            if(bit(k)&a[i]){
                cnt[k]++;
                break;
            }
        }
    }
    dump(cnt);
    ll ans = 0;
    rep(k,64)ans += cnt[k] * (cnt[k]-1) / 2;
    cout << ans << endl;
}

C1. Rescue Nibel!

簡単なDPです。

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];
    ll dp[2] = {0, -INFLL};
    rep(i,N){
        ll nxt[2] = {-INFLL, -INFLL};
        rep(j,2){
            chmax(nxt[j], dp[j]);
            chmax(nxt[j^1], dp[j] + (j ? -a[i]: a[i]));
        }
        rep(j,2)swap(dp[j], nxt[j]);
    }
    cout << max(dp[0], dp[1]) << endl;
}

D. Rescue Nibel!

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<ll> l(N), r(N);
    map<ll,int> mp;
    rep(i,N){
        cin >> l[i] >> r[i];
        mp[l[i]-1]++;
        mp[l[i]]++;
        mp[l[i]+1]++;
        mp[r[i]-1]++;
        mp[r[i]]++;
        mp[r[i]+1]++;
    }
    int idx = 1;
    for(auto &p: mp)p.second = idx++;
    rep(i,N){
        l[i] = mp[l[i]];
        r[i] = mp[r[i]];
    }
    ll M = idx + 5;
    vector<ll> imos(M);
    vector<ll> outs(M);
    rep(i,N){
        imos[l[i]]++;
        imos[r[i]+1]--;
        outs[r[i]]++;
    }
    rep(i,M-1)imos[i+1] += imos[i];
    mint ans = 0;
    rep(i,M){
        ll old = imos[i] - outs[i];
        // 少なくとも一つがnewであるもの　=> 余事象で全部がoldのものを引けばよい
        mint add = C.Comb(imos[i], K);
        add -= C.Comb(old, K); 
        ans += add;
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 179 ABC179 参加記

コンテスト参加記 AtCoder ABC imos法 DP 区間周期鳩の巣原理 MOD

A - Plural Form
- 解説
- 実装
B - Go to Jail
- 解説
- 実装
C - A x B + C
- 解説
- 実装
D - Leaping Tak
- 解説
- 実装
E - Sequence Sum
- 解説
- 実装
F - Simplified Reversi

A - Plural Form

問題へのリンク

解説

末尾を確認します。

実装

int main() {
    string S;
    cin >> S;
    if(S.back() == 's'){
        S.push_back('e');
    }
    S.push_back('s');
    cout << S << endl;
}

B - Go to Jail

問題へのリンク

解説

連続する3つについて全てゾロ目かどうかをチェックします。

実装

int D[111][2];
int main() {
    int N;
    cin >> N;
    bool ok = false;
    rep(i,N){
        cin >> D[i][0] >> D[i][1];
    }
    rep(i,N-2){
        if(D[i][0] == D[i][1]){
            if(D[i+1][1] == D[i+1][0]){
                if(D[i+2][0] == D[i+2][1]){
                    ok = true;
                }
            }
        }
    }
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - A x B + C

問題へのリンク

解説

$A$ を固定します。 $C$ が正になるような $B$ の個数を割り算で求めます。

実装

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

    ll ans = 0;
    for(ll a = 1; a <= N; a++){
        if(N%a == 0){
            ans += N / a - 1;
        }
        else ans += N/a;
    }
    cout << ans << endl;
}

D - Leaping Tak

問題へのリンク

解説

区間addを配らなければならないので計算量が爆発しそうですが、imos法をdpを進めながら使うことで、解決します。初期状態として、

dp[0] = 1, dp[1] = -1

とするのは、区間[0, 1)に1があることに対応します。

実装

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> l(K), r(K);
    rep(i,K)cin >> l[i] >> r[i];
    vector<mint> dp(N+10, 0);
    dp[0] = 1;
    dp[1] = -1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            int L = min(N, i + l[j]);
            int R = min(N+1, i + r[j])+1;
            dp[L] += dp[i];
            dp[R] -= dp[i];
        }
        dp[i+1] += dp[i];
    }
    cout << dp[N-1] << endl;
}

E - Sequence Sum

問題へのリンク

解説

鳩の巣原理により、 $M$ 項目までにループします。よって、ループを見つけるまで計算し、後はいい感じに和を取ります。実装が大変です。

実装

int main() {
    ll N, X, M;
    cin >> N >> X >> M;
    ll a = X;
    map<ll, int> mp;
    ll sum = a;
    ll cnt = 1;
    vector<ll> cumsum(1, 0);
    cumsum.push_back(a);
    mp[a] = 1;
    while(mp.find((a*a)%M) == mp.end()){
        a *= a;
        a %= M;
        sum += a;
        mp[a] = ++cnt;
        cumsum.push_back(sum);
        if(cnt == N){
            cout << sum << endl;
            return 0;
        }
        dump(a, cnt);
    }
    if(a == 0){
        cout << sum << endl;
        return 0;
    }
    int l_cnt = mp[(a*a)%M]-1;
    int r_cnt = mp[a];
    int len = r_cnt - l_cnt;
    ll ans = cumsum[l_cnt];
    N -= l_cnt;
    ans += N / len * (cumsum[r_cnt] - cumsum[l_cnt]);
    ans += cumsum[l_cnt + N%len] - cumsum[l_cnt];
    cout << ans << endl;
}

F - Simplified Reversi

問題へのリンク

まだわかっていません。

ACL Contest 1 参加記

コンテスト参加記 AtCoder ARC 2変数を1変数に UnionFInd 二分探索素因数分解互いに素拡張ユークリッドの互除法

2完青パフォでした。ACLはほとんど対策できてなかったのですが、自分のレート帯なら関係ないだろうと思って考察を頑張りました。Bでコンテスト前にたまたま目にした拡張ユークリッドの互除法が使える問題が出て、運がよかったです。

jjjjjjjtgpptmjjさんのACL Contest 1での成績：332位
パフォーマンス：1835相当
レーティング：1434→1481 (+47) :)
Highestを更新しました！#AtCoder #ACLContest1 https://t.co/Q9Ypyd5ynZ
— naga@精進 (@longeqe) 2020年9月21日

A - Reachable Towns
- 解説
- 実装
B - Sum is Multiple
- 解説
- 実装

A - Reachable Towns

問題へのリンク

解説

まず、 $x,y$ 座標の2変数を処理するのは困難なので、 $x$ でソートし、その配列を前から見ていきます。すると、自分より前に見た点は、必ず $x$ 座標が小さいので、 $y$ 座標も小さいものをmergeすればよいことがわかります。mergeした後は、mergeしたうち一つだけが未来の選択肢と残っていれば十分ですが、これはy座標が最も小さいものに代表させましょう。なぜなら、最もmergeされやすいからです。

選択肢の保存には二分探索したい関係で、std::setを使います。小さい方からとれる優先度つきqueueなどでもよさそうです。

実装

struct UnionFind{
    /**/
};
int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    UnionFind Uni(N);
    vector<pair<i_i, int>> xyi;
    rep(i,N){
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
        xyi.push_back({{x[i], y[i]}, i});
    }
    sort(all(xyi));
    set<pair<int, int>> st;
    // 今入ってる座標は全てx座標が自分未満なので、y座標が自分未満のやつを探せば良い
    rep(i,N){
        auto pp = xyi[i];
        auto [p, idx] = pp;
        auto [a, b] = p;
        // stの中の{b,INF}未満のやつを全てuniteする
        int ue = b;
        int minn = b;
        while(1){
            auto itr = st.lower_bound({ue, INF});
            if(itr == st.begin())break;
            itr--;
            auto tmp = *itr;
            auto [sita, idx2] = tmp;
            Uni.unite(idx, idx2);
            st.erase(itr);
            chmin(minn, sita);
        }
        st.insert({minn, idx});
    }
    rep(i,N){
        cout << Uni.size(i) << endl;
    }
}

B - Sum is Multiple

問題へのリンク

解説

$K \times (K+1)$ が $2N$ の倍数になればよいです。連続する2つの整数は互いに素、つまり $K$ と $K+1$ に共通する素因数がないことから、 $2N$ の素因数を素数ごとに別々に押し付けることになります。ここで、 $2N$ の素因数となる素数は高々 $13$ 個しかないので、それらの割り振りをbit全探索します。そうして割り振った2数をそれぞれ $a, b$ とすると、 $a$ と $b$ の倍数の差が1になるような数を探したくなります。つまり、

$ax - by = 1$

を満たす $x, y$ を求めればよいことになります。

この不定方程式は拡張ユークリッドの互除法に似ていて、 $ax + by = 1$ ならできることがわかっていました。ここで、 $a > 0$ かつ $b > 0$ なので、 $x \times y > 0$ なる解はありません。よって、 $x$ と $y$ の符号は異なることがわかります。したがって、それらの符号を反転させれば、差が $1$ の2数にすることができます。

参考 $2 \times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23\times 29\times 31\times 37\times 41\times 43 = 1.3082761e+16 > 1e15$

実装

template<typename T> 
map<T,int> factorize(T x){
    map<T,int> mp;
    for (T i = 2; i*i <= x; i++){
        while (x%i == 0) {
            x /= i;
            mp[i]++;
        }
        if (x == 1) break;
    }
    if (x != 1) mp[x]++;
    return mp;
}

ll power_pow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main() {
    ll N;
    cin >> N;
    auto vn = factorize(2*N);
    int M = vn.size();
    vector<pair<ll,int>> vp;
    for(auto p: vn)vp.push_back(p);
    if(N == 1){
        cout << 1 << endl;
        return 0;
    }
    ll ans = N-1;
    for(int i = 0; i < bit(M); i++){
        vector<pair<ll,int>> v2[2];
        rep(j,M)v2[(i>>j)&1].push_back(vp[j]);
        ll a = 1, b = 1;
        for(auto [val, sisu]: v2[0])a *= power_pow(val, sisu);
        for(auto [val, sisu]: v2[1])b *= power_pow(val, sisu);
        ll x, y;
        extGCD(a, b, x, y);
        if(x * y >= 0)continue;
        x *= -1;
        y *= -1;
        a *= abs(x);
        b *= abs(y);
        chmin(ans, min(a, b)));
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 178 ABC178 参加記

コンテスト参加記 AtCoder ABC MOD 包除原理数え上げ DP 45°回転マンハッタン距離構築

5完で水パフォでした。青パフォstreakが切れて悲しいですね。

jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 178での成績：864位
パフォーマンス：1597相当
レーティング：1412→1432 (+20) :)
Highestを更新しました！#AtCoder #ABC178 https://t.co/JlM3ZncqvH
— naga@精進 (@longeqe) 2020年9月14日

提出したコードへのリンク

A - Not
- 解説
- 実装
B - Product Max
- 解説
- 実装
C - Ubiquity
- 解説
- 実装
D - Redistribution
- 解説
- 実装
E - Dist Max
- 解説
- 実装
F - Contrast
- 解説
- 実装

A - Not

問題へのリンク

解説

1とのxorを取ると逆転します。

実装

int main() {
    int x;
    cin >> x;
    cout << x^1 << endl;
}

B - Product Max

問題へのリンク

解説

こういう問題最近よく見ます。大抵区間の端のみを見ればよいです。

実装

int main() {
    ll a, b;
    ll c, d;
    cin >> a >> b;
    cin >> c >> d;
    ll ans = -INFLL;
    chmax(ans, a * c);
    chmax(ans, a * d);
    chmax(ans, b * c);
    chmax(ans, b * d);
    if(a <= 0 && 0 <= b)chmax(ans, 0LL);
    if(c <= 0 && 0 <= d)chmax(ans, 0LL);
    cout << ans << endl;
}

C - Ubiquity

問題へのリンク

解説

dp[どこまで見たか][0が出たか][9が出たか]でdpします。

実装

mint dp[1000100][2][2];
int main() {
    int N;
    cin >> N;
    rep(i,N+1)rep(j,2)rep(k,2)dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    rep(i,N){
        rep(j,2)rep(k,2){
            for(int nxt = 0; nxt <= 9; nxt++){
                dp[i+1][j || nxt == 0][k || nxt == 9] += dp[i][j][k];
            }
        }
    }
    cout << dp[N][1][1] << endl;
}

D - Redistribution

問題へのリンク

解説

$\Theta(S^{3})$ のdpしか見えなくて雑に枝刈りしたら通りました。許してください。

実装

mint dp[2500][2500];
int main() {
    ll S;
    cin >> S;
    rep(i,2222)rep(j,2222)dp[i][j] = 0;
    dp[0][0] = 1;
    rep(i,2221)rep(j,S){
        if(dp[i][j].x == 0)continue;
        for(int add = 3; add + j <= S; add++){
            dp[i+1][add + j] += dp[i][j];
        }
    }
    mint ans = 0;
    rep(i,2222)ans += dp[i][S];
    cout << ans << endl;
}

E - Dist Max

問題へのリンク

解説

既出っぽいし典型っぽいので「マンハッタン距離最大」とかでググると色々ヒットします。マンハッタン距離なら45°回転は典型っぽいので、抑えておきたいところです。

実装

int main() {
    int N;
    cin >> N;
    vector<ll> v, w;
    rep(i,N){
        int x, y;
        cin >> x >> y;
        v.emplace_back(x-y);
        w.emplace_back(x+y);
    }
    sort(all(v));
    sort(all(w));
    ll maxx = 0;
    chmax(maxx, v.back() - v[0]);
    chmax(maxx, w.back() - w[0]);
    cout << maxx << endl;
}

F - Contrast

問題へのリンク

解説

ある数 $i$ が $A$ と $B$ に渡って $N$ 個以上あるとき、不可能で、それ以外は可能です。構築は難しいですが、 $B$ をreverseすると重なるのは一つだけなので、そこを雑に調整すると良さそうです。

実装

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    cin >> A >> B;
    map<int, int> mpa, mpb;
    rep(i,N){
        mpa[A[i]]++;
        mpb[B[i]]++;
    }
    for(int i = 1; i <= N; i++){
        ll cnta = mpa[i];
        ll cntb = mpb[i];
        if(cnta + cntb > N){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    reverse(all(B));
    int idx = 0;
    rep(i,N){
        if(A[i] == B[i]){
            while(B[idx] == B[i] || A[idx] == B[i]){
                idx++;
                idx %= N;
            }
            swap(B[i], B[idx]);
        }
    }
    rep(i,N){
        cout << B[i] << " ";
    }
    cout << endl;
}

AtCoder Library 環境構築（macOS & VSCode編）

AtCoder 環境構築

先日AC Libraryの導入が発表されましたが、皆様いかがお過ごしでしょうか。備忘録として私が環境構築で行ったことを記しておこうと思います。

注意

心配な方は公式ドキュメントに目を通してから環境構築を行ってください。

環境

macOS Catalina Version 10.15.6
Visual Studio Code version 1.48.2

ステップ 1.

AtCoder公式のアナウンスページAtCoder Library(ACL)からac-library.zipをダウンロードして適切な場所で解凍。

ステップ 2.

環境変数CPLUS_INCLUDE_PATHにac-libraryのpath(先ほど解凍したところ)を通す。

.bashrcや.zshrcなどに以下のように追加する。

export CPLUS_INCLUDE_PATH=/path/to/ac-library/

これでターミナルでinclude <atcoder/all>を追加した.cppファイルのコンパイルが通るようになります。

ステップ 3.

コンパイルは通るようになりましたが、エディタが認識できるようにはなっていません。私は普段からVisual Studio Codeを使っているので、その方法を記します。

setting.jsonに、以下のような項目を追加します。すると、VSCode内でもこのpathを探すようになるので、補完が効くようになります。

"C_Cpp.default.includePath": ["/path/to/ac-library/"],

いかがでしたか？

AtCoder Beginner Contest 177 ABC177 参加記

コンテスト参加記 AtCoder ABC ceil MOD グラフ UnionFInd DFS BFS 素因数分解高速素因数分解調和級数鳩の巣原理

5完2ペナで青パフォでした。初の青パフォstreak2で嬉しいです。

jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 177での成績：605位
パフォーマンス：1732相当
レーティング：1371→1412 (+41) :)
Highestを更新し、3 級になりました！#AtCoder #ABC177 https://t.co/KW2mCcgR3n
— naga@精進 (@longeqe) 2020年8月30日

A - Don't be late
- 解説
- 実装
B - Substring
- 解説
- 実装
C - Sum of product of pairs
- 解説
- 実装
D - Friends
- 解説
- 実装
E - Coprime
- 解説
- 実装
F - I hate Shortest Path Problem

A - Don't be late

問題へのリンク

解説

時間を計算して比較します。 $D$ が $S$ で割り切れない場合、切り捨てになってしまうので、切り上げを使って比較します。

実装

int main() {
    ll D, T, S;
    cin >> D >> T >> S;
    cout << ((D + S - 1) / S <= T ? "Yes" :"No") << endl;
}

B - Substring

問題へのリンク

解説

$\Theta(N^{2})$ で処理します。substr関数を使うとわかりやすいかもしれませんが、指定した長さが取れない場合に後ろをカットする仕様なので、気をつけましょう。これで1ペナはきました。

実装

int main() {

    string S, T;
    cin >> S >> T;
    int N = S.size();
    int M = T.size();
    ll ans = INFLL;
    for(int i = 0; i < N; i++){
        string tmp = S.substr(i, M);
        if(tmp.size() < M)continue;
        ll cnt = 0;
        rep(j,M)cnt += T[j] != tmp[j];
        chmin(ans, cnt);
    }
    cout << ans << endl;
}

C - Sum of product of pairs

問題へのリンク

解説

kyopro_friendsさんの方法で実装しました。組み $i, j$ を全て列挙したいとき、この表を思い浮かべると計算量が良い方法が思い浮かんだりします。

フェネック「C問題は ((ΣAi)^2 - Σ(Ai^2))/2 が答えだねー。この問題みたいに、「i<jの全ての組(i,j)について……」って問題で、「全ての組(i,j)について計算してからi=jの分を引いて2で割る」っていうのよく使うテクニックだから覚えておくといいよー」 pic.twitter.com/1stRIjuqj4
— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年8月29日

ちなみにここでもオーバーフローで1ペナはきました。本当に水色ですか？

実装

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N)cin >> A[i];
    ll sum = accumulate(all(A), 0LL);
    mint ans = 0;
    rep(i,N){
        ans += mint(A[i]) * mint(sum - A[i]);
    }
    cout << ans/2 << endl;
}

D - Friends

問題へのリンク

解説

最も人数の多い友達関係を全員違うグループに分けて、それ以下のグループはそこに詰めていけば達成でき、これが最小です。実装はUnionFindでもグラフにしてDFS, BFSで連結成分でもいいと思います。

実装

int main() {

    int N, M;
    cin >> N >> M;
    UnionFind T(N);
    rep(i,M){
        int a, b;
        cin >> a >> b;
        a--,b--;
        T.unite(a,b);
    }
    int ans = 0;
    rep(i,N)chmax(ans, T.size(i));
    cout << ans << endl;
}

E - Coprime

問題へのリンク

解説

高速素因数分解

高速素因数分解で殴りました。数の上限がある程度小さいとき、複数クエリに高速に答える手法です。説明はganariyaさんの記事がわかりやすいです。

https://t.co/CrqrsI3csh
— ganariya (@ganariya) 2020年8月29日

調和級数

AtCoder公式解説放送では調和級数を用いた方法が説明されていました。

www.youtube.com

鳩の巣原理

愚直な素因数分解を繰り返しても、ある素因数が二回現れるまでの更新は高々 $maxA$ 回であるので、それでも解けます。ちなみに愚直に毎回素因数分解を行って確認してもC++なら間に合うそうです。この前もそうでしたね。

実装

template<typename T>
vector<T> smallest_prime_factors(T n) {

    vector<T> spf(n + 1);
    for (int i = 0; i <= n; i++) spf[i] = i;


    for (T i = 2; i * i <= n; i++) {

        // 素数だったら
        if (spf[i] == i) {

            for (T j = i * i; j <= n; j += i) {

                // iを持つ整数かつまだ素数が決まっていないなら
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }

    return spf;
}

template<typename T>
map<T, int> factolization(T x, vector<T> &spf) {
    // vector<T> ret;
    map<T, int> mp;
    while (x != 1) {
        // ret.push_back(spf[x]);
        mp[spf[x]]++;
        x /= spf[x];
    }
    // sort(ret.begin(), ret.end());
    // return ret;
    return mp;
}
int main(){
    constexpr int MAX = 1000000;

    auto spf = smallest_prime_factors(MAX);

    int Q;
    cin >> Q;
    vector<int> v(MAX, 0);
    ll G = -1;
    while (Q--) {
        int x;
        cin >> x;
        if(G == -1)G = x;
        else{
            G = gcd(G, x);
        }
        auto result = factolization(x, spf);
        // for (auto z: result)cout << z << " ";
        // cout << endl;
        // print(result);
        for(auto p: result){
            v[p.first]++;
        }
    }
    bool ok = true;
    rep(i,MAX)if(v[i] >= 2)ok = false;
    if(ok){
        cout << "pairwise coprime" <<endl;
    }
    else if(G == 1){
        cout << "setwise coprime" << endl;
    }
    else{
        cout << "not coprime" << endl;
    }
    return 0;
}

F - I hate Shortest Path Problem

問題へのリンク

まだわかっていません。

AtCoder Beginner Contest 176 ABC176 参加記

コンテスト参加記 AtCoder ABC ダイクストラ法グリッド最短経路問題セグ木

D - Wizard in Maze
- 解説
- 実装
E - Bomber
- 解説
- 実装
  - 列の最大をとる
  - range max queryのセグ木
F - Brave CHAIN

50分5完で青パフォでした。そういえば競プロを始めてから2年が経っていました。

D - Wizard in Maze

問題へのリンク

解説

見た瞬間にグリッド上でグラフを構築してダイクストラしたくなります。言語によって実行時間が厳しかったりするようですが、C++なら間に合いました。ダイクストラは以下のようにライブラリにして持っておくと便利だと思います。

実装

二次元座標を一次元座標に縮める方法がポイントです。頻出です。

template<class T> class Dijkstra {
public:
    int N;
    T inf;
    vector<T> cost;
    vector<vector<pair<T, int>>> edge;
 
    Dijkstra(const int N, T inf) : N(N), inf(inf),cost(N), edge(N) {
    }
 
    void make_edge(int from, int to, T w) {
        edge[from].push_back({ w,to });
    }
 
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf;
 
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
 
        while (!pq.empty()) {
            T v = pq.top().first;
            int from = pq.top().second;
            pq.pop();
            for (auto u : edge[from]) {
                T w = v + u.first;
                int to = u.second;
                if (w < cost[to]) {
                    cost[to] = w;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
};

ll H, W;
int f(int x, int y){
    return x * W + y;
}
bool IsIn(int x,int y){
    return 0<=x&&x<H&&0<=y&&y<W;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    cin >> H >> W;
    ll sx, sy;
    ll gx, gy;
    cin >> sx >> sy;
    cin >> gx >> gy;
    sx--;sy--;
    gx--;gy--;
    vector<string> S(H);
    rep(i,H)cin >> S[i];
    Dijkstra<ll> d(H*W, INFLL);
    rep(i,H)rep(j,W){
        if(S[i][j] == '#')continue;
        rep(k,4){
            int ni = i + dx[k];
            int nj = j + dy[k];
            if(not IsIn(ni,nj))continue;
            if(S[ni][nj] == '#')continue;
            d.make_edge(f(i,j), f(ni,nj), 0);
        }
        for(int p = -2; p <= 2; p++){
            for(int q = -2; q <= 2; q++){
                int ni = i + p;
                int nj = j + q;
                if(not IsIn(ni,nj))continue;
                if(S[ni][nj] == '#')continue;
                d.make_edge(f(i,j), f(ni,nj), 1);
            }
        }
    }
    d.solve(f(sx, sy));
    if(d.cost[f(gx,gy)] == INFLL){
        cout << -1 << endl;
    }
    else{
        cout << d.cost[f(gx,gy)] << endl;
    }

}

E - Bomber

問題へのリンク

解説

行を固定すると、列はどこを選べば良いでしょう？実は、列の中で最も多いところだけを確認するので良いです。

実装

列の最大をとる

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll H, W, M;
    cin >> H >> W >> M;
    vec<int> cntx(H,0), cnty(W,0);
    map<l_l, int> mp;
    vector<l_l> cnt_x;
    vector<l_l> cnt_y(1, {-1,-1});
    rep(i,M){
        int h, w;
        cin >> h >> w;
        h--; w--;
        cntx[h]++;
        cnty[w]++;
        mp[{h,w}]++;
    }
    rep(i,H)cnt_x.emplace_back(cntx[i], i);
    rep(j,W)cnt_y.emplace_back(cnty[j], j);
    sort(all(cnt_x), greater<>());
    sort(all(cnt_y));
    vector<int> kouho_y;
    for(int i = W; i >= 0; i--){
        kouho_y.emplace_back(cnt_y[i].second);
        if(cnt_y[i].first != cnt_y[i-1].first)break;
    }
    ll maxxy = cnt_y.back().first;
    ll ans = 0;
    rep(i,H){
        int idx = cnt_x[i].second;
        ll tmp = cnt_x[i].first;
        if(ans >= tmp + maxxy)break;
        for(auto y: kouho_y){
            chmax(ans, tmp + maxxy - (mp[{idx,y}] > 0));
            if(ans >= tmp + maxxy)break;
        }
    }
    cout << ans << endl;
}

range max queryのセグ木

/*
@title 抽象化セグ木
@category データ構造
*/
template<typename T>
class SegTree {
  public:
    int N;//葉の数
    vector<T> data;//配列
    T unit;//単位元
    function<T(T,T)> op;//区間クエリで使う処理
    function<T(T,T)> update;//点更新で使う処理
    T _query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l)return unit;
        if(a <= l && r <= b){
            return data[k];
        }
        else{
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); //左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); //左の子
            return op(c1, c2);
        }
    }
    //コンストラクター
    //_N: 必要サイズ, _unit: 初期値かつ単位元, _op: クエリ関数, _update: 更新関数
    SegTree(int _N, T _unit, function<T(T, T)> _op, function<T(T, T)> _update) 
        :unit(_unit), op(_op), update(_update){
        N = 1;
        while(N < _N)N *= 2;
        data.assign(2 * N - 1, unit);
    }
    //i(0-indexed)の値にupdate関数を適用
    void change(int i, T x){
        i += N - 1;
        data[i] = update(data[i], x);
        while(i > 0){
            i = (i - 1) / 2;
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }
    //[a, b)の区間クエリの実行
    T query(int a, int b){
        return _query(a, b, 0, 0, N);
    }
    //添字でアクセス
    T operator[](int i) {
        return data[i + N - 1];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll H, W, M;
    cin >> H >> W >> M;
    auto f = [&](long long a, long long b){
        return max(a, b);
    };
    auto g = [&](long long a, long long b){
        return a + b;
    };
    SegTree<long long> Tree(W,0,f,g);
    vvec<int> v(H);
    rep(i,M){
        int h, w;
        cin >> h >> w;
        h--;w--;
        v[h].emplace_back(w);
        Tree.change(w, 1);
    }
    ll ans = 0;
    rep(i,H){
        for(auto j: v[i])Tree.change(j, -1);
        ll tmp = v[i].size() + Tree.query(0,W);
        chmax(ans, tmp);
        for(auto j: v[i])Tree.change(j, 1);
    }
    cout << ans << endl;
}

F - Brave CHAIN

問題へのリンク

DPっぽかったですがまた解法を確認していません。