# ABC374 振り返り
- [キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374） - AtCoder](https://atcoder.jp/contests/abc374)
- ABCD 4完 (1105) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc374)
![[スクリーンショット 2024-10-06 11.22.19.png]]
ABC374 でした。
前回 [[ABC373 振り返り | ABC373]] に似ていて E, F の難易度が高めでした。
- A (灰) ··· 文字列の末尾3文字をとって `san` かどうか調べる
- B (灰) ··· 先頭から比較して文字が異なるインデックスを調べる
- C (灰) ··· 部分集合を全部列挙して試す。一般にはビット全探索。Haskell なら `subsequences`
- D (茶) ··· 順列全探索 + ビット全探索で全経路試す
- E (水, upsolve) ··· 答えで二分探索。二分探索に渡す $f$ 関数の構成が難しかった
でした。
E は「答えで二分探索」なのがわかっていても解けず。
テストケースは通るものの WA がなくせず、時間切れでした。惜しかったと思いたいところですが、考察してみると、自力で答えに到達するのは難しかったのがよくわかりました。
## [A - Takahashi san 2](https://atcoder.jp/contests/abc374/tasks/abc374_a)
文字列 $S$ の末尾が `san` になってるか確認する。
Haskell なら `takeEnd 3` で後ろから 3文字取るとよいです。
```haskell
main :: IO ()
main = do
s <- getLine
let s' = takeEnd 3 s
printYn $ s' == "san"
```
## [B - Unvarnished Report](https://atcoder.jp/contests/abc374/tasks/abc374_b)
文字列 $S$ と $T$ を比較して、異なる場合は異なる最初の位置を特定する。
まず $S = T$ の場合を場合分けで処理。これで単純化する。
あとは `zipWith (=)` で $S$ と $T$ の異なる最初の位置を探す。
それでも同じ場合は長さが違うので、それを考慮する。
過去にも似たような問題があった気がします。
と、いいつつ $S$ の長さしかみておらず、$T$ の長さを考慮するのを失念して 1ペナもらいました。
```haskell
main :: IO ()
main = do
s <- getLine
t <- getLine
let n = length s
m = length t
if s == t
then print 0
else do
print $ case elemIndex False $ zipWith (==) s t of
Just i -> i + 1
Nothing -> min n m + 1
```
## [C - Separated Lunch](https://atcoder.jp/contests/abc374/tasks/abc374_c)
$N \leq 20$ 程度の整数を $2$ つのグループに分割する、というのが主眼です。
$20$ しかないので部分集合を全部列挙できます。全部列挙しても $2^{20}$ で $10^6$ 程度のサイズです。
Haskell の場合、リストの部分集合を全部列挙するのに `subsequences` を使うと良いです。
まず、$K_i$ の合計を求めておく。
部分集合を求めて、その総和がグループ $A$ 側の人数。$K_i$ の合計からそれを引いたものが $B$ 側の人数とみなせます。
その二つのうち大きい方が「同時に昼休みをとる最大人数」になります。
これを全部分集合に対して試して、最小を取る。
```haskell
main :: IO ()
main = do
_ <- getInt
ks <- getInts
let s = sum' ks
ans = minimum [max (sum ks') (s - sum ks') | ks' <- subsequences ks]
print ans
```
## [D - Laser Marking](https://atcoder.jp/contests/abc374/tasks/abc374_d)
平面上に、指定された $N$ 本の直線を引くにあたりレーザー照射の移動にかかる時間を最短にしたい。
レーザーを照射しているときは速度 $S$ 、そうでないときは速度 $T$ で移動できる。
$N \leq 6$ と小さいので、C 問題に同じく全列挙でよいです。
今回は $N$ 個の直線をどういう順番で引くか、が関心事なので `permutations` を使います。計算量は $O(N!)$ です。
全パターン試すには直線を描く順番に加えて、直線の開始位置を $v_1 = (A_i, B_i)$ と $v_2 = (C_i, D_i)$ どちらを先にみなすかの判断が必要。
直線ごとに $(v1, v2)$ と解釈するか、反転させて $(v2, v1)$ と解釈するかを全パターン試したい。
ビットマスクのように $N$ 個に対して `[True, False, True, ...]` みたいな反転するか否かの系列を全パターン生成するとよいです。
これまたビット全探索、Haskell なら `sequence $ replicate n [True, False]` で書けます。更にいうと `replicateM` をリストモナドに適用する `replicateM n [True, False]` でも OK
```haskell
ghci> replicateM 3 [True, False]
[[True,True,True],[True,True,False],[True,False,True],[True,False,False],[False,True,True],[False,True,False],[False,False,True],[False,False,False]]
```
便利です。
こちらの計算量は $2^6 = 64$ 程度です。
`permutations [0 .. n - 1]` と `replicateM 6 [False, True]` の計算量を合算しても $6! \times 2^6 = 720 \times 64 = 46080$ 通りと小さいです。
なお `permutations` と `replicateM` の直積はリスト内包表記で 合成すると簡単です。
あとはその全列挙したパターンに対し、距離関数を定義して全部計算し最小値を得ます。
`Double` で全部計算しても精度としては問題ないです。
```haskell
main :: IO ()
main = do
(n, s, t) <- auto @(Int, Double, Double)
xs <- replicateM n $ do
[a, b, c, d] <- map (read @Double) . words <
gt; getLine
return ((a, b), (c, d))
let xa = listArray @Array (0, n - 1) xs
ans =
minimum
[ resolve s t xa path choices
| path <- permutations [0 .. n - 1],
choices <- sequence $ replicate n [True, False]
]
print ans
resolve s t xa path choices =
let path' = ((0, 0), (0, 0)) : zipWith (\i c -> bool (xa ! i) (swap $ xa ! i) c) path choices
dists = zipWith fn path' (tail path')
where
fn (_, u2) (v1, v2) =
let d1 = distance u2 v1
d2 = distance v1 v2
in d1 / s + d2 / t
in sum' dists
distance :: (Double, Double) -> (Double, Double) -> Double
distance (x1, y1) (x2, y2) = sqrt ((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
```
## [E - Sensor Optimization Dilemma 2](https://atcoder.jp/contests/abc374/tasks/abc374_e)
結論、答えで二分探索でした。
$N \leq 100$ と小さいので DP かと思いましたが、DP をどう構成しても計算量を落としきれない。
一方「最小値の最大値」とか、ある製造能力 $w$ を達成したいときに必要な予算 $f(w)$ は $O(N)$ 程度で計算できそうな雰囲気があるので、おそらく $f(w) \leq X$ を二分探索する問題と踏みました。
この方針は合ってました。
問題はその $f$ 関数の定義です。
- 製造能力を $i \ldots N$ 工程まですべて、最低でも処理能力 $w$ にするためには、 $S_i$ を幾つ購入し、$T_i$ を幾つ購入しその結果コストは幾らになるか?
を計算するわけです。
まず機械 $S_i$ だけを購入するパターンを考えてみます。
機械 $S_i$ は $1$ 台あたり $A_i$ 個分処理できるわけで、それだけで $w$ に到達させるには $\lceil {w}/{A_i} \rceil$ 個、$S_i$ を購入すると良いです。これで必要な $S_i$ の個数が求まる。
機械 $T_i$ に対しても同様に考えられる。つまり $\lceil w/B_i \rceil$ 個
問題は、二つの機械を混ぜて買うときです。ここの最適解の割り出しが難しい。
ここは解説にある通り、$S_i$ の台数の上界は $B_i$ 、$T_i$ の台数の上界は $A_i$ として全探索すれば良いようです。
$A_i, B_i \leq 100$ なのでもっと雑に、それぞれ $0 \ldots 100$ 台までを考慮すれば良い。
$S_i$ の台数 $k$ が求まれば、$w$ 到達に必要な残りは $w - k \times A_i$ になるので、先に同様それを $B_i$ で `ceildiv` することで $T_i$ の台数およびコストが求まります。
$T_i$ の台数 $k$ を探索するときにも同じ。
うーん、まさか一方の台数の上界が $100$ で良いとは、まったく思いつかず (というか未だあまりよく飲み込めていない 😓)
この考察に至らず三部探索とか色々やっていましたが、だめでした。
```haskell
main :: IO ()
main = do
[n, x] <- getInts
items <- replicateM n $ do
[a, p, b, q] <- getInts
return (a, p, b, q)
let (ok, _) = bisect2 (0, 10 ^ 9 + 1) (\wi -> f wi <= x)
where
f wi = sum' [cost item wi | item <- items]
cost (a, p, b, q) wi =
let ss = (wi `ceildiv` a) * p
ts = (wi `ceildiv` b) * q
both1 =
minimum
[ k * p + (remain `ceildiv` b) * q
| k <- [0 .. 100],
let remain = wi - k * a,
remain >= 0
]
both2 =
minimum
[ k * q + (remain `ceildiv` a) * p
| k <- [0 .. 100],
let remain = wi - k * b,
remain >= 0
]
in minimum [ss, ts, both1, both2]
print ok
```
## 感想など
E は本戦中に解けそうで解けない感じだったので、惜しいかと思っていましたがよくよく考察してみると、自力では上界を $100$ にして全探索するという理屈にまったく辿りつけなかったですし、そこがこの問題の本懐だと思います。というわけで、惜しくない。
答えで二分探索なのは慣れていれば雰囲気で分かるわりに Difficulty が高いので何でだろうと思いましたが、合点がいきました。
終わってみれば B の 1ペナがもったいなかったです。
これがなければ水色パフォーマンスで、もうすこしレートが上がっていました。
が、+2 で微増、減らなかっただけでもよしとしましょう。
次回 ABC375 も予定どおり参加予定です。