ACL Beginner Contestで冷えて茶におちたこと

はじめに

９月２６日に突如開催されたACL Beginner Contestで冷えて茶に落ちました。
先週、色変して緑になったばかりで７日天下でした。
またがんばって緑にあがればよいだけなのでめげずにがんばります。

冷えに不思議の冷えなし

成績は２４分３完２ペナでした。
DとEが解けそうでなかなか解けず、特にDはTLEをどうやって解消したらよいのか椅子を温めながら悩みつづけました。世に聞くセグ木とかいうものがこの悩みを解決してくれるのでは、という思いが頭をよぎりましたが、のちにその思いが正しかったことがわかりました。

そのうちセグ木を身につけてリベンジしたいと思います。

振り返り

A問題

　ACLをN回繰り返す問題です。
　シンプルにfor文で書きました。
　２分１秒はまあまあです。

B問題

B - Integer Preference

　この手の一見簡単そうで実際も簡単な問題によく嵌ります。
　嵌りました。
　
WAしたコード

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

int main() {
  long long A,B,C,D;
  cin>>A>>B>>C>>D;
  if((C<=B && B<=D)||(C<=A && A<=D)){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  return 0;
}

このコードでWAするケースとしてはA=1　B=５　C=４　D=3
が考えられます。

先にC問題を解いて戻ってきてACしましたが１ペナと５分ほどロス。
これがなければパフォ８００は超えてましたので痛恨。

C問題

UnionFindのライブラリを使う問題です。
DSUのライブラリの練習はしていたのでスムーズに取り組めました。

もっとも０オリジンをうっかりしてデクリメントをせずに１WA。
たまたまサンプルケースが通ってしまったのが不運でした。
１ペナ。

D問題

TLEしたコード。
その後，いろいろ工夫しましたがどうしてもTLEが取れません。
O（N^2）をどうしたら縮められるのかいろいろ考えましたが思いつきませんでした。

考えている最中に頭をよぎったのはよく耳にするセグ木のことでした。
まだどんなふうに使うものなのか皆目見当がついていませんが、いつか身に着けてリベンジしたいと思います。

#include <bits/stdc++.h>
using namespace std;
int A[300010];
int dp[300010];

int main() {
  int N,K;
  cin>>N>>K;
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  for(int i=0;i<N;i++){
    dp[i]=1;
  }
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
      if(abs(A[i]-A[j])<=K){
        dp[j]=max(dp[j],dp[i]+1);
      }
    }
  }
  cout<<dp[N-1]<<endl;
  return 0;
}