2023-12-17

AGC052 - B Tree Edges XOR

AGC050-Bを解いた

問題

重み付きの木(辺 $i$ が結んでいるのは頂点 $u_i$ と $v_i$ 、重みは $w _ {i} ^ {1}$ )が与えられる。どれか一つ辺を選んでその辺と頂点を一つ共有するすべての辺について重みを選んだ辺の重みとの排他的論理和に置き換える。目標の重み( $w _ {i} ^ {2}$ )を達成するのは可能か?

解法

辺に対する操作は扱いにくいので各頂点に数( $A_i$ 、最初は全部 $0$ )が書いてあるとしてみて、辺の重みを $A _ {u _ i} \oplus A _ {v _ i} \oplus w _ i ^ 1$ として表す。すると、辺 $i$ に対する操作は「 $A _ {u _ i}$ と $A _ {v _ i}$ をswapし、それぞれを $w _ i ^1$ との排他的論理和に置き換える」と言い換えられる。ここで最終的にすべての $i$ ( $1 \leq i \leq N$ )について $A _ {u _ i} \oplus A _ {v _ i} = w _ i ^2$ を満たす必要があり、 $A$ の総xorが常に $0$ であることと併せて考えれば最終的な $A$ ( $A'$ と置く)は一意に定まる(ここで $N$ が奇数であることが役立つ)。
さて、 $f(u,v)=$ 入力で与えられた木についての $u,v$ 間の辺の重みの総xorと定める。ここで、もともと頂点 $P _ i$ にあった値が頂点 $i$ に移ったことを考えるとこの値は $f(i,P _ i)$ であり、これを $A' _ i$ に一致させる必要がある。また、 $f(u,v)=f(1,u) \oplus f(1,v)$ より、
数列 $(f(1,1),f(1,2) ... f(1,N))$ が
数列 $(f(1,1) \oplus A' _ 1,f(1,2) \oplus A' _ 2 ... f(1,N) \oplus A' _ N)$ の並べ替えであるかどうかを判定すればよい。

考察

辺は扱いにくいので頂点でうまくできないか考える->変化を見る
不変量を見つける

提出コード

https://atcoder.jp/contests/agc052/submissions/48531932

2023-12-15

AGC050 - C Block Game

AGC050-Cを解いた。

問題

無限に続く一列のマス目上で次のゲームを行う。文字列 $S$ があって、 $S _ i =$ S の時、Snuke君が1マス隣の空きマスに動くか、何もせずとどまる。 $S _ i =$ B の時、あなたは任意のマスを一つ選び通行不可にする。Snukeの両脇が通行不可である状態になったらあなたの勝ち、そうでなければSnuke君の勝ち。 $S$ の一部が ? に置き換わってしまっている文字列が与えられる。考えられる元の $S$ の内、あなたが勝てるものは何通り? mod998で求める。

解法

あなたの最適戦略は、明らかにSnuke君のいるマスの隣を通行不可にしてSnuke君から見てすぐ右の通行不可マスとすぐ左の通行不可マスの距離の差(これを $L$ とする、 $L$ が $1$ になったらあなたの勝ち)を最小化すること。Snuke君の最適戦略はなるべく動ける範囲の真ん中付近にいること。
あなたのターンで、ここまで $A$ 個の S がこれまで連続してきた状態を考える。すると $L$ は
$L → min(A+1,\lceil \frac{L}{2} \rceil)$
という変化をすることがわかる。切り上げは扱い辛過ぎるので切り捨てに直すことを考えて式を整理し、 $L' = L-1$ を考えると、
$L' → min(A,\lfloor \frac{L'}{2} \rfloor)$
という変化をしているので、 $L'$ の最上位bitが下から何桁目かだけの情報を持てばよく、DPができる。

考察

切り上げは切り捨てに直そう

提出コード

https://atcoder.jp/contests/agc050/submissions/48503906
(がんばって $O(N log N)$ に抑えた、もうちょっとスマートに書けないかしら...)

2023-12-03

ARC115 - D Odd Degree

ARC115-Dを解いた

問題

無向グラフが与えられて、いくつか辺を削除できるとき奇点の数が $K$ 個 $(0 \leq K \leq N)$ となるものの通り数 mod998を求める。

解法

連結成分ごとに独立に考えられる。グラフの全域木 $T$ を取って、 $T$ に含まれない辺を消すかどうか適当に選んだ後に $T$ に含まれる辺を消すかどうか考えると、消し方と最終的な次数 mod2の状態は一対一なので、 $2^{m-n+1}*\left(\begin{matrix} n \\ k \end{matrix} \right)$ 通りである。あとは畳み込みを使って計算。

考察

全体が連結でさえあれば好きなように状態を設定できることに気付けば普通に解けそう?

提出コード

https://atcoder.jp/contests/arc115/submissions/48165786

2023-12-03

ARC111 - D Orientation

ARC111を解いた

問題

頂点 $i$ から到達できる頂点が $C _ i$ 個になるように、無向グラフの各辺に向きを付ける。解が存在する入力のみ与えられる。

解法

各辺 $(a_i , b_i)$ について、 $C _ {a _ i} \neq C _ {b _ i}$ であるものは向きが明らかで、そうでないものは閉路に用いられている辺となる。解が必ず存在することより、dfsで貪欲に向きを付けていけばよいことがわかる。

考察

わりとすんなりいけた。

提出コード

https://atcoder.jp/contests/arc111/submissions/me

2023-11-21

ARC128 - D Neq Neq

ARC128-Dを解いた

問題

数列 $A$ が与えられる。 $A _ i \neq A _ {i-1} ∧ A _ i \neq A _ {i+1}$ を満たす $A _ i$ を削除する操作を好きなだけ行う。最終的な $A$ の数mod998244353を求める。

解法

まず、2つ以上同じ数が連続している部分について考える。ここに含まれる数は絶対に削除できない。
以後2つ以上連続している部分を併合してしまって考える(つまり $A _ i \neq A _ {i+1}(1 \leq i \lt N)$ )。 $x _ 1 ... x _ k$ のindexを選ぶことが可能か考える( $x$ は昇順)。まず、2以上の部分を併合したものが全て $x$ に含まれるのが必要。そうすれば、全ての間の数を削除できれば良い。
$x _ 1$ と $x _ 2$ の間の数を全て削除することが可能かどうかの問題を考える。間の数が $1$ 個までなら必ず実現可能。そうでなければ、間の数が $3$ 種類以上である、つまり間の数に $A _ {x _ 1} \neq m ∧ A _ {x _ 2} \neq m$ を満たす $m$ が存在するのが必要十分。これは帰納法で簡単に示せる。
$DP _ i = (A _ iを最後に選んだ時の通り数)$ というDPを考える。累積和などを用いて更新していけば解が求まる。

考察

最初に選ぶものを固定するのはよくある、間の数を削除するのもどうしたら選べるかどうか考えれば容易に思いつく気がする。後半部分については間の $A _ {x _ 1}$ と $A _ {x _ 2}$ が厄介なことに気付けばおのずと発想できると思う。

提出コード

https://atcoder.jp/contests/arc128/submissions/47802454
(セグ木を使っています、カス)

2023-11-21

ARC168 - D Maximize Update

ARC168-Dを解いた

問題

$N$ 個の白いマス目と $M$ 個の操作が与えられる。 $i$ 個目の操作では、 $L _ i \leq x \leq R _ i$ を満たす $x$ マス目を黒く塗る。ここで、操作前よりも操作後のほうが黒いマスが多くないといけない。最大操作回数は?

解法

$DP _ {l ,r} =$ 区間 $[l,r$ ]だけ考えた時の最大操作回数
としてDPする。 $DP _ {l , m-1}$ と $DP _ {m+1 , r}$ を合わせて $DP _ {l,r}$ を更新することを考えると、新しく操作できるようになるのは高々1回だけ( $m$ を黒にかえる)で、この操作 $i$ は $l \leq L _ i \leq m \leq R _ i \leq r$ を満たす必要がある。これは、事前に区間 $[l,r$ ]に完全に含まれる操作の数を累積和で計算しておけばよい。

考察

愚直なDP(マス目を使った/使ってないをbitで持つやつ)をまず考えてみてそこから区間を黒くすることに注目して区間だけの情報でDPすることを考えたかった。

提出コード

https://atcoder.jp/contests/arc168/submissions/47783642

2023-11-19

ARC136 - C Circular Addition

ARC136-Cを解いた

問題

円環状で要素がすべて $0$ の数列の連続部分列に $1$ を加算する操作を何回か行う。所望の数列 $A$ に一致させる最小操作回数は何回?

解法

$A$ から減算を繰り返して数列の要素をすべて $0$ にすることを考える。
$M=max(A)$ 、 $D _ i := A _ {i+1} - A _ i$ ( $A _ {N}$ は $A_0$ として) 、 $S := \frac{ sum(D) }{2}$ と置く。減算する区間の端に注目すると、まず $D$ から二項選び、 $1$ の加算と $1$ の減算をして $D$ の要素を全て $0$ にする必要がある。この操作は明らかに $S$ 回は必要。そして、実験をすれば $A$ を $M-S$ 以上の数に統一できることがわかる( $M$ と $S$ の大小関係で場合分けすれば証明できるはず)。ここから全体に $1$ を減算することを繰り返す。よって解は $S + max(M-S,0) = max(S,M)$ 。