ABC377 振り返り - Obsidian Publish

# ABC377 振り返り - [トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377) - AtCoder](https://atcoder.jp/contests/abc377) - ABCDE 5完 (1552) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc377) ![[スクリーンショット 2024-10-27 7.58.05.png]] ABC377 でした。青難易度の E を解いてパフォーマンス 1552 で過去最高の成績になりました。 - A (灰) ··· ソートして `ABC` と比較 - B (灰) ··· 何も置かれてない行数 $\times$ 何も置かれてない列数 - C (灰) ··· 余事象。ナイトが影響を与えるマスを全部生成してユニークをとって数える。それをマスの数 $N^2$ から引く - D (緑) ··· $l_i = (1, 2, \ldots, M)$ ごとに考える。$l_i$ からみて条件を満たす $r_i$ はどこまで伸ばせるか? が分ければ解ける - E (青) ··· 順列をぐるぐる回るサイクルが系列の中に複数あるので分解し、サイクル長を求める。遷移はダブリングのように$2$ の冪乗。サイクルの長さで mod とる E は遷移を繰り返したときに循環するという構造を予め知っていたのが大きかったです。どちらかというと E よりも、D に手こずりました。 ## [A - Rearranging ABC](https://atcoder.jp/contests/abc377/tasks/abc377_a) `ABC` は辞書式順に並んでいる文字列なので、入力も同様にソートして `ABC` となるかを調べると良いです ```haskell main :: IO () main = do s <- getLine printYn $ sort s == "ABC" ``` ## [B - Avoid Rook Attack](https://atcoder.jp/contests/abc377/tasks/abc377_b) チェス盤にルークが予め置かれている。ルークの影響のない空きマスが何個あるか。ルークは将棋でいうところの飛車で、自身が置かれたマスと同じ行、列に影響を与える。マスが狭いので、各コマの影響するマスを塗りつぶす、みたいな実装でもいけそうですが、面倒。コマがおかれていない行、コマがおかれていない列をそれぞれ数えて積をとると答えになります。 ```haskell main :: IO () main = do rows <- replicateM 8 getLine let hs = countBy (notElem '#') rows ws = countBy (notElem '#') $ transpose rows print $ hs * ws ``` ## [C - Avoid Knight Attack](https://atcoder.jp/contests/abc377/tasks/abc377_c) 今度はチェス盤にナイトが予め置かれている。ルークの影響のない空きマスが何個あるか。ナイトは自身がおかれたマスと、少し先の周辺 $8$ マスに影響を与える。 B 問題と違って今度は盤面が $10^9 \times 10^9$ もあるので、シミュレーションはできない。が、コマの数は $M \leq 2 \times 10^5$ 程度で、各コマ $9$ マスにしか影響を与えません。盤面ではなくコマの方に着目して、各コマが影響を与える $9$ マスを具体的に生成しユニークを取る。これでナイトの影響下のマスの数がわかります。盤面の範囲外まで数えてしまわないよう、注意。あとは余事象で考えて全体のマスの数 $N^2$ からそれを引く。なお、ユニークを取るのに Set を使うことができますが、実際やってみると遅いです。この問題は $4$ 秒制限問題なのでそれでも通ります。 Haskell の Set, HashSet, IntSet あたりは永続データ構造になっている分、こういう大量のデータをユニークを取ろうとすると少し時間を要します。自分は座標圧縮の実装で Unboxed Vector を使って高速にユニークをとる実装をしてあるのでこれを使います。内部的にはイントロソートでソートした上で隣接する重複要素を `VU.uniq` で削る、ということをやってます。 ```haskell main :: IO () main = do [n, m] <- getInts vs <- replicateM m getTuple let ix = index ((1, 1), (n, n)) let xs = [ ix u | v <- vs, d <- [ (0, 0), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1) ], let u = d + v, inRange ((1, 1), (n, n)) u ] (as, _) = zaatsuRank @UArray 1 xs ans = n * n - numElements as print ans ``` ## [D - Many Segments 2](https://atcoder.jp/contests/abc377/tasks/abc377_d) この問題では、与えられた各区間 $[L_i, R_i]$ を完全には含まないような区間 $[l, r]$ の個数を求めます。区間スケジューリング問題のような問題だなあと眺めていましたが、それだとなかなか解法に辿り着かず。 $l_i = (1, 2, \ldots, M)$ の $l_i$ を固定して、$l_i$ ごとに問題を分割して解く方針で考えます。まず、与えられた区間で指定されている $L_i$ からどこまで条件を満たす区間を右に伸ばせるかは $L_i$ と結びついた複数の $R_i$ のうち最小のものになることがわかります。ある $L_i$ に対して複数 $R_i$ が紐付いているとき、最小以外のものを選ぶと最小区間を包含した区間になってしまうからです。下図の上の例。この問題では与えられた区間に含まれていない $l_i$ も考える必要があります。これは下図の下の例。この $l_i$ からみると次の $L_i$ が伸ばせる $R_i$ までが条件を満たすことになります。これは終端から始点に向かって累積 min をとっていくと、この $l_i$ に対する $R_i$ が求まります。 ![[IMG_1968.jpeg|600]] というわけで - $l_i = 1 \ldots M$ のリストを考える - $L_i$ ごとに $R_i$ をまとめて $R_i$ の最小値をとる - 右から累積 min を求めるこれで $(l, r)$ の組みがわかるので、あとはその区間長 $-1$ を求めると、条件を満たす部分の長さの総和が求まります。結構むずい。本番では手続き的に実装してややごちゃつきましたが、きちんと考察すると accumArray と scanr による右からの累積 min でよいことがわかり非常にシンプルな実装になります。ここまで本番中に考察できればなおよかったです。 ```haskell main :: IO () main = do [n, m] <- getInts vs <- replicateM n getTuple let xs = accumArray @UArray min (m + 1) (1, m) vs rs = scanr min (m + 1) (elems xs) res = [max 0 (r - l) | (l, r) <- indexed 1 rs] print $ sum' res ``` ## [E - Permute K times 2](https://atcoder.jp/contests/abc377/tasks/abc377_e) $P_i$ を $P_{P_i}$ で更新を繰り返すという、循環置換の問題です。群論の本などを読んでいるとときどき出てきます。同じような遷移を $10^{18}$ などシミュレーションが難しい回数分繰り返す、というのでダブリングの雰囲気があります。ダブリングのライブラリで一発で解けるかと思いきや、状態遷移が静的でなく、遷移のたびに遷移テーブル $P$ が更新されてしまうのでそうはいきません。が、ダブリングのような操作になっているというのは重要なポイントです。もとい、シミュレーションすると、数列 $P$ の中に同じ循環をぐるぐる回っているサイクルのグループが複数ある構造になっているのがわかります。グラフ的にいうと、この遷移は Functional Graph になっていてかつ順列です。各頂点に出次数と入次数がそれぞれ1つずつ存在するため、任意の頂点から出発すると、その頂点に必ず戻ってくる閉路を形成します。さらに、Functional Graph の性質上、連結成分ごとに1つの閉路が存在することから、連結成分はすべて閉路になっている、という構造です。この周期性をうまく使い、循環のサイクル (グラフでいうなら閉路) ごとに問題を分割します。各サイクルの長さを $m$ とすると、循環は $\bmod m$ で周っている。そしてダブリングのような操作になっていることから $i$ から $k$ 回操作すると、$2^K$ 進みます。これを $\bmod m$ 空間で合同計算すれば、$i$ にあったものが $k$ 回操作したのち位置する $i'$ がどこかは分かります。本番ではサイクルをみつけるのに DFS で実装しましたが、グラフでモデル化すると Functional Graph なので閉路抽出には強連結成分分解 (SCC) が使えて楽です。 ```haskell main :: IO () main = do [n, k] <- getInts ps <- getInts let g = graph (1, n) $ indexed 1 ps css <- sccM g let res = [ [(x, xs ! i') | (i, x) <- assocs xs, let i' = (i + powMod 2 k m) `mod` m] | vs <- css, let m = length vs xs = listArray @UArray (0, m - 1) vs ] printList $ elems (array @UArray (1, n) $ concat res) ``` ## 感想など本番で E の青 diff を解いて、パフォーマンスも青パフォに近い 1500 オーバーと良い出来でした。全体で 3桁順位を取ったのは初めてです。レートは Highest には届きませんでしたが +60 で 1120 となり、ここ最近の大敗分を取り戻しつつあります。大敗するときの反省点としてありがちなのですが、十分に考察をする前に実装にとりかかりその間違った解法に執着してしまうというケースが多いので、今回はどの問題も早解きよりは考察をしっかりやることを意識しました。これがうまくいったようです。前回 ABC376 に出られなかったのをバーチャル参加で解いたときに、バーチャル参加なら焦らずやればいいかと考察集めでやったらわりとうまくできたので、その感じを本番でも意識してみました。特に D 問題は区間スケジューリング問題だと決めてかかって取り組む、ということをせずに考察しきれたのが良かったと思います。 E も既存のダブリングの実装をごちゃごちゃいじるとかせずにまずはナイーブに実装しシミュレーションで周期の構造を確かめたりと、よい考察ができました。始めたばかりのころに比べると、問題の読み取り、考察、その後の実装すべての速度が上がっているので気持ちでは「よく考察しよう」と思っていたとしても、実際にはそこそこ早解きになっています。時間をかけて考察したかどうかの実態よりも、心の中の優先順位として、考察することを上に持ってくる、ということが大事だと思いました。引き続きがんばります。