AtCoder: ABC122

A – Double Helix

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

実装

とりあえずcaseで実装。

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

B – ATCoder

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

文字を一文字ずつ読み込み、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

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

最初に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

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

シェアする

  • このエントリーをはてなブックマークに追加

フォローする