AtCoder Beginner Contest ABC403 解法メモ

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC403

ABC403A - Odd Position Sum

解法

(0..<N).toSeq.filterIt(it mod 2==0).mapIt(A[it]).sumでよい
ACコード

ABC403B - Four Hidden

解法

0..T.len-U.lenの$i$で、
(0..<U.len).toSeq.allIt(T[i+it]==U[it] or T[i+it]=='?')が成立するかみればよい
ACコード

ABC403C - 403 Forbidden

解法

各ユーザー毎に、

• クエリ$1$で閲覧権限を与えられたコンテストページの番号を格納するHashSet
• クエリ$2$で閲覧権限を与えられたかのbool

を保持し、
クエリ$3$が来たら、
HashSetにその番号があるか、そもそも、全ページの閲覧権限があるか
を確認すればよい
ACコード

ABC403D - Forbidden Difference

解法

各$Ai$の出現回数をカウントする配列を用意して、
それを間隔$D$で抜き出したとき、
数字が並ばないように削除することを考える
これは$0～10^6$の配列位置をmod Dで分類した配列毎に考えればよく、
各々の配列に対し、その項を削除するかどうかのDPを行えばよい
dp[数列の$i$項目]=そこまでで削除することになった個数の合計
とすると、
d[i]=min($i$の個数を$0$にした場合のそこまでの最小値,$i-1$の個数を$0$にした場合のそこまでの最小値)
（$0$にする、というのは、そもそも$0$かそうでなければ、その個数削除する、という意味）
となる
実装としては、
単にc=A.toCountTableとして、
また、n=10^6 div Dとして、
for i in 0..<D:
　for j in 0..n:
の中で、$n+1$項の配列dpに対して、
d[j]=min(dp[j-1]+c[D*j+i],dp[j-2]+c[D*(j-1)+i])
を遷移させていけばよい
答えは、各$i$でのdp[n]を足し合わせたものになる
ただし、$D=0$の場合は、各種$1$つだけ残ればよいから、答えはN-c.lenとなる
ACコード

メモ

$D=0$の場合を別に考えねばならないことが、最後までわからなかった
当初、$1$つ置きに削除すればよいと誤認した
AのCountTableのkeysから、
間隔$D$の連続した数列を可能な限り抜き出し、
各々の中で連続しないように削除していくことを考え、
$Ai$が$0～10^6$なので、頂点$10^6+1$個のUnion-Findを用意し、
各$Ai$に対して、$Ai-D$と$Ai+D$が$A$内にあれば辺を張る、としていくことで、数列群を作り、
できたgroupsの各々をソートした数列に対し、
「削除しないで残すこと」が$2$連続で起こらないよう、合計削除個数を最小化することを考え、
DPで、
dp[数列の$i$項目][その項を削除したか（$1$）しないか（$0$）]=そこまでで削除することになった個数合計
として、
dp[i][0]=dp[i-1][1]
dp[i][1]=dp[i-1].min+（$i$項目の個数）
の遷移を進め、
全groups数列のdp[^1].minの合計を求めた

ABC403E - Forbidden Prefix

解法

入力をすべて先読みし、
$Xi$のハッシュ値から、何番目のクエリかが引ける連想配列（同じ$Xi$に対しては。最も早いもの）を用意
答えとなる数列$a$に対して、
各$Yi$が出現したクエリ位置で$+1$
$Yi$をローリングハッシュして、連想配列を引きながら、一致した一番早いクエリ位置で$-1$
していく
最後、$a$の累積和を取ったものが答え
ACコード

---

反復学習にはmochiがおすすめ
全問入ったdeckはこちら