Zenn
🗂

ABC291 参加記録

2023/02/27に公開・約6,600字
AtCoder
#
競プロ
tech

ABC291 に参加しました。解説・感想を書いていきます~

A - camel Case

問題概要

英小文字・英大文字のみからなる文字列 S が与えられる。 S にはひとつだけ大文字が含まれてるので、大文字の含まれる場所を1-indexで教えてください。

  • S は英大文字・英小文字のみからなる
  • |S|\leq 100
  • S には、ひとつだけ英大文字が含まれる。

解説

C++にはisupprメソッドがあるので、それを使うといい。ASCIIコードとかでも判定できる。

実装例

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(isupper(s[i])){
            cout<<i+1<<'\n';
            return 0;
        }
    }
}

B - Trimmed Mean

問題概要

長さ 5N の数列 X=(X_1,X_2\dots,X_{5N}) が与えられる。
今から、 X のうち、大きいほう N 個,小さいほうから N 個の要素を除く。
操作を終えたとき、残った X の 3N 個の要素の平均値を求めてください。

  • 1\leq N\leq 100
  • 0\leq X_i\leq 100
  • 入力はすべて整数

解説

  1. X をソートする
  2. N+1 番目から 4N 番目までの和を求める
  3. 求めた和を 3N で割る

添え字をミスらないようにしよう。ソートは言語で用意されてるのを使うといい(無ければ...バブルソートとかしよう)

実装例

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> x(5*n);
    for(auto&xx:x){
        cin>>xx;
    }

    sort(x.begin(),x.end());
    int sum=0;
    for(int i=n;i<4*n;i++){
        sum+=x[i];
    }
    cout<<fixed<<setprecision(12);
    cout<<1.*sum/(3*n)<<'\n';
}

C - LRUD Instructions 2

問題概要

二次元平面に動点 P がある。 P は最初原点にある。
P は、今から N 回の移動を行います。これらの移動は、長さ N の文字列 S で表されます。
i 回目の移動は、次の通りです。

移動前の P が座標を (x,y) とする。

  • S_i がRならば (x+1,y) に移動する
  • S_i がLならば (x-1,y) に移動する
  • S_i がUならば (x,y+1) に移動する
  • S_i がDならば (x,y-1) に移動する

P は、 N 回の移動(始点,終点を含む)において同じ座標にいたことがありますか?

  • 1\leq N\leq 2\times10^5
  • N は整数
  • S はR,L,U,Dのみからなる長さ N の文字列

解説

要は 重複がない ということを確認しておけばいい。
訪れた座標を vector 等で管理しておけば、こういうのはソートで確認することができるので、全体 O(N\log N) で解ける。
また、set,mapとかで管理しても同じ計算量で解ける。

実装例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    string s;
    cin>>n>>s;

    vector<pair<int,int>> vec;  //訪れた座標を管理する

    int x=0,y=0;    //現在の座標

    vec.emplace_back(x,y);  //(0,0)を入れる

    for(int i=0;i<n;i++){
        if(s[i]=='R'){
            x++;
        }else if(s[i]=='L'){
            x--;
        }else if(s[i]=='U'){
            y++;
        }else{
            y--;
        }

        vec.emplace_back(x,y);
    }

    sort(vec.begin(),vec.end());    //ソートすると、「同じ要素」は必ず隣り合う
    for(int i=0;i<vec.size()-1;i++){
        //同じ要素を発見したら、Yes
        if(vec[i]==vec[i+1]){
            cout<<"Yes\n";
            return 0;
        }
    }
    //見つからなければNo
    cout<<"No\n";
}

D - Flip Cards

問題概要

N 枚のカードが並んでいる。
左から i 番目のカードの表には数字 A_i ,裏には数字 B_i が書かれています。
N 枚のうち、好きな枚数を選んで裏返すことを考えます。
次の条件を満たすような裏返し方は何通りありますか?
答えは非常に大きくなる可能性があるので、 \text{mod}998244353 で求めてください。

  • 選んだカードを全て裏返す。このとき、 i=1,2,\dots,N-1 について、
    • 左から i 番目のカードの表に書かれた数字と、左から i+1 番目のカードの表に書かれた数字は異なる。
  • 1\leq N\leq 2\times10^5
  • 1\leq A_i,B_i\leq 10^9
  • 入力はすべて整数

解説

こういうのは dp をする。
扱いやすくするために (A_i,B_i) ではなく、 (A_{i,1},A_{i,2}) とみなそう。こうすると、次のような dp にできる。

  • dp[i][j]= 左から 1,2,\dots,i 番目を決める方法であって、 i 番目に A_{i,j} を採用するような通り数 (\text{mod} 998244353)

この時、 dp[i][j] からの遷移は次の通り

  • 表を採用する: dp[i+1][1]\leftarrow dp[i+1][1]+dp[i][j] (A_{i,j}\neq A_{i+1,1})
  • 裏を採用する: dp[i+1][2]\leftarrow dp[i+1][2]+dp[i][j](A_{i,j}\neq A_{i+1,2})

すなわち、

  • j_2=1,2 に対して、 A_{i+1,j_2}\neq A_{i,j} ならば
    • dp[i+1][j_2]\leftarrow dp[i+1][j_2]+dp[i][j]

とすればいい。答えは dp[n][1]+dp[n][2] である。

実装例

#include<iostream>
#include<vector>
#include<atcoder/all>   //https://github.com/atcoder/ac-library
using namespace std;
using namespace atcoder;
using mint = modint998244353;   //自動でmodをとってくれる型
int main(){
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(2));
    for(auto&va:a){
        for(auto&v:va){
            cin>>v;
        }
    }

    vector<vector<mint>> dp(n,vector<mint>(2));

    dp[0][0]=1,dp[0][1]=1;  //最初は何をおいてもいい

    for(int i=0;i<n-1;i++)for(int j=0;j<2;j++)for(int j2=0;j2<2;j2++){
        if(a[i][j]!=a[i+1][j2]){
            dp[i+1][j2]+=dp[i][j];
        }
    }
    mint ans=dp[n-1][0]+dp[n-1][1];
    cout<<ans.val()<<'\n';  //出力
}

E - Find Permutation

問題文

(1,2,\dots,N) の並べ替え A=(A_1,A_2\dots,A_N) があります。
あなたは A を知りませんが、 A が次の条件を満たすことを知っています。

  • i=1,2,\dots,M について、 A_{X_i}<A_{Y_i}

A は一意に定まりますか?定まるならば実際に構築してください。

  • 1\leq N,M\leq 2\times10^5
  • 1\leq X_i,Y_i\leq N
  • 入力はすべて整数
  • 条件を満たすような A は存在する(一意とは限らない)

解説

言い換え

グラフの言葉に直そう。以下のような有向グラフ G を考える。

  • G の頂点数はちょうど N
  • 各 i について、頂点 X_i から頂点 Y_i に有向辺を張る

この時、次のような問題が解ければいい。

G をトポロジカルソートは一意に定まるか?一意ならばそれを求めよ

トポロジカルソート自体のことは他の記事を参照してください。

条件を満たす A が存在するので、 G はDAGで、トポロジカルソートをすることはできます。

一意性

G のトポロジカルソートを v=(v_1,v_2,\dots,v_n) とする。
この時、 v_i\to v_{i+1} の間に辺が無ければ v_i,v_{i+1} はswapしてもトポロジカルソートの定義を満たしていることがわかる。逆に、そのような i が存在しなければ v が一意に定まる。

構築

次のように A を構成できる。

  • 各 i について、 A_{v_i}=i
本当?

各 i について、以下のようにすると A_{X_i}<A_{Y_i} が成り立つことが分かる。

(s,t) を、 v_s=X_i,v_t=Y_i なる組とする。このとき、 A の構築方法から

A_{X_i}=A_{v_s}=s

A_{Y_i}=A_{v_t}=t

となる。
また、 G において X_i\to Y_i ,すなわち v_s\to v_t の辺が存在する。したがって、トポロジカルソートの定義から s<t である。
以上より、A_{X_i}=s<t=A_{Y_i},すなわち A_{X_i}<A_{Y_i}

したがって、上のように構築した A は、十分条件を満たしている。

まとめ

  1. G をトポロジカルソートする(結果を v とする)
  2. 全ての i=1,2,\dots,N-1 について、 v_i,v_{i+1} に辺があることを確認する。
  3. A_{v_i}=i として A を構築する

実装例

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<functional>
using namespace std;
using graph = vector<vector<int>>;

int main() {
    int n,m;
    cin>>n>>m;
    graph g(n);
    set<pair<int,int>> edges;  //辺
    
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        g[x].push_back(y);


        edges.emplace(x,y);
    }

    vector<int> ord;
    vector<bool> vis(n);
    function<void(int)> dfs=[&](int v)-> void {
        vis[v]=true;
        for(const auto&nv:g[v]){
            if(vis[nv]){
                continue;
            }

            dfs(nv);
        }
        ord.push_back(v);
    };


    for(int v=0;v<n;v++){
        if(vis[v]){
            continue;
        }
        dfs(v);
    }


    reverse(ord.begin(),ord.end());

    for(int i=0;i<ord.size()-1;i++){
        pair<int,int> e=make_pair(ord[i],ord[i+1]);
        if(edges.find(e)==edges.end()){
            cout<<"No\n";
            return 0;
        }
    }

    cout<<"Yes\n";
    


    vector<int> ans(n);
    for(int i=0;i<n;i++){
        ans[ord[i]]=i;
    }
    for(const auto&a:ans){
        cout<<a+1<<'\n';
    }
}

Discussion

ログインするとコメントできます