yukicoder contest 342 参加記

oo-oo---

A 問題。余りの余りの $\ldots$ と考えてしまうと難しく感じた。$ m $ で割った余りをとると $ m $ 未満になるので嬉しい。

B 問題。A と B のあいだ、C と D のあいだに仕切りがあるみたいなことを考えたがうまくいかず。 不変量を考えるとABだけで見た順番とCDだけで見た順番が不変に保たれることに気づく。逆に順番さえ保てばよいので二項係数。

C 問題。マージテクの計算量と実装法が分からなかった。正当性も証明できていない気がするので飛ばした。

D 問題。すべての可能性を調べるのはサンプル4で触れられているように難しいことが分かる。$a=2$ のときに $30$ 個くらいの選択肢があって $30^4=8.1\times 10^5$ なので半分全列挙ができそう。特に複雑なことはせず一般的な実装で済んだ。

E 問題。$i+j=A$ として $A$ を固定したとき、$A$ を与える $(i,j)$ がいくつあるかを数える。偶数回なら無視できることに注意する。$A=2L,2L+1,2L+4,2L+5,\dots$ のときに奇数回となるが、$(2x)\oplus (2x+1)=1$ (これは二進表記を考えると分かりやすい) に注意すればあとは $(R-L)\bmod 8$ による丁寧な場合分け。

F 問題。見てません...

G 問題。AC数を見てこちらに専念することに。ある点における回転たちをうまくまとめる問題。セグ木に乗るのか分からず、というか乗らないと思っていた。回転によって任意の $2$ 点間の距離は変わらないことに注目。操作前に適当に $3$ 点 $A,B,C$ を取って、各操作後にどこに移るかを記録しておく。操作 $s$ の直前の $3$ 点の位置($a,b,c$)と操作 $t$ の直後の $3$ 点の位置 $(a^\prime,b^\prime,c^\prime)$ について、点 $P$ の移動前の位置 $p$ と移動後の位置 $p^\prime$ が $ap=a^\prime p^\prime,bp=b^\prime p^\prime,cp=c^\prime p^\prime$ を満たすことから $p^\prime$ を計算できる。実装が分からず時間切れ。

H 問題。見てません...