ABC291 解法の要点と感想(AからD問題まで)

はじめに

A,B,Cの3完で16:40+0ペナでした。
コンテスト後にDも解いたので、それについてもまとめておきます。
ABC291-コンテスト成績証

なお、記事内で登場するコードには独自のテンプレートやマクロが含まれている場合があります。
それらの詳細については、お手数ですがこちらの記事をご確認ください。

A問題

問題文:

Diff: 8

string型で入力を受け取り、forなどのループ制御で手前の文字から順に英大文字か否か判定するとよいです。
与えられた文字が英大文字かどうかを判定する方法はいくつかありますが、ここではchar型同士で大小比較できることを利用しています。

int main() {
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] >= 'A' && s[i] <= 'Z'){
            cout << i+1 << el;
        }
    }
}

提出コード: https://atcoder.jp/contests/abc291/submissions/39225334

B問題

問題文:

Diff: 32

まず評点の配列をソートしておきます。
問題文には最大の要素、最小の要素を「取り除く」とありますが、実際にvector型の配列から要素を取り除くのは面倒です。(vector::eraseを使うと実現できますが、計算時間量が重いことや要素の無効化など懸念すべき事項があるので、あまり推奨しません¹)
ではどうするかというと、ソートしたことによって、先頭からN個の要素と末尾からN個の要素には興味がなくなるため、それらにはアクセスしないような条件でfor文を書きます。
for文で範囲内の評点の和を取り、和を3*nで除算しましょう。(N-(2*n)と書いていますが、3*nで問題ないです)
答えは小数点型でないといけないので、double型で集計するようにしましょう。なお、setprecision(11)は不要です。²

int main() {
    int n;
    cin >> n;
    int N = 5*n;
    vector<int> x(N);
    rep(i,0,N) cin >> x[i];
 
    double ans = 0;
    sort(all(x));
    //for(int i = n; i < N-n; i++){ と同義です
    rep(i,n,N-n){
        ans += (double)x[i];
    }
    cout << setprecision(11) << ans / (N - (2*n)) << el;
}

提出コード: https://atcoder.jp/contests/abc291/submissions/39233754

C問題

問題文:

Diff: 188

既に訪れたことのあるものの記録といえば、std::setですね。今回は、x,y座標のペアで記録できるよう、set< pair<int,int> >で宣言するとよいです。
あとは現在地を表すpair<int,int>型変数を用意すれば実際にシミュレーションするだけで解けます。
始点となる{0,0}の座標をstd::setに予め記録するのを忘れないようにしましょう。

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
 
    set<pii> se;
    se.insert({0,0});
    pii pos = {0,0};
 
    rep(i,0,n){
        if(s[i] == 'R') pos.first++;
        if(s[i] == 'L') pos.first--;
        if(s[i] == 'U') pos.second++;
        if(s[i] == 'D') pos.second--;
        
        if(se.count(pos)){
            YES;
            return 0;
        }
        se.insert(pos);
    }
    NO;
}

提出コード: https://atcoder.jp/contests/abc291/submissions/39241209

D問題

問題文:

Diff: 720

DPを適用するとうまくいく問題です。「D問題のDはDPのD」といわれるほどなので、D問題あたりであまり解法の方針が立たなければDPをまず疑う方がいいです。³

条件を満たすような裏返すカードの選び方は何通りあるかを、部分和問題のように小さいケースから考えていくイメージです。dp[選んだ枚数][表or裏]という形ですすめましょう。
次のカードの表or裏と今のカードの値が等しくなければ通り数を加算する、という形で遷移させるとよいです。

998244353で割った余りを求める必要があるので、遷移の際に%998244353を忘れないようにしましょう。なお自分はACLのmodintを使用することで%演算を省略しています。その場合、最後の.val()同士で加算する際に%998244353が必要なので、付け忘れに注意しましょう。⁴

typedef modint998244353 mint;
//----------------キリトリ------------------------------------------------------
int main() {
    int n;
    cin >> n;
    vector<int> a(n),b(n);
    rep(i,0,n) cin >> a[i] >> b[i];
 
    vector dp(n,vector<mint>(2));
    dp[0][0] = 1, dp[0][1] = 1;
    rep(i,0,n-1){
        // ここの ^ は != と同義です
        if(a[i] ^ a[i+1]) dp[i+1][0] += dp[i][0];
        if(a[i] ^ b[i+1]) dp[i+1][1] += dp[i][0];
        if(b[i] ^ a[i+1]) dp[i+1][0] += dp[i][1];
        if(b[i] ^ b[i+1]) dp[i+1][1] += dp[i][1];
    }
    cout << (dp[n-1][0].val() + dp[n-1][1].val()) % 998244353 << el;
}

提出コード: https://atcoder.jp/contests/abc291/submissions/39275777

感想

この回は直前まで寝落ちしていたこともあり、全然頭が回っていませんでした。B問題は実装するまでに時間かかりすぎだし、C問題もstd::setで解けると気づかずにstd::stackを使うのか?と迷走していました。コンテスト直前まで寝ているとひどい目に遭うので、おすすめしません。
D問題も結構DPとしては易しいほうだと思うのですが、遷移を掴めませんでした……DPっぽいなぁと思いながら見ても遷移が浮かんでこなかったのは、全く精進不足でした。悔しかったので今はDPの復習に力を入れています。
E問題がトポロジカルソートで解けそうなのもコンテスト中に見えたのですが、結局解けませんでした。今でも「Aを一意に特定する」操作がわからず解けていません。くやしいね。
逆にここまで散々な成績ながら落茶はしなかったので、助かった……と思った回でした。普通にレート -15してますけど。

ついでですが、ABC解説記事を初めて書いたので、レイアウトからそれとなく考える必要があり疲れました。これからはそのテンプレに当てはめながら書けばいいので楽なのですが、これでいいのかなぁと思っています。ここが見づらい！ここもっと詳しく書いて！等あれば教えてください。

1. なお今回の問題は制約が小さいので、実際に取り除いても計算時間は十分高速です。 ↩

2. 小数点型を使う問題では不安でつい付けてしまう癖があります。 ↩

3. DPだと思っても漸化式を立てるのが難しいものもよくありますが…… ↩

4. modint::val は unsigned int型を返すため。ここ罠ですよね。 ↩