ARC104参戦記

はじめに

ARC104は２完パフォ608で前回に続いて冷えてレート-18で新レート779になりました。
続けざまに冷えてちょっと悲しいですが冷える回こそ力をつける回です。

一喜一憂せずに精進を重ねたいと思います。

A問題

A - Plus Minus

A+BとA-BからAとBを求める問題。
中学入試とかでよくでてくるやつですね。
しっかり確認して２分１秒でAC。まあまあです。

B問題

B - DNA Sequence

考察

文字列の連続する部分列から並び替えによってA-T C-Gのペアにできるものの数を求める問題。
最初はAとTの数，CとGの数がともに等しくなるような部分列を全探索で求めることをやりました。

Nがmax5000くらいでつくる部分列は必ず偶数であるため5000*2500=1250万くらいならまにあうかとえいやで出してるのがよわよわです。評価にも時間がかかるのでTLEしました。
countは文字列長さ分の検索を行うのでO(N^3)オーダーになるようです。

TLEしたコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin>>N;
  string S;
  cin>>S;
  string T;
  int cnt=0;
  for(int i=1;i<=(N/2);i++){
    for(int j=0;j<=N-2*i;j++){  
      T=S.substr(j,2*i);
      //cout<<j<<" "<<i<<" "<<T<<endl;
      if(count(T.cbegin(),T.cend(),'A')==count(T.cbegin(),T.cend(),'T') && count(T.cbegin(),T.cend(),'C')==count(T.cbegin(),T.cend(),'G')){
        cnt++;
      }
    }
  }
  cout<<cnt<<endl;
  return 0;
}

更に考察

枝刈りをいろいろ考えてみましたがうまくありません。
尺取り的な方法を考える中で評価のところをシンプルにやるために累積和をとることに思い至りました。
これだと計算量的にはO(４*N+N^2)ぐらい。間に合いました。

この方針思いつくまでに４０分かかり、更に実装に３０分かけてようやくACしました。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin>>N;
  string S;
  cin>>S;
  int A[N+1],asum;
  int T[N+1],tsum;
  int G[N+1],gsum;
  int C[N+1],csum;
  A[0]=0;
  T[0]=0;
  G[0]=0;
  C[0]=0; 
  asum=0;
  tsum=0;
  gsum=0;
  csum=0;
  for(int i=0;i<N;i++){
    if(S.at(i)=='A'){
      asum++;
    }
    if(S.at(i)=='T'){
      tsum++;
    }
    if(S.at(i)=='G'){
      gsum++;
    }
    if(S.at(i)=='C'){
      csum++;
    }    
    A[i+1]=asum;
    T[i+1]=tsum;
    G[i+1]=gsum;
    C[i+1]=csum;
  }
  long long  cnt=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j=j+2){
      //cout<<i<<" "<<j<<" "<<A[i]<<" "<<A[j]<<" "<<T[i]<<" "<<T[j]<<endl;
      if(A[j+1]-A[i]!=T[j+1]-T[i])continue;
      //cout<<i<<" "<<j<<" "<<C[i]<<" "<<C[j]<<" "<<G[i]<<" "<<G[j]<<endl;      
      if(C[j+1]-C[i]==G[j+1]-G[i])cnt++;
    }
  }
  cout<<cnt<<endl;
  return 0;
}

C問題

C - Fair Elevator

難しかったです。
時間いっぱい考えましたが正しい回答に辿り着けませんでした。
解説を聞いて方針は理解できましたがこのレベルが解けるようになるのはまだまだ先になりそうです。

反省

今回の反省はB問題でみえみえのTLEを実装して時間を溶かした（更にTLEで２ペナくった）ことだと思います。これが現在の実力なので仕方ないところですが，このくらいのんびりだと解けても１完最速組とパフォがあまり変わりません。

２完最速のパフォは1855（ただし2分28秒のファーストACとってる方なのでなかなかまねできない）２完最遅のパフォ538なのでその差は1300以上。

今回はなんとかB問題を解ききった自分をほめつつ、実装力の強化もがんばりたいと思います。