ABC302に出た。

A: ceil(A/B), AとBはくそでかいことに注意

B: 全マスを始点にして8方向全探索

C: 順列全探索

D: Aを全探索し、各場合についてにぶたんで最も良いBを探す

E: 孤立頂点の数だけ差分更新すればあとは愚直にやってよい。辺の数は高々Q本であり、各辺について変更操作は「追加する」「削除する」しかしないので全体$O(Q)$で済む。

F: 整数と集合をそれぞれ頂点としたグラフを作ってBFS

G: 解けず。2サイクル→3サイクル→4サイクルの順で解決すると通る。競プロフレンズ氏の解説が分かりやすい。

アライグマ「G問題は貪欲なのだ！　2個swapを直すと1手で2個正しい位置に移せるのだ。3個rotateを直すと2手で3個、4個rotateだと3手で4個なのだ。だから効率がいい方からやるのだ！」 pic.twitter.com/3hVURbwhFp

— 競技プログラミングをするフレンズ (@kyopro_friends) May 20, 2023

noshi91氏によれば数が5以上だと無理らしい。そこまで踏まえて最大を4としていたのか。

G: できるだけたくさんのサイクルに分解する問題になるわけだが、一般に長さ 1, 2 のサイクルは即座に取り除いて良い。長さ 3 のサイクルは一般には取り除けないのだが、取り除けないのは 3 辺が相異なるサイクルとして使われている場合で、少なくとも 6 頂点ないと起きない。

— 熨斗袋 (@noshi91) May 20, 2023

Ex: 解けず。木ではなく配列の場合が解けて、なおかつ1長い配列の場合と1短い配列の場合が高速に解ければあとはDFSするだけだなと思ったのだが、前提となる配列の場合の問題が解けなかったので無理だった。どうやらグラフで定式化してUnionFindを上手く使うと解けるらしい。