# ABC318 振り返り
- [THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318） - AtCoder](https://atcoder.jp/contests/abc318)
- 成績 ABCD 5完 (1008) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc318)
- 前回 [[ABC317 振り返り]]
パフォーマンス 1008 で、前回上がった緑色を維持できました。
![[スクリーンショット 2023-09-03 0.01.23.png]]
D と E が同程度の難易度だったので、E も解きたかったのですが残念ながら時間切れでした。
B でしょうもないことではまってしまったり、終了間際に E の計算方法がわかったなど惜しいところはありましたが今の実力値からすると適正、という感じですね。
![[スクリーンショット 2023-09-03 7.18.11.png]]
というわけで、誰が読むかもわからない振り返りです。いえ、自分のために書いてます。
----
## [A - Full Moon](https://atcoder.jp/contests/abc318/tasks/abc318_a)
先日がスーパーブルームーンだったからの問題でしょうか。粋ですね。これはやるだけ。
```haskell
main :: IO ()
main = do
[n, m, p] <- getInts
print $ length [m, m + p .. n]
```
[提出 #45129347](https://atcoder.jp/contests/abc318/submissions/45129347)
----
## [B - Overlapping sheets](https://atcoder.jp/contests/abc318/tasks/abc318_b)
座標としては $(A, C)$ $(B, D)$ と考える必要があるところを $(A, B)$ $(C, D)$ と勘違いしていて「あれ、合わない?」と頭を抱えて 10 分ほど無駄にしました。ときどきやってしまいます。
最初、二次元いもす法かと思いましたが、よく考えると各マスを塗るだけでいいので全マス目を生成して集合でユニークをとる。
二次元配列の問題で、マスに値があるかないかを判別するときは配列ではなく集合でやると楽ということはよくあります。境界を気にしなくてよくなるのが良いですね。
```haskell
main :: IO ()
main = do
n <- readLn @Int
xs <- replicateM n getInts
let xss = map (\[a, b, c, d] -> range ((a, c), (b - 1, d - 1))) xs
s = Set.fromList $ concat xss
print $ Set.size s
```
[提出 #45145329 ](https://atcoder.jp/contests/abc318/submissions/45145329)
----
## [C - Blue Spring](https://atcoder.jp/contests/abc318/tasks/abc318_c)
単純に見えて、案外難しい。B や C でこの手の問題が出るのが一番怖いです。
こういう問題でつまづくとメンタルを立て直すのが大変...。
$1$ 日あたりの旅費は $F_1, F_2, F_3 ...$ と個別に与えられている
その一方で $D$ 枚セットの周遊チケットが $P$ 円で売られていて、このチケットを使うと好きな $F_i$ を無料にすることができる。
「$D$枚セット」なので、下手に買いすぎるとチケットが余ってしまう。最適な購入数で留める必要があります。
ぱっと思いつくのはチケットの $1$ 日あたりの単価を出して突合するやり方ですが、これだと浮動小数点が出てきて危ないし、$D$ 枚セットの境界判定の実装が大変そう。
ところで数列ですが、購入したパスは1枚ずつ好きな日に使えるので順序に意味がありません。数列があるのに順序に意味がないときはソートしたりバケットをとったりするのが定石です。大きい順にソートしてみます。
入力例 $1$ だと
```
7 6 6 1 3
```
となります。これと $D = 2$ という数値をうーんと睨めっこしていたところ
```
[7, 6], [6, 6], [1, 3]
```
と分けると、どの塊でチケットを使えばいいかが判断できることに気づきました💡
```haskell
main :: IO ()
main = do
[_, d, p] <- getInts
fs <- getInts
let xs = map sum $ chunksOf d (sortOn Down fs)
print $ sum $ map (\x -> if p < x then p else x) xs
```
- [提出 #45151690](https://atcoder.jp/contests/abc318/submissions/45151690)
----
## [D - General Weighted Max Matching](https://atcoder.jp/contests/abc318/tasks/abc318_d)
入力の形式からワーシャルフロイドかなあと思いましたが、違いました。
頂点の被りがないように2頂点ずつ選ぶ、経路に意味はなさそう。$N \leq 16$ なので全部試すことを要求されていると踏みました。
ここで自分の盆栽の中に `1, 2, 3, 4` という数列を `[(1, 2), (3, 4)] [(1, 3), (2, 4)] [(1,4), (2,3)]` というペアの組み合わせ全列挙する関数を持っていることを思い出しました。[ABC236 D - Dance](https://atcoder.jp/contests/abc236/tasks/abc236_d) を解くのに実装したものです。DFS (再帰) ですね。
$N = 16$ に対して実際にペアを生成して、計算量的に間に合うことがわかったのでこれを使って解きました。
頂点数が奇数の場合はペアをうまく生成できませんが、その場合は頂点を一つ足して偶数にし、その頂点への重みは常に $0$ とすることで補正できます。
結局、解法そのものより入力を配列に入れるところの実装の方が時間がかかりました。
こういう入力ときおり見かけるので、ライブラリ化しておこうと思います。
なお想定解法は bit DP みたいですね。あとで bit DP でも解こうと思います。
```haskell
main :: IO ()
main = do
n <- readLn @Int
ds <- replicateM (n - 1) getInts
let n' = if even n then n else n + 1
xs = zipWith (\i xs -> zipWith (\j d -> ((i, j), d)) [i + 1 ..] xs) [1 ..] ds
g = accumArray @UArray (flip const) 0 ((1, 1), (n', n')) (concat xs)
print $ maximum [sum [g ! v | v <- ps] | ps <- pairPermutations [1 .. n']]
{-- Library --}
-- >>> pairPermutations [1 .. 4]
-- [[(1,2),(3,4)],[(1,3),(2,4)],[(1,4),(2,3)]]
pairPermutations :: Eq a => [a] -> [[(a, a)]]
pairPermutations [] = [[]]
pairPermutations (x : xs) = do
y <- xs
sub <- pairPermutations (delete y xs)
[(x, y) : sub]
```
- [提出 #45168350](https://atcoder.jp/contests/abc318/submissions/45168350)
----
## [E - Sandwiches](https://atcoder.jp/contests/abc318/tasks/abc318_e) (upsolve)
時間は十分に合ったのですが、解ききれず。
紙の上で計算方法をあれこれやって「わかった !」 と思って顔を上げたら時間過ぎてましたw
$3$つ組の場合は真ん中に注目するという定石があるみたいですね。
自分はそうではない解法で考えました。
「同じ整数の間に何個違う整数が挟まっているか」を基本に考えます。
例えば以下の図なら $2$ に着目していますが、$2$ の出現位置から距離を取ることで間に何個あるか自体はすぐにわかります。
問題は図にある通り、各 $2$ からみて自分より後ろにある $2$ 全てに対する依存があるところですね。ナイーブに計算すると $O(N^2)$ で間に合いません。
![[スクリーンショット 2023-09-03 8.08.10.png]]
累積和をうまく使うと、線形に計算できました。
1. 一番左の $2$ から右端まで累積和をまず取ります。これが `[0, 1, 4, 6]` になります。和は 11 です
2. 次の $2$ から右端までの累積和は `[3, 5]` です。和は 8 です
3. 次の $2$ から右端までの累積和は `[2]` です。和は 2 です。
この $11 + 8 + 2 = 21$ が欲しい答えではありますが、1, 2, 3 でそれぞれ累積和をとってしまうと当然 TLE します。
が、今回欲しいのは累積和の和なので 1 だけ計算してやれば 2 と 3 は $O(1)$ で計算できます。
累積和は再帰的な構造を持っているので、 以下の図のように考えると 1 の累積和の先頭要素に着目して、累積和に対して累積演算して行くことで目的の `[11, 8, 2]` を作り出すことができます。
![[スクリーンショット 2023-09-03 8.19.04.png]]
以下、その実装です。
ありそうでなさそうな計算ではあります。ただちょっと、難しいですね。
想定解法の定石の方が簡単そうなので、そちらをマスターしたいと思います。
```haskell
-- >>> f [1, 3, 2]
-- 21
f :: [Int] -> Int
f xs = do
let n = length xs + 1
s = scanl' (+) 0 xs
let (_, s') = mapAccumL g (sum s, 0) (zip [n, n - 1 ..] s)
where
g (acc, k) (i, a) = do
let acc' = acc - (a - k) * i
((acc', a), acc')
sum s'
main :: IO ()
main = do
n <- getInt
as <- getInts
let uvs = zip as [1 :: Int ..]
g = graph (1, n) uvs
ds = [zipWith (\b a -> b - (a + 1)) xs (tail xs) | xs <- elems g]
print $ sum (map f ds)
```
- [提出 #45205476](https://atcoder.jp/contests/abc318/submissions/45205476)
----
## 感想
パフォーマンス 1000 ぐらいは安定して出せるようになってきましたが、次の壁がなかなか越えられません。
毎回手は掛かっている気がするのですが。でもまあ、訓練していけば越えられる感じはするので引き続きやっていこうと思います。
今回も、昼にストレッチに行って、コンテスト前に風呂に入って汗をかきました。
やはり一汗かいてから本番に臨むと緊張がだいぶ和らぐというか、緊張はしているのですが緊張度を一定ラインに留めることができるように思いました。自律神経を安定させるのが重要なんでしょう。風呂もいいですが有酸素運動も良いです。
競プロをきっかけに汗をかく。名付けて競プロ健康法。いや、実際そのために平日も有酸素運動したりストレッチに行ったりしてるので、おかげで健康になってきてますw
## 宿題
- [x] D 問題を bit DP で解く
- [x] D 問題の入力形式をライブラリにする
- [ ] E 問題の定石をマスターする