ACL Beginner Contest 感想

ううううううううううしたぷにきあくん笑笑笑笑笑笑笑笑笑

ACL Beginner Contestに参加して図1のような成績だった　5完いたのは良い。5ペナはカス　レートは上がったのでﾖｼ!

コンテスト中に解くことが出来たAからEまでの感想を吐く。

A. Repeat ACL

yarudake rep(i,k)cout<<"ACL";

https://atcoder.jp/contests/abl/submissions/17049246

B. Integer Preference

難しすぎる　適当を書いて2ペナ(は？)1ペナした時点で次は絶対ACできる提出をしろや

区間(A,B)と(C,D)が重なっているか判定する。二つの区間が重なっている場合は4通りしかないので全部試す

https://atcoder.jp/contests/abl/submissions/17049284

C. Conner Cities

union find (disjoint set)で与えられたグラフを構築します。互いに行き来することが出来る頂点をまとめて一つの頂点としてみた時に残っている頂点の個数を $N'$ とするとそれらの頂点を連結にするために必要な辺の数は $N'-1$ になる。いや直感でわかるので説明するのが難しいです

https://atcoder.jp/contests/abl/submissions/17049380

D. Flat Subsequence

い　つ　も　の

お　ま　た　せ

親　の　顔　よ　り　見　た　セ　グ　木　D　P

dp[i][j] = i 番目までみてBに値 j を選択するときの最大の長さとしてDPをする。よくみると時系列の i は不要だとわかるのでdp[j] = B に値 j を選択するときの最大の長さとする。遷移は値 j との差の絶対値が k 以下のところから遷移してくることができるので $dp[ a_i ] = max(dp[a_i-k],dp[a_i-k+1],...,dp[a_i+k-1],dp[a_i+k])+1$ と表せる。これを愚直にやると $O(N^2)$ なので区間 max をセグ木で高速化する.