# ABC337 振り返り
- [トヨタ自動車プログラミングコンテスト2024#1（AtCoder Beginner Contest 337） - AtCoder](https://atcoder.jp/contests/abc337)
- 成績 ABCD 4完 (855)
![[スクリーンショット 2024-01-21 11.27.11.png]]
![[スクリーンショット 2024-01-21 11.26.10.png]]
ABC337 でした。
4完できて自分のレート帯的にはこんなもんかなと思いつつ、ペナルティ x 5 がスコアの足をひっぱってしまいました 😅
- A (灰) ··· 高橋くんと青木くんのスコアを別々に sum する
- B (灰) ··· 圧縮してできた文字列が条件に当てはまるか比較。落とし穴があるので注意
- C (灰) ··· グラフで隣接した辺を辿る
- D (茶) ··· 行と列を独立に考える。`x` で split して累積和でやりました
- E (緑) ··· (upsolve) インタラクティブ問題。「毒入りワイン判定問題」という有名問題らしい
という問題セットでした。
ペナルティを重ねたこともあってスコアは良くなかったですが、4問解けた & 考察はちゃんとできていたしで、まあまあやれたかなという実感はあります。スコアはただの結果、後からついてくるもの、と思っておきましょう。
----
## [A - Scoreboard](https://atcoder.jp/contests/abc337/tasks/abc337_a)
タプルで入力を受け取り fst と snd を別々に sum して比較する。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let (a, b) = bimap sum sum (unzip xs)
putStrLn $ case compare a b of
EQ -> "Draw"
GT -> "Takahashi"
LT -> "Aoki"
```
----
## [B - Extended ABC](https://atcoder.jp/contests/abc337/tasks/abc337_b)
問題文を良くよむ必要があります。「空文字列も拡張文字列」ということは `ABC` になったものだけでなく、`AC` や `BC` なども拡張文字列になります。そこをちゃんと考えてなくてパッチに次ぐパッチで 3ペナ貰ってしまいました。
```haskell
solve x
| x == "" = True
| x == "ABC" = True
| x == "AB" = True
| x == "BC" = True
| x == "AC" = True
| x == "A" = True
| x == "B" = True
| x == "C" = True
| otherwise = False
main :: IO ()
main = do
s <- getLine
let xs = rle s
x = map fst xs
printYn $ solve x
```
ちなみにこの拡張文字列というのは、言い換えれば単調増加列になっているということなので、これでいいそうです。
「系列が最初から単調増加列になっているか」のチェックはソートで比較。ときどき見る解法ですが、なかなかぱっと思いつきません。
```haskell
main :: IO ()
main = do
s <- getLine
printYn $ sort s == s
```
----
## [C - Lining Up 2](https://atcoder.jp/contests/abc337/tasks/abc337_c)
グラフの先頭と、各頂点の親がわかっている。
グラフ探索後に得られる、親の頂点がわかっている状態での経路復元の問題ですね。
いろいろやり方はありそうですが、私は配列を逆転させて先頭から辿りました。
B で WA が出るたび C といったりきたりしながらやってたので、大変でした 😅
本番中では Haskell だと WJ 待ちが長いこともあって、C 実装し始めたかと思うと B の WA が確定するみたいなのの繰り返しで、心臓に悪かったです。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let s = succ $ fromJust (findIndex (== -1) as)
let as' = listArray @UArray (1, n) as
invIndex = accumArray @UArray (flip const) 0 (-1, n) $ map swap (assocs as')
res = take n $ iterate (invIndex !) s
putStrLn . unwords . map show $ res
```
なお、誰からも参照されてない頂点が末尾なので、それをみつけた上で、そこから逆にっていくというのでも良かったですね。
こちらのほうがスタート地点からゴールまでの経路を復元するという普段通りの実装なので、良かったかもしれません。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let t = IS.findMin (IS.difference (IS.fromList [1 .. n]) (IS.fromList as))
let as' = listArray @UArray (1, n) as
path = takeWhile (/= -1) $ iterate (as' !) t
putStrLn . unwords . map show $ reverse path
```
----
## [D - Cheating Gomoku Narabe](https://atcoder.jp/contests/abc337/tasks/abc337_d)
解法をたてる道筋はしっかり考察できてよかったのですが、実装で沼り散らかしました。
- グリッドがそこそこ広いので二次元で一度に考えると難しそう。こういうときはまず一次元に単純化して考えます
- 例えば $K = 6$ で `....o...oox...` のとき、答えは $3$ です。`....[o...oo]x.` の区間を使うのが最適
- `x` が含まれないところの長さが関心事なので `x` で `split` し、長さが $K$ に満たない部分列を捨てて更に問題を単純化します
- 「`....o...oo` の中の連続する長さ $K$ の部分列のうち、どこからどこを選べば最適か」となりました
ここまで分解できると典型問題の匂いがしてきます。累積和、二分探索、しゃくとり法など色々解法がありそうです。
自分は累積和でやりました。
これで1次元の方針が立ちます。斜めや区画はみる必要がないので、2次元に拡張した際に特別考慮する事は無いですね。
というわけで、行と列を別々に計算すれば OK。
···方針は完璧でしたが、境界条件周りの実装でミスして、デバッグでもなかなか気づけず苦労しました。
慌てて実装すると良くないですね。2ペナで $10$ 分無駄にするよりは、結果的には、ゆっくり丁寧に実装したほうが良かった気がします。
```haskell
f k s =
[ k - (cs ! (i + k) - cs ! i)
| (l, s') <- [(l, s') | s' <- split (== 'x') s, let l = length s', l >= k],
let cs = listArray @UArray (1, l + 1) $ scanl' (\acc c -> if c == 'o' then acc + 1 else acc) (0 :: Int) s',
i <- range (bounds cs),
inRange (bounds cs) (i + k)
]
main :: IO ()
main = do
[h, w, k] <- getInts
rows <- replicateM h getLine
let cols = transpose rows
xs = concatMap (f k) rows
ys = concatMap (f k) cols
print $ minimumWithDefault (-1) (xs ++ ys)
```
----
## [E - Bad Juice](https://atcoder.jp/contests/abc337/tasks/abc337_e)
苦手なインタラクティブ問題でした。
どうやら有名問題だったようで、グーグルで検索すれば解法が出てきました。
- [どうしてもわからない問題があります。ワインが千本あります、その中の一... - Yahoo!知恵袋](https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14115376614)
これのベストアンサー。本番中にはグーグルで調べるという機転は働かず。二分探索かなあ、ビット操作かなあ、とかいろいろ考えてるうちに時間切れでした。
ちなみにダメ元で ChatGPT に実装させてみたらそれっぽい実装がでてきたので試しに送信してみましたが TLE + WA でした。
あとあと見たらだいたい方針はあっていて、細かいところで間違えてました。結局、AI に指示する側が解法をわかってないと、根本的に間違えてるのか、修正すれば通るのかを見通すことができません。なんだか仕事の話みたいです。
もとい以下解法です。
$N$ 本のワインに通し番号を振る。それを2進にする。$7$ 本あるなら $3$ ビットで表現できて
```
1 001
2 010
3 011
4 100
5 101
6 110
7 111
```
となります。(取りあえず簡単のため 1-based で考えていますが、あとで 0-based になおします。)
このビットのリストを、縦に、列単位でみます。`transpose` ですね。
```
1234567
----------------
1人目 ··· 1010101
2人目 ··· 0110011
3人目 ··· 0001111
```
これが各人が飲むワインです。
- 例えば 7 が毒入りなら、3人全員死にます。
- 2 が毒入りなら、2人目しか死にません。
- 5 が毒入りなら、1人目と3人目が死にます。
というように、どのワインに毒が入っていたかで誰が死ぬかが一意に定まります。なんだか物騒な話ですが。
必要な人数は $N$ をビットで表現できるビット数ですね。
そして結果は `001` や `101` などのように誰が死んだかがビットで返ってきます。これは自分が送信した入力の順序に依存しているので、入力の大小関係を整列した状態で送信、それを (入力を昇順 / 降順どちらで送ったかを考慮しつつ) $2$ 進で解釈して $10$ 進に直せば答えになります。
というわけでビット演算でもいいし、2進のデータ列を作って `transpose` でもいいので上記の構造を作って送信して、レスポンスを 2進解釈すればいいわけですが、一つ落とし穴があり、$1$ 本目のワインを $0$ で表現する必要があります。この問題では $M$ 人を最も小さい数に収める必要があるので `0000000` も使う必要があります。
インタラクティブ問題にはテストケースがないこともあり、ここに気づけるかどうかが結構難しかったですね。
```haskell
main :: IO ()
main = do
n <- getInt
let m = log2 n
rows = [replicate (m - length ds) 0 ++ ds | ds <- map (toDigits 2) [0 .. n - 1]]
cols = [[i | (i, x) <- zip [1 .. n] col, x == 1] | col <- transpose rows]
print m
hFlush stdout
for_ cols $ \col -> do
putStrLn . unwords . map show $ length col : col
hFlush stdout
response <- getLine
let x' = fromDigits 2 $ map digitToInt response
print (x' + 1)
exitSuccess
```
---
## 感想など
今回は緊張はあまりせず気楽に出来て良かったです。
金曜日の夜ぐらいから ABC337 のことは忘れて、エルデンリングを延々とやってました。夕方に昼寝をして起きて FitBox にのって30分ほど汗を流し、あとは時間まで本を読んだりしてました。
金曜日ぐらいから ABC のことを意識してしまうと、土曜の朝から頭から離れなくなって問題を解いたりしてるうちに緊張感が高まってしまうので、金曜日の夜以降は精進しないことにしました。
よくスポーツ選手が、競技のことばかり考えてリフレッシュできずに本番で力を発揮できないみたいな話があります。自分もそれに近い状態だったかもしれないなーと思い、定期的に休みを挟んだほうが良いのかもしれないですね。
昔から何かに夢中になるとそればっかりやってしまう... 過集中する傾向が強いので、適度に休みを挟むように意識したいと思います。