AtCoder: ABC122

A – Double Helix

問題

解法

入力に対応する塩基を出力するだけ。

実装

とりあえずcaseで実装。

case gets.chomp
when 'A'
  puts 'T'
when 'T'
  puts 'A'
when 'G'
  puts 'C'
when 'C'
  puts 'G'
end

B – ATCoder

問題

解法

文字を一文字ずつ読み込み、ATGCのいずれかであれば部分文字列の長さを1増やし、それ以外であれば部分文字列の長さを0にもどす。各部分文字列の最大値を記憶・更新しておいて、最後に出力すれば良い。

実装

S=gets.chomp.split("")
ans = 0
tmp = 0
S.each do |c|
  if "ATGC".include?(c)
    tmp += 1
  else
    ans = [tmp,ans].max
    tmp = 0
  end
end
ans = [tmp,ans].max

C – GeT AC

問題

解法

累積和の変形問題という感じ。

最初に1文字目からn文字目までの’AC’の出現回数の数列を用意しておく(Cnとする)
そして、各l、rについては、C[r]-C[l]を計算すれば定数時間で計算可能。

実装

N,Q=gets.chomp.split.map(&:to_i)
S=gets.chomp
csum = [0,0]
0.upto(N-2) do |i|
  if S[i,2] == 'AC'
    csum[i+2] = csum[i+1] + 1
  else
    csum[i+2] = csum[i+1]
  end
end

Q.times do
  l,r=gets.chomp.split.map(&:to_i)
  puts csum[r]-csum[l]
end

D – We Like AGC

問題

解法

DPで解ける。

DP[直前の3文字][n]: 文字列の長さがnでの直前の3文字毎の文字列の数

とすると、nが3の場合が初期値となり、以下の通りとなる。

DP[‘AGC’][3] = 0
DP[‘GAC’][3] = 0 (1文字目と2文字目を入れ替えるとAGCになるので)
DP[‘ACG’][3] = 0 (2文字目と3文字目を入れ替えるとAGCになるので)
DP[上記以外][3] = 1

4文字目以降については、直前の4文字に着目して条件に一致する場合だけ数え上げて行けば良い。

実装

N=gets.to_i
ACGT=['A','C','G','T']
MOD=10**9+7
dp = {}
ACGT.each do |c1|
  ACGT.each do |c2|
    ACGT.each do |c3|
      c = c1+c2+c3
      dp = [0]*102
      if c == 'AGC' || c == 'ACG' || c == 'GAC'
      else
        dp[3] = 1
      end
    end
  end
end
4.upto(N) do |i|
  ACGT.each do |c1|
    ACGT.each do |c2|
      ACGT.each do |c3|
        ACGT.each do |c4|
          c = c1+c2+c3+c4
          if c.match(/AGC/) || c.match(/GAC/) || c.match(/ACG/) || c.match(/A.GC/) || c.match(/AG.C/)
          else
            dp[c2+c3+c4][i] += dp[c1+c2+c3][i-1]
            dp[c2+c3+c4][i] %= MOD
          end
        end
      end
    end
  end
end
ans = 0
dp.each_key do |k|
  ans += dp[k][N]
end
puts ans%MOD

コメント

タイトルとURLをコピーしました