AtCoder Beginner Contest 286 に参加しました＆反省会

AtCoder Beginner Contest 286 の振り返り

• B問題のみ解けた
• A問題：添字P-Q、R-Sの要素だけを入れ替える方法がわからず、個別にベクターに格納するなど無駄なことをした
• B問題：文字列のnaをnyに置き換える
• C問題：当初入力値の回文を作るのだと勘違いしていた。勘違いに気づいた後も解法が分からず
• D問題：動的計画法で解ける問題だが、実装できなかった

A問題

atcoder.jp

考えたこと

• S−R=Q−Pである事から交換される要素以外の添字は変わらない

実装例 添字を入れ替える箇所のみ

1 for文とif文の組み合わせ

 for(int i=1;i<=n;i++){
        if((p<=i)&&(i<=q))cout<<a[i+r-p];
        else if((r<=i)&&(i<=s))cout<<a[i+p-r];
        else cout<<a[i];
        if(i<n)cout<<" ";
        else cout<<endl; 
    }

2 swap関数の利用

for(int i=p;i<=q;i++)swap(a[i-1],a[r-p+i-1]);

• std::swap

// 値版
  {
    int a = 1;
    int b = 2;

    using std::swap;
    swap(a, b);

    std::cout << a << ", " << b << std::endl; // 2, 1
  }

https://cpprefjp.github.io/reference/utility/swap.html

B問題

atcoder.jp

考えたこと

• naを見つける
• 見つけたnaのnとaの間にyを挿入する

実装例

 for(int i = 0; i < (int)s.size() - 1; i++) {
        if(s.substr(i, 2) == "na") {
            s.insert(s.begin() + i + 1, 'y');
            fin = 0; //whileループから抜けるフラグ
            break;
        }
    }

• .insert()を一回行うのにかかる計算量はO(N)なので全体でO(N²)

• 文字を置き換える関数regex_replace

regex_replace(s, regex("na"), "nya")

指定された文字列の中で、正規表現にマッチする部分を指定した文字列に置換する。

C問題

atcoder.jp

解説から

最初に A 円払う操作を何回かしてから B 円払う操作を何回か行うというように操作の順序を決め打っていいというものがあります。また、 A 円払う操作の回数は N 回未満であるということも重要です。（ N 回行うと元に戻るので）
この考察を用いると、制約が小さいことから A 円払う操作の回数を全探索できます。 B 円払う操作の必要回数の最小値は、回文になるために同じ文字でないといけない組のうち、二つの文字が現時点で一致していないものの個数として求まります。

実装例

 s += s;
    long long ans = 1ll << 60;
    for(int i = 0; i < n; i++) {
        long long tmp = a * i;
        for(int j = 0; j < n / 2; j++) {
            int l = i + j;
            int r = i + n - 1 - j;
            if(s[l] != s[r]) tmp += b;
        }
        ans = min(ans, tmp);
    }