競技プログラミング練習記 No.39【ABC122練習】

初回 -> はじめに

ABC122を解きました。
3完です！
D問題は解説をみて解きました。

問題	時間	アルゴリズム	実行時間
A	1min	-	4ms
B	2min	-	5ms
C	11min	累積和	34ms
D	-	動的計画法	6ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

C問題の実行時間が提出者の中で最速だったのでうれしい。
累積和には慣れてきました。

動的計画法はまだまだ苦手ですが、比較的わかるようになっています。この調子。
結果として違いましたが、包除原理を思いつけたので勉強の成果が出ているといえます。
次はその妥当性を評価できるようにします。

A - Double Helix

  char b;
  cin >> b;
  if (b == 'A') cout << 'T';
  if (b == 'T') cout << 'A';
  if (b == 'C') cout << 'G';
  if (b == 'G') cout << 'C';

A <=> T
C <=> G
の対応なので、全通り列挙しました。

B - ATCoder

  string s;
  cin >> s;
  int len = 0;
  int ans = 0;
  for(int i = 0; i < s.length(); ++i)
  {
    if (s[i] == 'A') len++;
    else if (s[i] == 'C') len++;
    else if (s[i] == 'G') len++;
    else if (s[i] == 'T') len++;
    else len = 0;

    ans = max(ans, len);
  }
  cout << ans;

最長部分列の長さを求める問題ですね。

C - GeT AC

  int n, q;
  string s;
  cin >> n >> q >> s;
  vector<int> cnt(n + 1, 0);
  for(int i = 1; i < n; ++i)
  {
    if (s[i - 1] == 'A' && s[i] == 'C') { cnt[i + 1]++; }
    cnt[i + 1] += cnt[i];
  }
  int l, r;
  for(int i = 0; i < q; ++i)
  {
    cin >> l >> r;
    cout << cnt[r] - cnt[l] << endl;
  }

解いた時点の、C++ (GCC 9.2.1)で提出した人の中で最速の実行時間でした。嬉しい。

文字列を走査して、"AC"の文字列があるとカウントを1増やし、累積和を求めます。
いもす法にも似ていますね。

累積和がわかると、数列内の任意の範囲の部分和が簡単に求まります。
つまり、プログラムのようにcnt[r] - cnt[l]で答えがわかります。

D - We Like AGC

こちらのライブラリを使いました。
https://github.com/atcoder-live/library/blob/master/mint.cpp

mint dp[101][4][4][4];
void solve()
{
  int n;
  cin >> n;
  dp[0][3][3][3] = 1;

  for(int len = 0; len <= n; ++len) {
    for(int i1 = 0; i1 < 4; ++i1) {
      for(int i2 = 0; i2 < 4; ++i2) {
        for(int i3 = 0; i3 < 4; ++i3) {
          if (dp[len][i1][i2][i3].x == 0) continue;

          for(int c = 0; c < 4; ++c)
          { // cut
            if (c == 2 && i1 == 1 && i2 == 0) continue; // AGC
            if (c == 1 && i1 == 2 && i2 == 0) continue; // ACG
            if (c == 2 && i1 == 0 && i2 == 1) continue; // GAC
            if (c == 2 && i2 == 1 && i3 == 0) continue; // AG C
            if (c == 2 && i1 == 1 && i3 == 0) continue; // A GC

            dp[len + 1][c][i1][i2] += dp[len][i1][i2][i3];
          }
        }
      }
    }
  }

  mint ans = 0;
  for(int i1 = 0; i1 < 4; ++i1) {
    for(int i2 = 0; i2 < 4; ++i2) {
      for(int i3 = 0; i3 < 4; ++i3) {
        ans += dp[n][i1][i2][i3];
      }
    }
  }
  cout << ans;
}

包除原理かとおもったのですが解けませんでした。ギブアップです。
動的計画法だそうで、思いつかないのはまだまだ苦手なんだなって思いました。

ザ・DPみたいな、コードだけ見てもわけわかんない系の問題ですね。
まだ拒否反応はあるのですが、以前よりも読めるようになっていて嬉しいです。

文字のままだと扱いにくいので、数字に変換します。
A : 0
G : 1
C : 2
T : 3
として、
012 / 021 / 102 / 01_2 / 0_21
が数列内になければ求める文字列になりますね。
これが何通りあるかを数えます。

特定の文字列にならなければよくて、その文字列の長さは最長で4です。
つまり、直前の4文字だけ見ていればOKで、見るべきは高々4文字になります。

後ろの4文字を見て、特定の文字列になっていなければ組み合わせの数を足しているというコードです。

以上です。ありがとうございました。