geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC241 参加記録

ABC 出次数1の有向グラフ双方向連結リスト Loop 鳩の巣原理

コンテスト中AC:A〜C,E
コンテスト後、Dは自力AC

2022/07/06追記
Eの実装に単射や同値類という記載がありますが、誤りです。無視してください。

D - Sequence Query
E - Putting Candies

D - Sequence Query

実装が複雑になりましたが、自作双方向連結リストでACしました。

出現した整数の昇順ソートされた順序集合 $S$ (set)
初めて出現した整数が双方向連結リストに何番目に挿入されたかを記録するハッシュマップ $M$ (unordered_map)
双方向連結リスト $D$

を準備します。
それぞれにあらかじめ、 $-\infty , \infty$ を入れておきます(番兵)。
$D$ には昇順に値が挿入されていくように処理します。

具体的には、 $i$ 番目のクエリは以下のように処理します。

クエリ1 x

$x$ が $D$ に初めて挿入される場合、 $M$ に $D$ の何番目に挿入されたかを記録する。
$x$ より大きい最小の整数 $y$ を $S$ から二分探索で得る。
$y$ が $D$ の何番目に挿入されたかを $M$ から得る。これを $j$ 番目とする。
$D$ において、 $j$ 番目に挿入された値( $y$ )の後ろに $x$ を挿入する。

クエリ2 x k

$x$ より大きい最小の整数 $y$ を $S$ から二分探索で得る。
$y$ が $D$ の何番目に挿入されたかを $M$ から得る。これを $j$ 番目とする。
$D$ において、 $j$ 番目に挿入された値( $y$ )から後ろに $k$ 回辿る。この時、途中または最後に $-\infty$ にたどり着いた場合、-1とする。そうでない場合、辿った先を答えとして出力する。

クエリ3 x k

$x$ より大きい最小の整数 $y$ を $S$ から二分探索で得る。
$y$ が $D$ の何番目に挿入されたかを $M$ から得る。これを $j$ 番目とする。
$D$ において、 $j$ 番目に挿入された値( $y$ )から前に $k-1$ 回辿る。この時、途中または最後に $\infty$ にたどり着いた場合、-1とする。そうでない場合、辿った先を答えとして出力する。

multisetを使うとイテレータの増減だけでいいようです。今更ながら勉強になりました。

提出コード

E - Putting Candies

$i\rightarrow (i+A_i)\ mod\ N$ に移動すると考えます。
常に移動先は同じなので、鳩の巣原理によって、多くとも $N$ 回くらい移動すると、同じ場所が2回現れ、その後ループします。

あとは、 $K$ 回の移動で何回iから移動するかをカウントすれば答えを計算できます。

それを自作ライブラリ化してあったので、よければ参考にしてください。
実装はコンテスト後に少し修正してあります。

なお、この問題は各頂点が有向辺を1つだけもつグラフとも捉えられます。
そのようなグラフは閉路を１つだけ持ち、すべての頂点は閉路に属するか、閉路へ向かうように向きづけられています。
(ここで一応証明してみてあります。AtCoderの過去問の記事なのでネタバレ注意)

提出コード