ferinの競プロ帳

競プロについてのメモ

ARC

ARC 081 E - Don't Be a Subsequence

問題ページ arc081.contest.atcoder.jp 解法 まず、dp[i] = (区間[i, s.size())の部分文字列に含まれない最短の文字列の長さ)としたDPを考える。文字cがi番目以降ではじめて現れる位置をnext(i, c)と表記することにすると、このDPはdp[i] = min{dp[next(i, …

ARC079D Decrease (Contestant ver.)

問題ページ D - Decrease (Contestant ver.) 解法 n=50で考える。 k=0のとき 49 49 49 … 49 とする。 k=1のときは1回操作してこの数列になればよいので 99 48 48 … 48 k=2でも同様に 98 98 47 47 … 47 これを繰り返していくと、 k = 50 で 50 50 50 … 50 k =…

ARC079 C Cat Snuke and a Voyage

問題ページ C - Cat Snuke and a Voyage dijkstraで殴った

ARC023 B問題-謎の人物X

arc023.contest.atcoder.jpD回移動した後にたどり着ける点はD回移動の範囲内に収まり偶奇が一致する点です。したがってたどり着ける点についての全探索でO(RC)で解けます。

ARC022 B問題-細長いお菓子

arc022.contest.atcoder.jp重複した数が存在しない最大の領域を求める問題です。重複した数が存在するかどうかの判定ををunordered_setで行いました。unordered系のデータ構造はじめて使ったんですが衝突さえしなければO(1)でできるの便利ですね… 解いている…