PCK2024予選雑解説(7,8以外)

1問目　もらったキャンディ

4036 < PCK Prelim < Challenges | Aizu Online Judge

C-10を出力してください

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int c;
    cin>>c;
    cout<<c-10<<endl;
}

2問目　神輿(みこし)の担ぎ手

4037 < PCK Prelim < Challenges | Aizu Online Judge
w/cの切り上げを計算して、それがN以下かどうか。

a/bの切り上げは(a+b-1)/bで計算できる。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,c,w;
    cin>>n>>c>>w;
    int x=(w+c-1)/c;
    if(x>n)cout<<"No"<<endl;
    else{
        cout<<"Yes"<<endl;
        cout<<x<<endl;
    }
}

3問目　ラッキーナンバー

PCK Prelim < Challenges | Aizu Online Judge

問題文のとおりに数えるだけです。
nは文字列として受け取ると楽です。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int d;
    string n;
    cin>>d>>n;
    int cnt=0;
    for(char c:n){
        cnt+=(c-'0'==d);
    }
    cout<<cnt<<endl;
}

4問目　魔法のポケット

4039 < PCK Prelim < Challenges | Aizu Online Judge
このあたりから難しくなってきます。

もし、C,Dが最小の2でも40回くらい叩けばビスケットの数は10^12を超えます。T<=10^11なので右のポケット、左のポケットを叩く回数は、大体40以下まで考えれば良い。

全探索。オーバーフローに気をつけます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll A,B,C,D,T;
    cin>>A>>B>>C>>D>>T;
    int ans = 1e9;
    ll x = A;
    rep(a,40){
        ll y = B;
        rep(b,40){
            if(x+y==T) ans = min(ans, a+b);    
            y*=D;
            if(y>T) break;
        }
        x*=C;
        if(x>T) break;
    }
    if(ans==1e9) cout<<"No"<<endl;
    else {
        cout<<"Yes"<<endl;
        cout<<ans<<endl;
    }
}

5問目　データセンター

404 Error | Aizu Online Judge

自由に移動できるので最初のファイルの位置は考える必要はありません。大事なのはファイルの総数です。
できるだけ多くのサーバーを余らせるには、たくさんのファイルが持てるサーバーに優先的に押し付けるべき。

貪欲法

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,m;
    cin>>n>>m;
    vector<int> c(n),a(n);
    rep(i,n){
        cin>>c[i]>>a[i];
    }
    int sum = 0;
    rep(i,n) sum+=a[i];
    sort(c.begin(),c.end(),greater<int>());
    int use = 0;
    rep(i,n){
        if(sum>0){
            sum -= c[i];
            use++;
        }
    }
    if(n-use>=m) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

6問目　湖の調査

Aizu Online Judge

.の連結成分の個数を数える問題です。
周りに隣接している.の集合をカウントしてはいけないので、予め取り除いておきます。

unionfindでも良いですが、本番ではライブラリぺた～できないのでdfsでやると楽です。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int h,w;
    cin>>h>>w;
    vector<string> s(h);
    rep(i,h) cin>>s[i];

    vector<vector<int>> used(h,vector<int>(w,0));
    auto dfs = [&](auto dfs, int y, int x) -> void {
        if(y<0 || h<=y || x<0 || w<=x) return;
        if(s[y][x]=='#') return;
        if(used[y][x]) return;
        used[y][x]=1;
        vector<int> dd = {0,1,0,-1,0};
        rep(i,4){
            dfs(dfs, y+dd[i], x+dd[i+1]);
        }
    };

    rep(i,h){
        dfs(dfs, i, 0);
        dfs(dfs, i, w-1);
    }
    rep(j,w){
        dfs(dfs, 0, j);
        dfs(dfs, h-1, j);
    }

    int cnt = 0;
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#') continue;
            if(used[i][j]) continue;
            dfs(dfs, i, j);
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

9問目　壁のリフォーム

404 Error | Aizu Online Judge

「隣り合う列の高さが同じ」は考えにくい。
図を書いてみるとわかるが、すべてのiについてh[i]-d[i]の値を一致させることと同じ。

「差の総和を最小化するときは中央値を使う」という典型がある。
C - Linear Approximation

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin>>n;
    vector<ll> h(n),d(n);
    rep(i,n)cin>>h[i];
    rep(i,n)cin>>d[i];

    vector<ll> sa(n);
    rep(i,n) sa[i] = h[i]-d[i];

    sort(sa.begin(),sa.end());
    ll md = sa[n/2];
    
    ll cnt = 0;
    rep(i,n) cnt += abs(sa[i]-md);
    cout<<cnt<<endl;
}

10問目　宇宙戦艦イヅア

404 Error | Aizu Online Judge
各クエリの入力がめっちゃおおいですが、各操作の最大しか考慮しなくて良いです。

直感的には
dp[i][j]i番目のクエリまでみて、現在のポンプの強さがjのときのスコアの最大値
というdpをやりたいですが、ポンプの強さが超大きいので間に合いません。
N<=2000であることに注目します。

クエリ1(ポンプ増強)は、以降クエリ2を行う回数が分かれば全体のスコアに影響する量が求まるのでその時に即加算すれば、現在のポンプの強さをdpに持たせなくて良い。
dp[i][j]= i個目のクエリまで見て、以降にクエリ2ã‚’j回行うと決めたときのスコアの最大値

答えはdp[N][0]

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin>>N;
    vector<vector<ll>> dp(N+1,vector<ll>(N+1,-1e18));
    rep(i,N+1)dp[0][i] = 0;
    rep(i,N){
        int L;
        cin>>L;
        int l1 = 0;
        int l2 = 0;
        rep(j,L){
            int t,a;
            cin>>t>>a;
            if(t==1) l1 = max(l1, a);
            else l2 = max(l2, a);
        }
        rep(j,N+1){
            if(l1>0 && j>0) dp[i+1][j-1] = max(dp[i+1][j-1], dp[i][j]+l1);
            if(l2>0) dp[i+1][j] = max(dp[i+1][j], dp[i][j]+l2*j);
        }
    }
    cout<<dp[N][0]<<endl;
}

11問目　デイリーミッション

Aizu Online Judge

指定された順で部屋を順番に訪れていく。敵の部屋に訪れる回数を最小化したうえでの、部屋の移動回数を最小値を求めてください、
各小鬼の場所への移動について、始点と終点は決まっているので、独立に考えて最後に足し合わせれば良いです。
子鬼の数が超多くて、部屋の数は300と小さめ。

ワーシャルフロイドです。

ただし普通のワーシャルフロイドとは少しだけ違うところがあって、

• 辺ではなく頂点に重みがついている。
  • これはその頂点へ向かっている辺に重みがあると考えて良いです。
• 最小化したい値が2つある。
  • 普通にpairで持てばいいです。
  • 毒の部屋を最小化したうえで移動回数を最小化したいので、pair<毒部屋訪数, 移動回数>の順で持たせる
    • もしくは、毒部屋へ訪れると1e9ペナルティ、移動すると1ペナルティとして、mod1e9を出力しても良い。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N,M;
    cin>>N>>M;
    vector<vector<ll>> G(N,vector<ll>(N,1e18));
    rep(i,N) G[i][i]=0;
    rep(i,M){
        int u,v;
        cin>>u>>v;
        u--;v--;
        G[u][v]=1;
        G[v][u]=1;
    }
    int K;
    cin>>K;
    vector<int> a(K);
    rep(i,K) cin>>a[i],a[i]--;

    int Q;
    cin>>Q;
    rep(i,Q){
        int b;
        cin>>b;
        b--;
        rep(j,N){
            G[j][b]+=1e9;
        }
    }
    rep(k,N){
        rep(i,N){
            rep(j,N){
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
            }
        }
    }
    ll ans = 0;
    int mae = 0;
    rep(i,K){
        ans += G[mae][a[i]];
        mae=a[i];
    }
    cout<<ans%(int)1e9<<endl;
    
}

12問目　ログインボーナス

404 Error | Aizu Online Judge
遅延セグ木とは言っていますが、計算がかなり複雑。

g(l,i) = Ai*Si + Bi*f(l,i)

Ai*Siはやるだけ。
Bi*f(l,i)が面倒です。
f(l,i)は、iより前に1が何個連続してるか。

これを更新するにはセグ木に、

• その区間の左端から何個1が連続してるか
• その区間の右端から何個1が連続してるか

を持たせればいいです。

説明難しいので詳しくはコード内のコメントに書きます。

反転クエリで0と1が入れ替わる場合もあるので、上記の0バージョンも保持しておきます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

// aojではACLが使えません。
#include<atcoder/lazysegtree>
using namespace atcoder;


// Bの累積和配列
vector<ll> bsum;

struct S{
    ll A; //Aの総和
    ll AS; //A*Sの総和
    ll Bf1; // B*f(l,i)の総和
    ll Bf0; // B*f0(l,i)の総和 (f0はfの0連続バージョン)
    ll l1; // 左端から1が何個連続しているか
    ll r1; // 右端から1が何個連続しているか
    ll l0; // 左端から0が何個連続しているか
    ll r0; // 右端から0が何個連続しているか
    ll sz; // 区間の幅
    ll i; //区間の左端の添字
};
S op(S a, S b){
    
    S s;

    // 普通に足す
    s.A = a.A+b.A;
    s.AS = a.AS+b.AS;
    
    // 左から1が何個続くかはaのl1を参照すればいい。(遅延セグ木のライブラリの内部でaが左、bが右に揃えてくれてます)
    s.l1 = a.l1;


    // ただし、a.l1がa.szと同じ場合、つまりすべての要素が1の場合は、b.l1も加えます。(l1は左から何個1が連続してるかなので)
    if(a.l1==a.sz){
        s.l1 += b.l1;
    }
    // ...
    s.l0 = a.l0;
    if(a.l0==a.sz){
        s.l0 += b.l0;
    }
    // ...
    s.r1 = b.r1;
    if(b.r1==b.sz){
        s.r1 += a.r1;
    }
    // ...
    s.r0 = b.r0;
    if(b.r0==b.sz){
        s.r0 += a.r0;
    }
    

    // 一旦普通に足す。
    s.Bf1 = a.Bf1+b.Bf1;
    // bの左から連続している1のみ、f(i,l)の値が、aの右端に連続している1の分だけ、増えます。
    s.Bf1 += (bsum[b.i+b.l1]-bsum[b.i])*a.r1;

    // ...
    s.Bf0 = a.Bf0+b.Bf0;
    s.Bf0 += (bsum[b.i+b.l0]-bsum[b.i])*a.r0;
    

    // 区間の左端の添字なので小さい方
    s.i = a.i;
    // 区間の幅
    s.sz = a.sz+b.sz;

    return s;
}
S e(){
    return S{0,0,0,0,0,0,0,0,0,0};
}
using F = ll;
S mapping(F f, S a){
    S s=a;
    //奇数の場合のみ反転が行われる
    if(f==1){
        // Sは0か1なので、反転はAの総和-A*Sの総和で可能
        s.AS = a.A-a.AS;

        // 入れ替える
        swap(s.Bf0,s.Bf1);
        // 入れ替える2
        swap(s.l0,s.l1);
        // 入れ替える3
        swap(s.r0,s.r1);
    }
    return s;
}
F composition(F f, F g){
    return (f+g)%2;
}
F id(){
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,q;
    cin>>n>>q;
    vector<ll> a(n),b(n),s(n);
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];
    rep(i,n)cin>>s[i];

    bsum.assign(n+1,0);
    rep(i,n) bsum[i+1] = bsum[i]+b[i];

    vector<S> init(n);
    rep(i,n){
        init[i] = S{a[i],a[i]*s[i],b[i]*s[i],b[i]*(1-s[i]),s[i],s[i],1-s[i],1-s[i],1,i};
    }

    lazy_segtree<S,op,e,F,mapping,composition,id> seg(init);

    rep(qi,q){
        int c,l,r;
        cin>>c>>l>>r;
        l--;
        if(c==1){
            seg.apply(l,r,1);
        }
        else{
            S res = seg.prod(l,r);
            cout << res.AS+res.Bf1 << endl;
        }
    }
}

H - Counting 1's
F - Vacation Query
これとか解いたことないと相当きつい。