ABC204 解説 - Motsu_xe 競プロのhogeやfuga

AtCoder Beginner Contest 204 の解説記事です。私は2100点(45:41)30位でした。*1

A - Rock-paper-scissors

思考

3人じゃんけんでは、全員バラバラか、全員同じ手を出せばあいこになります。もしアラフェネの出した手が同じなら、サーバルも同じ手、アラフェネが別の手を出していれば、サーバルは残りの1手を出せば良いです。バラバラなら、3からアラフェネの手の合計を引く(xorとかでもいいです)などで簡単に実装できますが、どうやってもいいです。

実装例

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

int main(){
    int x, y;
    cin >> x >> y;
    if(x==y) cout << x << endl;
    else cout << 3-x-y << endl;
}

コンテスト中のACコード

B - Nuts

思考

愚直にシミュレーションするだけで簡単に解けます。実装例では配列で受け取っていますが、その必要すらありません。

実装例

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    ll ans{};
    for(auto&i:a){
        cin >> i;
        ans += max(i-10, 0);
    }
    cout << ans << endl;
}

コンテスト中のACコード

C - Tour

思考

スタート地点を固定して考えます。すると、DFSなりBFSなりで、到達可能な点を全列挙することで $O(M)$ で解くことができます。よってスタート地点を全て考えると $O(NM)$ で解くことができ、十分間に合います。

実装例

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

int main(){
    int n, m;
    cin >> n >> m;
    auto e = vector(n, vector<int>());
    for(int i{},a,b;i<(m);++i){
        cin >> a >> b;
        --a, --b;
        e[a].push_back(b);
    }
    ll ans{};
    for(int s{};s<(n);++s){
        vector<bool> vis(n);
        vis[s] = true;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            ++ans;
            int i = q.front();q.pop();
            for(auto&j:e[i]) if(!vis[j]){
                vis[j] = true;
                q.push(j);
            }
        }
    }
    cout << ans << endl;
}

コンテスト中のACコード

D - Cooking

思考

片方のオーブンを使用する料理の集合を $S$ とすると、料理を作るのにかかる時間は $\max(\sum_{i\in S}T_i, \sum_{i\notin S}T_i)$ となります。これは $ST = \sum_{i=1}^N T_i$ とすれば、 $\max(\sum_{i\in S}T_i, ST - \sum_{i\in S}T_i)$ とかけます。よって、料理の部分集合の合計調理時間として表される時間を全て求めることができれば、十分です。これは一般的な部分和問題で、簡単なDPで実装できます。std::bitsetを使用すると、実装量と実行時間を共に抑えられます。

実装例

#include<bits/stdc++.h>
using namespace std;
bool chmin(int&x,int y){if(x>y){x=y;return true;}return false;}

int main(){
    int n;
    cin >> n;
    vector<int> t(n);
    int s{};
    bitset<100001> v;
    v[0] = 1;
    for(auto&i:t){
        cin >> i, s+=i;
        v |= (v << i);
    }
    int ans = INT_MAX;
    for(int i{};i<=s;++i) if(v[i]){
        chmin(ans, max(i, s-i));
    }
    cout << ans << endl;
}

コンテスト中のACコード

E - Rush Hour 2

思考

辺の長さが状況によって異なる最短経路問題ですが、このような場合でも到達時点での最短な行き方をするようなダイクストラ法が回ることが知られています(類題(ネタバレ注意))。ある辺を辿るときに、最速な辿り方を考えます。結論から言うと $\frac{D}{t+1}-\frac{D}{t+2}\geq1$ が成立している間は待つのがよく、そうでない時は直ぐに渡るのが良いです。これは $\frac{D}{t+1}-\frac{D}{t+2}\geq1$ が成立している時は、1秒待てば、辺が1以上縮み、そうでない時は、辺が高々1しか縮まないことから言えます。よってこれに基づいてダイクストラ法を回せば良いです。

待つ待たないの境界時刻は、2次方程式を解けば十分高速に求められますが、誤差が怖いので、2次方程式を大雑把に解いた後、その付近で境界を適当に見つけるなどすると楽です(2分探索などでもOKです)。

実装例

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

int main(){
    int n, m;
    cin >> n >> m;
    struct edge{
        ll to, c, d;
    };
    auto e = vector(n, vector(0, edge({})));
    for(int i{},a,b,c,d;i<(m);++i){
        cin >>a >> b >> c >> d;
        --a, --b;
        e[a].push_back(edge({b, c, d}));
        e[b].push_back(edge({a, c, d}));
    }
    vector<ll> dis(n, 1ll << 60);
    dis[0] = 0;
    using P = pair<ll, int>;
    priority_queue<P, vector<P>, greater<>> pq;
    pq.emplace(0, 0);
    while(!pq.empty()){
        auto[D, u] = pq.top();pq.pop();
        if(u == n-1){
            cout << D << endl;
            return;
        }
        if(dis[u] < D) continue;
        for(auto[v, c, d]:e[u]){
            if(d < D or d < (D+1)*(D+2)){
                ll L = c + (d/(D+1));
                if(dis[v]>D+L){
                    dis[v] = D+L;
                    pq.emplace(D+L, v);
                }
            }
            else{
                ll tmp = floor(sqrt(d+0.25)-2.5);
                chmax(tmp, 0);
                while(d >= (tmp+1)*(tmp+2)) ++tmp;
                ll L = c + (d/(tmp+1));
                if(dis[v] > tmp + L){
                    dis[v] = tmp + L;
                    pq.emplace(tmp+L, v);
                }
            }
        }
    }
    cout << -1 << endl;
}

コンテスト中のACコード

F - Hanjo 2

思考

Hがやたら小さく、Wがやたら大きいので、列の状態を適当に持って、漸化式を行列累乗などで解く問題だとおおよそ予想が立ちます。持つべき状態ですが、

$\mathrm{DP}_{i,S}=(i$ 列目より左が全て埋まっており、 $i$ 列目の埋まっている集合が、 $S$ であるような敷き詰め方の通り数)

とすれば、この遷移は $\mathrm{DP}_{i,S}$ を $2^H$ 次元ベクトルとして見れば、行列で書くことができます。この行列に関しては、実際に全ての埋め方を調べてやることで簡単に求めることができます。

時間計算量は、行列の構成に $O(6^H)$ *2、行列累乗に $O(8^H\log W)$ となり、十分高速です。

実装例

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

int h;
ll w;
using mint = modint998244353;
template<class T> struct mat{}; //行列のライブラリ

void rec(int b, vector<vector<mint>>&m, int i,int x, int y){
    if(i == h){
        ++m[y][b];
    }
    else if((x>>i)&1) rec(b, m, i+1, x, y);
    else{
        rec(b, m, i+1, x, y);
        rec(b, m, i+1, x, y|(1<<i));
        if(i<h-1 and ((x>>(i+1))&1)==0) rec(b, m, i+1, x|(1<<(i+1)), y);
    }
}

int main(){
    cin >> h >> w;
    auto m = vector(1<<h, vector<mint>(1<<h));
    for(int b{};b<(1<<h);++b){
        rec(b, m, 0, b, 0);
    }
    mat<mint> mt(m);
    mt = pw(mt, w);
    cout << mt(0,0).val() << endl;
}