はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Beginner Contest 060 / AtCoder Regular Contest 073 解説

競技プログラミング

ABC060: http://abc060.contest.atcoder.jp
ARC073: http://arc073.contest.atcoder.jp

本家の解説

以下、解説

























A. Shiritori

http://abc060.contest.atcoder.jp/submissions/1255055
C++のstringクラスのfront,backメソッドを使うと楽

B. Choose Integer

http://abc060.contest.atcoder.jp/submissions/1255056
Aの倍数を適当に足してできた数は、結局はAの倍数である。
よって、「あるAの倍数 mod B = C」を満たすかチェックすれば良い。
賢いアルゴリズムを考えるべきではあるが、AtCoderの200点は愚直にやれば解ける問題が多いので、何かしらの全探索をまず考えてみよう。
ここではAの倍数を全列挙して考えればよい。

C. Sentou

http://abc060.contest.atcoder.jp/submissions/1255057
t[i]秒にスイッチが押されてt[i+1]秒にまたスイッチが押されるとき、お湯が出続ける時間はmin(T, t[i+1]-t[i])である。
この計算は全ての区間について独立に考えることができる（延長される訳ではないので）ので、全ての区間の時間を足すと答え。
t[N]秒で押されてからT秒出るので、それを足すのを忘れないように。
オーバーフローにも気をつける。

D. Simple Knapsack

http://abc060.contest.atcoder.jp/submissions/1255058
dp[i][w0][w1][w2][w3] := i番目まで使ってw[0]の物をw0個,w[0]+1の物をw1個,w[0]+2の物をw2個,w[0]+3の物をw3個取る時の価値の最大
として、根性O(N^5)DPをする。
dp[101][101][101][101][101]とするとMLE。
よくあるメモリ領域を使いまわすDP手法を使って、dp[2][101][101][101][101]としてもMLE。
w0～w3の個数をカウントして上限ギリギリにしてやってAC。

E. Ball Coloring

http://arc073.contest.atcoder.jp/submissions/1255061
全ての要素の最大MAXと最小MINは必ずRmax,Rmin,Bmax,Bminのどれかに現れる。
赤と青で特別に分ける理由も特に無いので、以下の2つに場合分けして解く。
Rmax=MAX,Bmin=MIN(solve1関数)
赤の方はなるべく下限を大きく、青の方はなるべく上限を小さくしたいので、全てのペアに関して、大きい方を赤、小さい方を青とすればよい。
Rmax=MAX, Rmin=MIN(solve2関数)
赤の方は適当で良く、青の最大と最小の差を最小化するアルゴリズムを考える。
赤側の方は特に考える必要は無く、青の方を上手くやるようにアルゴリズムを作ろう。
まず全てのペアについて小さい方を青とする。
それから、小さい方から順番に大小を入れ替えていきながら、答えの最小値を探せば良い。
最小値最大値のセグメントツリーを用意して実装した

F. Many Moves

http://arc073.contest.atcoder.jp/submissions/1255256
公式解説の通り説明していく

O(N^3)解法
dp[i][a][b] := i番目までのクエリを終えていて、片方の駒がa,もう片方の駒がbにいる最小時間
dp[0][A][B] = 0, dp[0][?][?] = INF
dp[i + 1][X[i]][B] = min(dp[i][A][B] + |X[i] - A|)
dp[i + 1][A][X[i]] = min(dp[i][A][B] + |X[i] - B|)
で更新する
メモリがまず乗らないのでダメ

O(N^2)解法
dp[i][a] := i番目までのクエリを終えていて、片方の駒がa、もう片方の駒がX[i-1]にいる最小時間
X[-1] = Bとしておき、dp[0][A] = 0, dp[0][?] = INFが初期値
後は、aをX[i]に移すか、X[i-1]をX[i]に移すかで更新する
iの方はそのまま置くとMLEするので、使いまわすアレで使いまわす。
O(N^3)解法におけるbはb=X[i-1]であると考える

1. b(X[i - 1]) -> X[i]の遷移
dp[(i + 1) % 2][a] = min(dp[(i + 1) % 2][a], dp[i % 2][a] + abs(b - X[i]));

2. a -> X[i]の遷移
dp[(i + 1) % 2][b] = min(dp[(i + 1) % 2][b], dp[i % 2][a] + abs(a - X[i]));

O(NlogN)解法
各遷移を高速化することを考える。

遷移1はよくよく見ると、dpの全ての要素にabs(b-X[i])を足しているだけと見れる。
そして、全てに同じ数を足しても大小関係は特に変わらないので、offsetを用意しておき、そちらに累積しておく。

遷移2もよくよく見ると、毎回要素bの1つしか更新していない。
更新式を分解してみると

min{a=0...N}(dp[i][a] + abs(a - X[i]))
= min{ min{a=0...X[i]}(dp[i][a] - (a - X[i])), min{a=X[i]...N}(dp[i][a] + (a - X[i]))
= min{ min{a=0...X[i]}(dp[i][a] - a) + X[i], min{a=X[i]...N}(dp[i][a] + a) - X[i] }

となり、dp[i][a] - aの区間最小値、dp[i][a] + aの区間最小値を聞く問題に帰着する。
よって、これを探して最小値を持ってくれば良い。
最後に -= abs(b-X[i]) するのに注意（他の要素は+abs(b-X[i])されているので、こちら側の遷移でされてない分引くことで帳尻が合う）
これでAC