ABC 251 参加記

2022.05.15

競技プログラミング

90分6完(1ペナ)で382位、パフォーマンスは1869でした。EでDPの遷移がごちゃごちゃになってしまったりFがよくわからなかったりして大変でしたが、通せてよかったです。BでTLEしたときは困ってしまいましたが…

A Six Characters

問題

$1$以上$3$以下の文字数の文字列$S$が与えられます。$S$を繰り返して得られる文字列であり、長さが$6$のものを出力してください。

提出コード

int main(){

    string S; cin >> S;
    string T = "";
    while(T.length() != 6){
        T = T + S;
    }
    cout << T << endl;
}

B At Most 3(Judge ver.)

問題

$N$個の重りがあり、$i$番目の重りの重さは$A_i$です。$3$つ以下の異なる重りを自由に選んで、重さの和を$n$にできるとき、正整数$n$は良い整数と呼びます。$W$以下の正整数のうち、良い整数は何個ありますか？

$1 \leq N \leq 300$

$1 \leq W, A_i \leq 10^6$

考察

$A$に$0$を2つ付け加えた数列$A'$を考えます。すると、3つの異なるおもりを選んで～に言い換えることができるので、場合分けをしなくて済みます。面倒だったのでsetで管理したら余計な$\log$がつきTLEしてしまいました。気を付けましょう！！！

提出コード

int main(){

    ll N, W; cin >> N >> W;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    A.pb(0); A.pb(0);
    N += 2;

    set<ll> list;

    rep(i, N) for(int j = i+1; j < N; j++) for(int k = j + 1; k < N; k++){
        if(W >= A[i] + A[j] + A[k]) list.insert(A[i] + A[j] + A[k]);
    }
    cout << list.size() << endl;
	// for(auto l: list) cout << bitset<6>(l) << endl;	// D問題で使います
}

C Poem Online Judge

問題

$N$回の提出があり、早い方から$i$番目には文字列$S_i$が提出され得点$T_i$が得られました。$N$回の提出のうち、その提出よりも早い提出であり文字列が一致するものが存在しないような提出をオリジナルであると呼びます。オリジナルな提出のうち、最も得点が高いものを最優秀賞と呼びます。そのような提出が複数ある場合、最も提出が早いものを最優秀賞とします。最終週省は早い方から何番目の提出ですか？

$1 \leq N \leq 10^5$

$S_i$は長さが$1$以上$10$以下の英小文字からなる文字列

$0 \leq T_i \leq 10^9$

考察

オリジナルなもののみを抽出し、その中の得点最大を求め、1番目から順にみていき求めた得点最大と初めて一致するものを答えればよいです。オリジナルなもののみの抽出にはsetを使いました。

提出コード

int main(){

    ll N; cin >> N;
    set<string> Word;
    vpll Score;
    rep(i, N){
        string S; ll T; cin >> S >> T;
        if(Word.find(S) == Word.end()){
            Score.pb({T, i + 1});
        }
        Word.insert(S);
    }

    ll ma = 0;
    for(auto [t, id]: Score) chmax(ma, t);

    for(auto [t, id]: Score) if(ma == t){
        cout << id << endl; exit(0);
    }

}

D At Most 3 (Contestant ver.)

問題

整数$W$が与えられます。あなたは以下の条件をすべて満たすようにいくつかの重りを用意することにしました。

おもりの個数は$1$以上$300$個以下

おもりの重さは$10^6$以下の正整数

$1$以上$W$以下のすべての正整数は良い整数(良い整数の定義はB問題と同じ)

条件を満たすようなおもりの組を$1$つ出力してください。

考察

まず思い浮かぶのが$1, 2, 4, 8, 16, 32, … $としてみる方法です。試しに$1, 2, 4, 8, 16, 32$としたときに良い整数がどうなるか見てみましょう。これはJudge ver.を少しいじって良い整数をすべて出力するようにすればよいです(2進数で表示するようにしました詳しくはB問題のコードを見てください)。

立っているbitが$3$つ以下の正整数が良い整数となることがわかります。

ここで、$10^6 - 1$を$3$桁の$N$進数で表すことを考えます。これは$100$進数を使うとできます。　これより、$1, 2, \cdots, 99, 100, 200, \cdots, 9900, 10000, 20000, \cdots, 990000$の$297$個で$10^6$以下のすべての数が良い整数となります。

提出コードでは適当に実装したのでちょうど$300$個となりました。

提出コード

int main(){

    ll W; cin >> W;

    vll Ans;
    for(int i = 1; i <= 100; i++) Ans.pb(i);
    for(int i = 100; i <= 10000; i += 100) Ans.pb(i);
    for(int i = 10000; i <= 1000000; i += 10000) Ans.pb(i);

    cout << Ans.size() << endl;
    for(int i = 0; i < Ans.size(); i++){
        cout << Ans[i] << (i != Ans.size() - 1 ? ' ' : '\n');
    }

}

E Takahashi and Animals

問題

高橋くんと$N$匹の動物$1, 2, \cdots, N$がいます。以下の$N$種類の行動を好きな回数行います。

$A_1$円払い、動物$1$と$2$に餌をあげる。

$A_1$円払い、動物$1$と$2$に餌をあげる。

$\cdots$

$A_i$円払い、動物$i$と$i+1$に餌をあげる。

$\cdots$

$A_N$円払い、動物$N$と$1$に餌をあげる。

すべての動物にそれぞれ$1$回以上餌をあげるまでにかかる費用の合計として考えられる最小値を出力してください。

$2 \leq N \leq 3 \times 10 ^ 5$

$1 \leq A_i \leq 10^9$

考察

dp[i番目まで][i+1番目がの餌やりができている/できていない] ときのかかる費用の最小とするとよいです。$1$つ前からのみ遷移するので配列を持たずにかけます。$A_N$で$N$と$1$に餌やりができるので、これをするときとしない時の2通りDPを書くとよいです。

提出コード

int main(){

    ll N; cin >> N;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    ll ans = INF;

    {
        pll dp = {A[N-1], INF};
        for(int i = 0; i < N - 1 ; i++){
            dp = {min(dp.fi, dp.se) + A[i], dp.fi};
        }
        chmin(ans, min(dp.fi, dp.se));
    }

    {
        pll dp = {INF, 0};
        for(int i = 0; i < N; i++){
            dp = {min(dp.fi, dp.se) + A[i], dp.fi};
        }
        chmin(ans, min(dp.fi, dp.se));
    }

    cout << ans << '\n';

}

F Two Spanning Trees

問題

$N$頂点$M$辺の単純かつ連結な無向グラフ$G$が与えられます。$i = 1, 2, \cdots, M$について、$i$番目の辺は$u_i$と$v_i$を結ぶ無向辺$\{u_i, u_v\}$です。

下記の2つの条件を満たすような$G$の$2$つの全域木$T_1, T_2$を$1$組ずつ構築してください。

$T_1$は以下を満たす。

$T_1$を頂点$1$を根とする根付き木とみなしたとき、$G$の辺のうち$T_1$に含まれないすべての辺$\{u, v\}$について、$u$と$v$は$T_1$において祖先と子孫の関係にある。

$T_2$は以下を満たす。

$T_2$を頂点$1$を根とする根付き木とみなしたとき、$G$の辺のうち$T_1$に含まれないすべての辺$\{u, v\}$について、$u$と$v$は$T_2$において祖先と子孫の関係にない。

$2 \leq N \leq 2 \times 10 ^ 5$

$N-1 \leq M \leq \min\{2 \times 10 ^ 5, N(N-1)/2\}$

$1 \leq u_i, v_i \leq N$

考察

まず、$T_1$について考えます。これはDFS木で達成可能です。DFSでは行く先に未訪問の頂点がある限り進むということからわかります。

次に、$T_2$について考えます。これはBFS木で達成可能です。証明は公式解説を見ましょう。

提出コード

int main(){

    ll N, M; cin >> N >> M;
    vvll G(N);
    rep(i, M){
        ll u, v; cin >> u >> v; u--; v--;
        G[u].pb(v);
        G[v].pb(u);
    }

    {
        vvll T1(N);
        vb ch(N, false);
        auto dfs = [&](auto&& self, int now, int bef) -> void {

            for(auto e: G[now]) if(bef != e && !ch[e]){
                T1[now].pb(e);
                ch[e] = true;
                self(self, e, now);
            }

        };

        ch[0] = true;
        dfs(dfs, 0, -1);

        rep(i, N){
            for(auto e: T1[i]){
                cout << i + 1 << " " << e + 1 << "\n";
            }
        }
    }

    {
        vvll T2(N);
        vll dist(N, INF);
        dist[0] = 0;
        deque<ll> que; que.pb(0);
        while(!que.empty()) {
            int now = que.front(); que.pop_front();
            for(auto e: G[now]) if(dist[e] == INF){
                dist[e] = dist[now] + 1;
                T2[now].pb(e);
                que.pb(e);
            }
        }

        rep(i, N){
            for(auto e: T2[i]){
                cout << i + 1 << " " << e + 1 << "\n";
            }
        }
    }
}

考察がだいぶ雑になってしまいました。ごめんなさい…