# ABC333 振り返り - [トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333） - AtCoder](https://atcoder.jp/contests/abc333) - 成績 ABCDE 5完 (1177) [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc333) ![[スクリーンショット 2023-12-17 12.19.36.png]] ABC333 でした。 私用があって今回は出られない予定でしたが、その私用が中止になったので出場しました。 結果はまずまず･･･ 現在のレートからすると良かったです。 E の実装に時間を使いすぎてしまったのが反省点。ここをもっと早く済ませられれば水色パフォーマンスに到達できたようです。 - A (灰) ･･･ `replicate n n` する - B (灰) ･･･ 正五角形の辺と対角線で分ける。同じ種類同士なら長さは等しい - C (灰) ･･･ $12$ 桁までの $11111\ldots$ を全部生成して、3つ組みの和を全て作りソート - D (茶) ･･･ 木DPで部分木頂点数を数えて、頂点 $1$ にぶらさがる部分木のうち最も大きいもの以外を削除対象とする。 - E (緑) ･･･ どのポーションを拾うかと、$K_{min}$ を求める計算を分離して2パスにすると楽。前から二分探索 or 後ろから貪欲 でした。F、G も少しトライしてみましたが撃沈でした 😅 今回も B、C で少し頭を使う問題でしたが、前回 ABC332 の反省を活かしてちゃんと考えきってから解くことができて沼らずに済みました。 ---- ## [A - Three Threes](https://atcoder.jp/contests/abc333/tasks/abc333_a) $N$ を $N$ 個繋げる。Haskell にはそのもの `replicate` 関数があるのでそれで数を生成します。 ```haskell main :: IO () main = do n <- getInt putStrLn $ map intToDigit $ replicate n n ``` ---- ## [B - Pentagon](https://atcoder.jp/contests/abc333/tasks/abc333_b) わ、幾何の問題かあと･･･思いましたが、よく観察すると簡単。 正五角形の辺と対角線とは長さが違いますが、頂点同士を結ぶ直線はその二種類しかないので二種類に分けて突合すればよいです。 辺を列挙するのはまあ、5種類しかないのでハードコードで良いでしょう。 順序があるのでそこは間違わないよう、丁寧にやります。 ```haskell distance a b = case (a, b) of ('A', 'B') -> 1 ('B', 'C') -> 1 ('C', 'D') -> 1 ('D', 'E') -> 1 ('A', 'E') -> 1 _ -> 2 main :: IO () main = do ss <- getLine tt <- getLine let [a, b] = sort ss [c, d] = sort tt putStrLn $ if distance a b == distance c d then "Yes" else "No" ``` ---- ## [C - Repunit Trio](https://atcoder.jp/contests/abc333/tasks/abc333_c) 真面目に repunits を順番に生成していくと沼りそうな問題だなあと思い立ち止まりました。 $N$ が最大でも $333$ と小さいのでおそらく上界を見積もればいい問題だと踏みました。 実は上界は入力例 $3$ に書いてましたね。私はそれと気づかず、ChatGPT に上界を教えて貰いました 😉 上界がわかればあとは全部生成して和を取れば OK です。 GPT にそのままコードも書かせたらそれっぽいのが出てきたのでそのまま提出しました。 (以下はその後自分で書き直したもの) ```haskell -- >>> repunits -- [1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111] repunits = map (\i -> fromDigits 10 $ replicate i (1 :: Int)) [1 .. 12] main :: IO () main = do n <- getInt let res = IS.toList . IS.fromList . sort $ map sum (replicateM 3 repunits) print $ res !! (n - 1) ``` ---- ## [D - Erase Leaves](https://atcoder.jp/contests/abc333/tasks/abc333_d) 削除できるのは葉だけ。木の頂点が葉になれる条件はその頂点の出次数が $1$ になったとき。 頂点 $1$ を削除するためには頂点 $1$ にぶら下がる何本かの辺を $1$ 本にまで削る必要がある。 ということは、ぶらさがっている部分木のうち一番大きなもの以外を削除すれば最適になりそう。 削除するのに必要な操作数は、部分木に含まれる頂点の数に等しいのは明らかなのでボトムアップの木DPで部分木の頂点数を求めます。 木DP は毎回同じようなコードを書くのでちょうど一週間前にライブラリ化してました。 それを使って実装したので、実装時間が短く済みました。盆栽重要です。 ```haskell main :: IO () main = do n <- getInt uvs <- replicateM (n - 1) getTuple let g = graph2 (1, n) uvs tree = treeGraph @UArray (g !) 1 (bounds g) (1 :: Int) values <- foldTreeBottomUp @IOUArray (+) tree let vs = g ! 1 xs <- traverse (readArray values) vs let m = maximumWithDefault 0 xs print $ sum xs - m + 1 ``` --- ## [E - Takahashi Quest](https://atcoder.jp/contests/abc333/tasks/abc333_e) いろいろ解き方はありますが、どのポーションを拾うかを決める計算と $K_{min}$ を求めるのを同時にやらないほうが簡単そう。 どのポーションを拾うかを決定したら $K_{min}$ は自ずと確定するのでまずはどのポーションを拾うかの計算をすることにフォーカスしました。 結論からいうと「後ろからみていって貪欲」にやるのが簡単です。後ろからみていくのは本番中にも考えましたがどうもそれを貪欲にやるのでいいのか自信が持てず。 自分はポーションの出現位置をポーションの種類ごとに順序付き集合で整理しました。 - 順序付き集合なら二分探索で、あるモンスターの出現位置よりも最も手前の索引を探すことができます。 - 先頭から見ていってモンスター $x$ が出現したら現在地点より手前で最も近い位置にあるポーション $x$ を拾います。 - 拾ったポーションはすぐ使用するので集合から削除する - ポーションが見つからないことが一度デモあったら、モンスターを撃退することができないのでその回は `-1` 確定 としました。 これで AC できるし速いのですが、実装は後ろから貪欲よりも工数がかかります。 特にポーションを使用したら集合から削除する ･･･ つまりインデックスの更新処理ですね。ここで MArray を使う必要がありましたが、途中まで実装をイミュータブルな Array でやっていて、実装の切り替えに時間がかかってしまいました。イミュータブルにやってたらそれでは駄目、と気づいてから実装を直すのに手戻りが大きいのは Haskell の弱点ですね 🥺 ```haskell solve g monsters = do mapM ( \(x, i) -> do s <- readArray g x case IS.lookupLE i s of Just j -> do writeArray g x (IS.delete j s) return (Just j) Nothing -> return Nothing ) monsters main :: IO () main = do n <- getInt xs <- replicateM n getTuple let xs' = zip xs [1 :: Int ..] uvs = map (\((_, x), i) -> (x, i)) $ filter (\((t, x), i) -> t == 1) xs' g = amap IS.fromList $ graph (1, n) uvs g' <- thaw g :: IO (IOArray Int IS.IntSet) let monsters = map (\((_, x), i) -> (x, i)) $ filter (\((t, x), i) -> t == 2) xs' res <- solve g' monsters if any isNothing res then do print (-1 :: Int) else do let s = IS.fromList (map fromJust res) ys = map (\(_, i) -> if IS.member i s then 1 else 0 :: Int) uvs let ks = scanl' f 0 xs' where f :: Int -> ((Int, Int), Int) -> Int f acc ((1, _), i) = do if IS.member i s then acc + 1 else acc f acc ((2, _), _) = acc - 1 f _ _ = error "!?" print $ maximum ks putStrLn . unwords . map show $ ys ``` 後ろから貪欲にやる場合は `mapAccumR` を使えば簡単です。 こちらの実装なら丁寧にやっていっても20分もかからないでしょう。 ```haskell main :: IO () main = do n <- getInt xs <- replicateM n getTuple let xs' = zip [1 :: Int ..] xs let res = mapAccumR f emptyMS xs' where f s (i, (1, x)) | memberMS x s = (deleteMS x s, Just i) | otherwise = (s, Nothing) f s (_, (2, x)) = (insertMS x s, Nothing) f _ _ = error "!?" if not $ nullMS (fst res) then print (- 1 :: Int) else do let pos = accumArray @UArray (||) False (1, n) $ map (,True) (catMaybes (snd res)) items = map fst $ filterOnSnd (\(t, _) -> t == 1) xs' let ks = scanl' f (0 :: Int) xs' where f acc (i, (1, _)) = if pos ! i then acc + 1 else acc f acc (_, (2, _)) = acc - 1 f _ _ = error "!?" print $ maximum ks putStrLn . unwords . map show $ map (\i -> if pos ! i then 1 else 0 :: Int) items ``` ---- ## 感想など D まで比較的スムーズに解くことが出来て、D を提出段階でパフォーマンス予測は 1500 over の水色でした。 E は少し時間を使いすぎてしまいましたが、まあ水色パフォーマンスぐらいその時点でもあるだろうとおもったら 1200 を切ってましたｗ E の後ろから貪欲に気付いている人は実装が早かったです。より簡単な解法がないか、あと3分吟味する癖をつけたいです。 最近、競技プログラミングの参考になればと思いスポーツとメンタルに関する本を3冊ほど読みました。 結果、いろいろと学びがありました。やはりアスリートの方々も本番で緊張して普段どおりの実力が出せない･･･ということに大なり小なり皆さん課題を抱えているようです。 なるほどなと思ったのは「本番で普段どおりに実力が出せない選手の多くは、技術課題 (スキル) に準備が偏り過ぎている」という下りです。安定感のある選手は技術だけでなく、意識 (感覚) や価値観 (挑み方や臨み方) に対する練習、準備にもバランス良く時間を投じているということでした。 これは思い当たる節があります。スポーツをやっていたときも「技術さえ身につけていれば本番もどうにかなるだろう」とたかをくくって、本番で自分が失敗するというケースを甘く見積もっており、身体が暖まる前の緒戦から強豪と対戦するときなどに安定を欠くということがよくありました。 本番で普段どおりの実力を出すためのトレーニングは技術スキルを身につけるのとは別系統の練習だと捉えて偏りをなくす必要があると思いました。 それから、いずれの書籍にも書いてあったのは「自己との対話」の重要性ですね。 何か失敗したときは、やはりそれを振り返ることが大事です。この自分との対話ができるかどうかにその後がかかっているというのはどの本にも書かれていました。またその対話において「何が駄目だったか」の原因論を追求しすぎると、できてない箇所や苦手なことばかりに意識が向いてかえって自己効力感が失われるともありました。自己効力感が失われると、失敗する自分をイメージする傾向が強まり、それが過剰な緊張につながってしまいます。 そこで振り返りは 1. 現状の確認 (何がどのぐらいできているのか?) 2. ありたい姿を確認 (本当はどうしたいのか) 3. そのためにできることを考えて実行する と、原因論ではなく目的論で考えると良いとのことでした。 「なんで失敗したか」ではなく「いまの自分がどういう位置にいるか」を振り返るわけです。要するに進捗確認ですね。 今回の ABC333 でいくと、緑 diff を含めて 5問解くことはできている。ただし周囲と比較すると、もっと早く実装できるとよいスコアに繋がりそう、その余地が大いにある。そのためにはより平易な解法を同時に検討することを癖にする。バーチャル参加などの模擬戦でそれを意識した練習をする･･･ということになるでしょうか。 反省をするのは大事ですが、その反省のコンテキストを原因論から目的論に切り替えることで自己効力感を下げるどころか高めることができる、ということです。 (ありがちな話ではありますが) 『大谷選手は父親と交換日記のようなも形で「悪かったとき、次になにをすれば課題を克服できるのか考えて行動に移す」ことを実行していた』とありました。 私もなんとなくでこうして ABC の振り返りを記録しつづけていすが、やはり自分と対話し続けるのは良いことだったんだなと思いました。また、振り返りにあたっては「現状確認」を意識してやっていくのがよさそうです。これからも続けていこうと思います。