# ABC355 振り返り
- [東京海上日動プログラミングコンテスト2024（AtCoder Beginner Contest 355） - AtCoder](https://atcoder.jp/contests/abc355)
- ABCD 4完 (895) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc355)
![[スクリーンショット 2024-05-26 9.54.39.png]]
![[スクリーンショット 2024-05-26 9.53.56.png]]
ABC355 でした。
E が黄色、F が青と後半が高難度であったため、実質的には A 〜 D の早解きができるか? という回になりました。
結果、私は C で時間をかけ過ぎてスコアはいまいち。
とはいえ C, D ともにきちんと考察しきって解くことはできたので、そこそこ満足しています。
- A (灰) ··· $A = B$ なら犯人は一意に定まらない。$A \ne B$ なら一意に定まる。ので if で切り分け
- B (灰) ··· $A$ に所属する値、$B$ に所属する値にそれぞれ印を付けてソート。連長圧縮して $A$ の印が $2$ 個以上連続するかをみる
- C (灰) ··· 整数をグリッドの $(i, j)$ に変換して、縦、横、斜めのカウンターをカウントアップ。都度 $N$ になったかを確認
- D (茶) ··· イベントソート。新しい区間が始まるたび、その時点で開いている区関の数を累積する
- E (黄, 🍊未完) ··· インタラクティブ問題。セグメント木?
- F (青, upsolve) ··· 重みが高々 $10$ なのを利用し、Union-Find を $9$ 個用意。全重み $10$ の最小全域木から重みがどれだけ下がるかを $9$ 個の Union-Find を利用し寄与数で考える?
でした。
C は Haskell を使いつつも手続き的プログラミングに振り切ったほうが良かったです。
この割りきりが足りず、必要以上に実装が難しくなってしまい、時間が掛かりました。
## [A - Who Ate the Cake?](https://atcoder.jp/contests/abc355/tasks/abc355_a)
犯人候補が $3$ 人がいる。目撃証言が $A, B$ の $2$ つある。
$A = B$ のときは犯人を $1$ 人に絞り込めないので $-1$ を出力。$A \ne B$ なら一意にきまるのでその数を出力、で OK です。
わざわざ IntSet を使ってオーバーキル気味ですが、集合に含まれない値を見つける、というときにこの実装を書くのが癖になってます。
```haskell
main :: IO ()
main = do
[a, b] <- getInts
print $ if a == b then (-1) else IS.findMin $ IS.difference (IS.fromList [1 .. 3]) (IS.fromList [a, b])
```
## [B - Piano 2](https://atcoder.jp/contests/abc355/tasks/abc355_b)
$A, B$ 二つの数列を繋げて昇順で並べたしたときに $A$ 由来の値が隣り合うことがあるかを判定する。
やり方は色々ありそうですが、$A$ と $B$ それぞれの値に色をつけてからソートし、そのソートされた結果から色を抜き出し連長圧縮して同じ色が $2$ 回以上続いているかどうか、で判定しました。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
let cs = map (,1 :: Int) as ++ map (,0 :: Int) bs
cs' = sortOn' fst cs
res = [k | (i, k) <- rle (map snd cs'), i == 1]
printYn $ any (>= 2) res
```
## [C - Bingo 2](https://atcoder.jp/contests/abc355/tasks/abc355_c)
$N \times N$ のビンゴのマスがあり、整数が系列 $A$ の順序に与えられる。
一番最初にビンゴするのは何ターン目か?
アルゴリズムはそれほど難しくなく、シンプルに実装できるかどうかが問われる問題です。
$N$ が最大で $2 \times 10^3$ になるので、グリッドが $10^6$ ぐらいの広さになる前提で考える必要があります。
$A_i$ が与えられるたびマス目全体をみてビンゴしてるかを確認するのは、マス目が最大で $10^6$ オーダーになるため、まったくもって間に合いません。
一方、ビンゴになるのは $A_i$ によってそのとき埋まったマスが載っている行、列、斜めのそれぞれ $N$ 個のマスのみが関与します。$N^2$ のマス目全部を見なくても良いでしょう。
ただし、その関係する行 / 列 / 斜めを見る方法でも、行や列のマス $N$ 個をその都度みるのでは、$A$ が $2 \times 10^5$ で、目が $N = 10^3$ あるので、$O(10^8)$ とかになってしまい、厳しい。
よく考えてみるとビンゴになっているかどうかは、同じ行 / 同じ列で埋まったマス目の個数だけわかっていればよい。そこでカウンターで数だけを管理します。これなら $A_i$ がマスに追加されるたびに更新 / チェックするデータはカウンター数のみで $O(1)$ になるため、間に合います。
答えとして要求されているデータは何かから逆算して、不必要な情報量を落としていくと計算量が削減できる... という基礎が問われる問題でした。
というわけで実装です。
系列 $A$ の値を一つ一つみながら行 / 列 / 対角線のカウンターを更新していくわけですが、手続きプログラミングに振り切ると実装がシンプルになりました。$(i, j)$ が対角線上に載ってるかどうかの判定が、慣れてないとすぐに出てこないですね。
```haskell
main :: IO ()
main = do
[n, _] <- getInts
as <- getInts
let ix = listArray @Array (1, n * n) $ range ((1, 1), (n, n))
rows <- newArray @IOUArray (1, n) (0 :: Int)
cols <- newArray @IOUArray (1, n) (0 :: Int)
d1 <- newIORef (0 :: Int)
d2 <- newIORef (0 :: Int)
for_ (indexed 1 as) $ \(k, a) -> do
let (i, j) = ix ! a
modifyArray cols i (+ 1)
modifyArray rows j (+ 1)
when (i == j) $ modifyIORef' d1 (+ 1)
when (i + j == n + 1) $ modifyIORef' d2 (+ 1)
x <- readArray cols i
y <- readArray rows j
z1 <- readIORef d1
z2 <- readIORef d2
when (n `elem` [x, y, z1, z2]) $ do
print k
exitSuccess
print (-1 :: Int)
```
Haskell 的にはこれでもシンプルなほうだと思いますが、手続きプログラミングに振り切ったとしても配列の書き換え命令やら IORef やらで記述量が多めです。
以下は @prd_xxx さんの Python の提出です。とてもシンプル、かつやっていることも明確で、良い実装だなと思いました。
```python
N,T = map(int,input().split())
A = list(map(int,input().split()))
rows = [0] * N
cols = [0] * N
d0 = d1 = 0
for t,a in enumerate(A):
a -= 1
i,j = divmod(a,N)
rows[i] += 1
cols[j] += 1
if i == j:
d0 += 1
if i+j == N-1:
d1 += 1
if rows[i] == N or cols[j] == N or d0 == N or d1 == N:
print(t+1)
exit()
print(-1)
```
一方の私は、本番では手続きプログラミングに振り切らずに、中途半端に関数型と命令型のデータ構造をまぜて実装したため時間がかかり、またミスでペナルティももらいました。
foldM を使ってミュータブルな MArray とイミュータブルな Set を同時に更新したり、カウンターの更新に際して MultiWay If で切り分けたり、何回目でビンゴをするかの結果をリストに集めたりとなかなか手間のかかる実装になってしまいました。
こういうときは無理にパラダイムを二つ混ぜずに、命令型に振り切ったほうがよいですね。
返り値を伴わない命令文と、返り値を必ず返す必要のある式とが混ざるとプログラムが複雑化しやすい 😖
F 問題の実装も似たような感じでした。
表現力は豊富だが型は厳密な、Haskell ならではの落とし穴、という感じではあります。
```haskell
main :: IO ()
main = do
[n, t] <- getInts
as <- getInts
let ix = listArray @Array (1, n * n) $ range ((1, 1), (n, n))
rows <- newArray @IOUArray (1, n) (0 :: Int)
cols <- newArray @IOUArray (1, n) (0 :: Int)
let cs = [(i, n - i + 1) | i <- [1 .. n]]
c = Set.fromList cs
s10 = Set.empty :: Set.Set (Int, Int)
s20 = Set.empty :: Set.Set (Int, Int)
center = if odd n then ((n + 1) `div` 2, (n + 1) `div` 2) else (-1, -1)
(res, _, _) <- foldForM ([], s10, s20) as $ \(acc, s1, s2) a -> do
let v@(i, j) = ix ! a
updateArray (+) cols i (1 :: Int)
updateArray (+) rows j (1 :: Int)
let (s1', s2') =
if
| v == center -> (Set.insert v s1, Set.insert v s2)
| i == j -> (Set.insert v s1, s2)
| Set.member v c -> (s1, Set.insert v s2)
| otherwise -> (s1, s2)
x <- readArray cols i
y <- readArray rows j
let z1 = Set.size s1'
z2 = Set.size s2'
let flag = elem n [x, y, z1, z2]
return (flag : acc, s1', s2')
case findIndex (== True) (reverse res) of
Just i -> print $ i + 1
Nothing -> print (-1 :: Int)
```
初手で制約を見誤ってナイーブに実装して TLE し、そこからこの実装に切り替えたこともありトータルでかなりの時間を溶かしてしまいました。
とはいえ、総崩れにならずにリカバリできたのは良かったと思います。ピンチのときも諦めない心が重要です。
## [D - Intersecting Intervals](https://atcoder.jp/contests/abc355/tasks/abc355_d)
$N$ 個の実数の区間が与えられる。そのうち $2$ つをチョイスしたとき、区間が被ってるケースは幾つある?
連続する複数区間の問題なので、区間スケジューリング問題、いもす法、しゃくとり法などいろいろな選択肢を頭がよぎりましたが、イベントソートでやるのが簡単そうだったので、それでいきました。
初手では座標圧縮 + いもす法が思いついたのですが、座圧 + いもす法で解けるときはだいたい、それ以外のよりシンプルな解法 ··· 典型的にはイベントソートでやると良いというのを何度か経験していたので 💡 ときたのでした。
区間が開く / 閉じるタイミングをイベントと捉えて、開くときに $+1$、閉じるときに $-1$ を割り当てます。
その上でイベント発生順に系列をソートする。イベントソートでは同じタイミングでイベントが発生することがあるのでそこは注意。
この問題の場合、同じタイミングでのイベントは閉じるイベントを優先します。
(Haskell ならタプルのソートは二値両方をみてくれるので、単にソートするだけで OK です)
そしてソートされたイベントを順に処理し、区間の開始タイミングで、その時点で開いている区間の数を累積します。
考え方としては寄与数ですかね。
$N$ 個の区間ごとに寄与数を考える。その区間が開くタイミングで、その時点で開いている数を数え上げたものが寄与数。
$N$ 個ある値の中から $2$ つの組み合わせを考えるという問題は ABC353 で幾つも出た $\sum\sum$ の計算のような構造を持っており、まず一方を固定して考える ··· 結果、寄与数に至るというのが典型的な思考パターンだと思います。
実装は、C 問題とはうって変わってこちらは `foldl'` を使ってイミュータブルにシュッと書けます。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let events = [[(l, 1 :: Int), (r + 1, -1)] | (l, r) <- xs]
events' = sort' $ concat events
let ans :: Int
(ans, _) = foldl' f (0, 0) events'
where
f (acc, open) (_, event)
| event == 1 = (acc + open, succ open)
| otherwise = (acc, pred open)
print ans
```
## [E - Guess the Sum](https://atcoder.jp/contests/abc355/tasks/abc355_e) (🍊未完)
インタラクティブ問題は苦手です。秒で諦めました 😭
克服せねばなりません
## [F - MST Query](https://atcoder.jp/contests/abc355/tasks/abc355_f)(upsolve)
連結グラフ $G$ が与えられる。
クエリで新たな重み付きの辺が次々と与えられるが、新たな辺を使ったときに最小全域木の総コストを下げられるか。
下げられるなら、どれだけ下がったかを計算する。
重み付きの最小全域木なので Union-Find を使ったクラスカル法が視野に入ります。
ただし Union-Find は一度追加した辺の削除や入れ換えは苦手としています。
より高度なデータ構造があるのか... ということが頭をよぎりますが、 Union-Find の辺の更新 / 削除が想起される問題は決まって、Union-Find を使いつつも何かしら工夫をすることで解けることが多いです。
この問題の特徴としては、与えられる辺の重みが高々 $10$ と小さいことですね。(本番でこれを見逃してました)
これを使ってどうにかしろ、といわんばかりの制約です。
···で、実装が単純だったので解説をみながら upsolve はできたものの、まだその動きがちゃんと理解出来てません。
- Union-Find を重み $1 \ldots 9$ の $9$ 個用意
- スタートは全ての辺の重みが $10$ の全域木を考える
- そこからグラフ $G$ の辺とクエリを区別に辺をその多層になっている Union-Find に追加しながら、都度総コストがどれだけ下がるかを計算する
ということをやってるのですが、どういう理屈なのか説明しろと言われるとよくわからない 😅
これ以上考えても難しそうなのでいったん保留。
D を解いた時点で 20分強時間があったので F 問題で C での遅れを取り戻そうと奮闘しましたが、青diff 上位問題ということもあり、さすがにそんな簡単にはいきませんでした。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
uvs <- replicateM (n - 1 + q) getWeightedEdge
ufs <- listArray @Array (1, 9) <
gt; traverse (\_ -> newUF @IOUArray (1, n) (-1)) [1 .. 9]
acc <- newIORef ((n - 1) * 10)
res <- for uvs $ \((u, v), w) -> do
for_ [w .. 9] $ \i -> do
same <- isSame (ufs ! i) u v
unless same $ do
unite (ufs ! i) u v
modifyIORef' acc (+ (-1))
readIORef acc
let ans = drop (n - 1) res
for_ ans print
```
## 感想など
C で沼ってしまいましたが、周囲の人たちと同程度の 4完はできたので、スコアはともかく出来はまずまずかなと思っています。
ABCD 各問題の難易度が灰灰灰茶ですが、体感では灰灰茶緑ぐらいかなと思いました。
AI 提出の影響で全体的にその辺が揺らいでる感じがします。
もとい、 E や F がもう少し簡単であればそれを解いて C の遅れを挽回といきたかったわけですが、崖になってると挽回が難しいですね。
この辺は時の運かなと思います。
今回の反省としては、実装時に命令型のパラダイムで行くか、関数型のパラダイムでいくか、あえてハイブリッドでいくかの判断にメリハリをつけるべき、ということですね。
MArray や Union-Find などの作用を伴う実装を使うときは、命令型に振り切るかどうかの判断を一度挟むようにしていこうと思います。
どうも IORef を使うのを躊躇って、無駄に複雑化させてることが多い気がします。
話は変わって、ここ一週間の練習としては、ADT Hard を休みにして PAST の過去問をやってます。
6月になると次の PAST の試験あるんですかね? システムがよくわかってませんが。
それを受験することも視野に入れて、やってみてます。
序盤の未知の問題をスラスラと解けると、気づかないうちに結構実力がついたなーということを実感できて楽しいです。
但し、その序盤の問題も ABC の普段の問題に比べてすこし歯ごたえがありますね。ただの作業にならないのは良いところです。
I, J, K, L あたりの問題になってくると、おそらく緑後半から水色ぐらいの難易度がありますが、考察実装も含めいまの自分にちょうどいい難易度で面白いです。
ひとまずこの調子で、過去問を K or L あたりまで全部解いてみようかなと思います。
![[スクリーンショット 2024-05-26 13.28.26.png]]