# ABC321 振り返り
- [サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321） - AtCoder](https://atcoder.jp/contests/abc321)
- 成績 ABD 3完 (933) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc321)
- 前回 [[ABC320 振り返り]]
ABC321 でした。少し前進した感があってほっとしました。
![[スクリーンショット 2023-09-24 7.57.42.png]]
- A はやるだけ。
- B は最初 $O(1)$ で解こうとしてややはまりかけましたが、よく制約を見て全探索に切り替えて AC
- C はすぐにはわからなかったので、ここ数回の反省もあり飛ばす
- 落ち着いて D を解く
- その後 C に戻るも、60分かけても解くことができず。上界を見積もる、問いう発想に至れなかった。
という感じでした。
C は 321-like 数の上界を考えれば解法が見えた問題で、それを知ったら「なんだあ」という感じですが、コンテスト中はやはり視野が狭まっているのか「上界を考える」という典型考察に至ることができませんでした。
とはいえ、ここ何回かは C でつまづき慌ててしまい D 以降崩れるというパターンを繰り返していましたが、今回はそこから立て直すことができたのはよかったと思います。
D 問題は緑 diff のようですが、自分としてはあまり難しいと感じることもなく解くことができました。ここ最近の訓練の成果が出ていると思います。
スランプからの脱出が見えてきています。
----
## [A - 321-like Checker](https://atcoder.jp/contests/abc321/tasks/abc321_a)
隣の数と比較して単調減少が続いているか調べる。
この辺は Haskell なら `zipWith` でシュッと書けます。
```haskell
main :: IO ()
main = do
s <- getLine
let xs = map digitToInt s
result = all (== True) $ zipWith (>) xs (tail xs)
putStrLn $ if result then "Yes" else "No"
```
[提出 #45890638](https://atcoder.jp/contests/abc321/submissions/45890638)
----
## [B - Cutoff](https://atcoder.jp/contests/abc321/tasks/abc321_b)
$N$ ラウンド目に取れるスコアは $0$ 以上 $100$ 以下しかないので、全探索でその全てに対してスコアを仕様通りに計算する。
はじめ全探索ではなく「最小値と最大値を取り除いて、その状態で幾つ取れば $X$ を満たせるか...」と計算してたのですが、サンプルがうまく通らず。
問題を改めて見直したところ、先の制約をみて全探索に切り替えました。
B にしてはやや難し目の問題ですね。
```haskell
f as i = do
let as' = i : as
a = minimum as'
b = maximum as'
sum as' - a - b
main :: IO ()
main = do
[n, x] <- getInts
as <- getInts
let xs = [(i, f as i) | i <- [0 .. 100]]
print $ case filterOnSnd (>= x) xs of
[] -> -1
xs -> fst (head xs)
```
[提出 #45829204](https://atcoder.jp/contests/abc321/submissions/45829204)
---
## [C - 321-like Searcher](https://atcoder.jp/contests/abc321/tasks/abc321_c) (upsolve)
残念ながら解けず!
ポイントが分かれば3行で解ける問題でした。
321-like Number は桁ごとに単調減少する数字ですが、その上界を考えると $9876543210$ であることがわかります。それ以上の数は作りようがない。
321-like Number すべてを合計しても大した数にならないので、全て生成してソートしてしまえばいい、というのが答えでした。
時間的に余裕もあったしナイーブに実装した上で全部値を生成して出力してみるとか、そういう工夫でも途中でしてみれば気づくことができたかなあと思うのですが、紙の上で延々と唸っていたためそういう発想に至らず。紙の上で考えていてもわからないときは、発想を変える必要がありますね。
```haskell
main :: IO ()
main = do
k <- getInt
let xs = map (fromDigits 10) $ filter (not . null) $ subsequences [9, 8 .. 0]
print $ head . drop k $ sort xs
```
[提出 #45890638](https://atcoder.jp/contests/abc321/submissions/45890638)
----
## [D - Set Menu](https://atcoder.jp/contests/abc321/tasks/abc321_d)
二分探索と累積和の組み合わせ。
$A$ を固定して $B$ を二分探索します。
ただしこの問題の場合、累積和そのものを二分探索すると答えを求めることができません。
累積和を取らない状態でソート済みの $B$ を探索して、境界を引く位置を決める。
その後、$A$ と $P$ は寄与数で総和を出し、$B$ の総和は累積和で出します。
```haskell
main :: IO ()
main = do
[n, m, p] <- getInts
as <- getInts
bs_ <- getInts
let bs = sort bs_
let ba = listArray @UArray (1, m) bs
s = listArray @UArray (1, m + 1) $ scanl' (+) 0 bs
xs = [(a, ng) | a <- as, let (ng, _) = bisect (0, m + 1) (\i -> a + ba ! i >= p)]
xs' = [s ! (r + 1) + p * (m - r) + r * a | (a, r) <- xs]
print $ sum xs'
```
[提出 #45851334](https://atcoder.jp/contests/abc321/submissions/45851334)
----
## 感想など
前回 C 問題でつまづいたときに慌ててしまったことを振り返り、何が良くなかったのかを整理しました。
### boilerplate コードの整備
それまで自分で作ったライブラリ関数は、あらかじめテンプレートに記載するなどはしておらず、必要になった時につどソースコードを検索してコピペして提出用のコードに貼り付けていました。
が、慌てている状況では、視野が狭まることもあって、こういう無駄な作業を繰り返すだけでも消耗してしまいます。
また、その時点での実装がダメで実装を切り替える時に、ライブラリから目的のアルゴリズムを探して貼り付け直すという作業も無駄でした。
というわけで、Haskell 諸先輩方同様にテンプレートを整備して、わざわざコピペしてきたりモジュールを import したりすることなしにノー準備で、自作関数を使える環境を整えました。テンプレートが肥大化してくるとソースコード自体がごちゃつくのが嫌ですが、VSCode の Explicit Folding という拡張機能で、boilerplate の部分は畳み込んで必要な時以外は視界に入らないようにしました。
たかがこの程度のことですが、実際にこの整えた状況で問題を解いてみると、余計なことに認知コストが取られない効果は大きく、想像以上の効用がありました。
なお、Union-Find やセグメント木などのある程度実装ボリュームのあるコードはテンプレートに載せていません。この辺も載せるかどうかは、検討中です。
確か AtCoder の送信コード数はサイズに制限がありましたね。
### メンタル分析
あいも変わらずコンテスト本番は緊張してしまうのですが、会社の競プロ部の同僚と雑談していたら中には全然緊張しないという人も一人二人いて、この差はなんだろうと考えました。
よくよく話を聞いてみると、緊張しない御仁はチャレンジャーマインドで「失敗しても構わない」というか「うまくいかないのが当然」と思っているような印象を受けました。
他方、自分の緊張の原因は何かと掘り下げていくと、どうやら失敗することを怖がっているのが原因ではないかと思い至りました。
もっといえば、失敗した自分を人に見られるのが嫌。つまり他人の目を気にしているわけです。
あまりそういう自己認識はなかった、あるいは見ないようにしていた気がしますが、冷静に分析するとやっぱりそこだなあと。
歳をとったこともあり、失敗した自分を曝け出すというのが恥ずかしいとか、そういうプライドが肥大化していたようです。
別に AtCoder のコンテストで失敗したところで失うものがあるわけでもない (レートは下がりますが、それが何か生活に影響を与えるわけでもない) ので、なんで失敗するのが嫌かといえば、失敗した自分を自分で受け入れるコストが高いと思っているとか、人に失敗したことを言い訳するコストが高いとか、そういうことが心理としてあるんじゃないかなあと。
···というわけでそこが緊張の原因だと仮定して、これからは「別に失敗してもいいや」と思うことにしました。
前回 2完でうまくいかなかったことで、開き直ってそう思えるようになった、というのはあるかもしれません。
今回も仮に1完や2完で終わったとしても「失敗しました!」と言えばいいだけの話だ、と思って臨んだら随分と楽になった気がします。
毎回この自己暗示をかけるのはいいかもしれません。