# ABC314 振り返り
- [AtCoder Beginner Contest 314 - AtCoder](https://atcoder.jp/contests/abc314)
- 成績 ABCD 4完 (910) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc314)
- 前回 [[ABC313 振り返り]]
ABC314 は高難度回の前回に比較すると、D までは比較的簡単な回でした。
314 だから 3.14 や円に絡んだ問題が出る、と噂になってしましたが実際そうなりましたね。ただし $\pi$ を使うような円の計算問題のようなものはなかったようです。
改めて初の5完を目指してましたが、E が青難易度。700人強しか解けていないような問題でしたので、ちょっと厳しかったです。
DP だなーというのはわかったんですが、期待値DPに取り組んだことがなかった私には無理ゲーでした。
以下 A 〜 D の振り返りです。ソースコードはコンテスト後にリファクタリング済みです。
----
## [A - 3.14](https://atcoder.jp/contests/abc314/tasks/abc314_a)
- [提出 #44490322 - AtCoder Beginner Contest 314](https://atcoder.jp/contests/abc314/submissions/44490322)
円周率の小数第 $100$ 位までから、小数第 $N$ 位までを抜き出して表示する問題。
最初問題文に与えられている円周率が小数第 $100$ 位まで全部ないのでは! と思って「えっ、この界隈では円周率 $100$ 位まで暗記してるのが普通なんですか?」と驚愕しましたが、よく見たら $100$ 位まで書いてました。のでいそいそとコピペ
なお、Twitter見てたら $100$ 位まで暗記してて解いたという人も実際にはいました 😨
```haskell
main :: IO ()
main = do
n <- readLn @Int
let s = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
xs = take n s
putStrLn $ concat ["3.", xs]
```
----
## [B - Roulette](https://atcoder.jp/contests/abc314/tasks/abc314_b)
- [提出 #44548390 - AtCoder Beginner Contest 314](https://atcoder.jp/contests/abc314/submissions/44548390)
$X$ に賭けた人だけを抽出して、その $X$ に賭けた人の中でも賭けた目が最小だった人たちを表示する。
特に難しくはないんですが、最小を求めたり同じ最小値を持ってる人を抽出したりと地味に線形な処理が多く、実装するのがやや面倒でした。
```haskell
main :: IO ()
main = do
n <- readLn @Int
xss <- replicateM n $ do
c <- readLn @Int
as <- getInts
return (c, as)
x <- readLn @Int
-- X に賭けた人の id と個数を抽出
let ys = map (\(i, (ci, _)) -> (i, ci)) $ filterOnSnd (\(_, as) -> x `elem` as) $ zip [1 :: Int ..] xss
if null ys
then print (0 :: Int)
else do
-- 最小の個数 k を賭けた人に絞る
let (_, k) = minimumOn snd ys
zs = map fst $ filterOnSnd (== k) ys
print $ length zs
putStrLn . unwords . map show $ zs
```
----
## [C - Rotate Colored Subsequence](https://atcoder.jp/contests/abc314/tasks/abc314_c)
- [提出 #44548496 - AtCoder Beginner Contest 314](https://atcoder.jp/contests/abc314/submissions/44548496)
問題文がややこしい。読解に時間がかかる私としてはこういう問題に時間がかかってしまいます。
しかし焦りは禁物、落ち着いてノートに問題のあらましを記述しながら動きを確かめて解法の方針を立てました。
![[IMG_2918.jpeg|600]]
同じ色の文字の部分列を巡回シフトする、というところがナイーブにやるとやや計算量的に怪しそうに思いましたが、実際には $N$ に対してその部分列の個数分しか処理しないで、$O(N)$ でした。
```
-- sa は文字列 S
> f sa [1, 4, 7]
[(4,'a'),(7,'b'),(1,'c')]
```
こういう関数があればあとはやるだけ、という方針が立ったのでそれを実装して AC しました。
なお途中、グラフにしてるのは「同じ色の文字の出現位置」がグラフの隣接リストと同じ構造をしているので、横着して流用しました。
```haskell
-- $setup
-- >>> let sa = listArray (1, 8) "apzbqrcs" :: UArray Int Char
-- >>> f sa [1, 4, 7]
-- [(4,'a'),(7,'b'),(1,'c')]
f :: UArray Int Char -> [Int] -> [(Int, Char)]
f _ [] = []
f sa (x : xs) = zip (xs ++ [x]) (map (sa !) (x : xs))
main :: IO ()
main = do
[n, m] <- getInts
s <- getLine
cs <- getInts
let sa = listArray @UArray (1, n) s
xs = elems $ amap sort $ graph (1, m) (zip cs [1 :: Int ..])
s' = elems . array @UArray (1, n) $ concatMap (f sa) xs
putStrLn s'
```
----
## [D - LOWER](https://atcoder.jp/contests/abc314/tasks/abc314_d)
- [提出 #44548422 - AtCoder Beginner Contest 314](https://atcoder.jp/contests/abc314/submissions/44548422)
クエリ先読みの問題。クエリ問題はナイーブにやると TLE するから何か一捻りしろ、というのは相場が決まってます。
問題をよく見ると、大文字小文字操作は毎回やらなくても、最後の一回だけ分だけを考慮すればいいということがわかります。
というわけでクエリを先読みして、後ろから見ていって一番最後の大文字小文字操作のところで列を前半、後半の二つに分割します。前半の置換を終えてから、その最後の大文字小文字操作を加えて、残りを置換する。これで AC。
なお後ろから見ていって目的の場所で列を分割する... というのには `Data.List.Extra.breakEnd` が使えるのですが、本番中は「そんな関数あったような気がするなー」と思いつつ思い出せなかったので、`reverse` して後ろから見て分割してまた `reverse` して戻すみたいなことをやってたら途中で訳がわからなくなり、混乱して時間を浪費しました。
ハイレベル関数は、日頃から意識的に使って記憶回路に植え付けておくべし...
```haskell
main :: IO ()
main = do
n <- getInt
s <- getLine
q <- getInt
qs <- replicateM q $ do
[ti, xi, ci] <- words <
gt; getLine
return (read @Int ti, (read @Int xi, head ci))
-- 後ろから見ていって最初に 1 でない数が出たところで二つに分割
let (pre, post) = breakEnd (\(ti, _) -> ti /= 1) qs
-- 最後の大文字/小文字操作はどれか
-- 0 の場合は大文字 / 小文字操作なし
z = if null pre then 0 else fst (last pre)
-- 大文字 / 小文字操作されるところまで置換
let sa = listArray @UArray (1, n) s
s' = elems $ accum (flip const) sa $ map snd $ filterOnFst (== 1) pre
-- 最後の大文字 / 小文字操作を適用
let s'' = case z of
0 -> s'
2 -> lower s'
_ -> upper s'
-- 残りを置換
let sa2 = listArray @UArray (1, n) s''
x = elems $ accum (flip const) sa2 $ map snd $ filterOnFst (== 1) post
putStrLn x
```
----
## 感想・反省など
いずれの問題も解法につまづいたりすることもなく解けました。
が、ちょっと実装スピードが遅いです。今回も E が青だったこともあって、早く解けたかどうかでスコアに大きく差がつきました。同じ4完でも水色パフォーマンスの人と、自分とで比較すると $20$ 分くらいの差があります。
早く実装するのが苦手というより、本戦の緊張感で慎重になってしまいがち、というメンタル的なところに原因があるように思います。実際、競プロに限らず平常心なら実装は割と早い方だと思います。こればかりは地道な訓練が必要です。引き続き、あさかつなどに参加して鍛えていこうと思います。あさかつに出られない日も、タイマーで 60分セットして解く、というのを日課にしています。