努力を惜しまず精進す

ABC 304 G - Max of Medians

初めに

atcoder.jp 解説放送で AC です

解法

中央値の最大化で手が止まります.

では最小値の最大化は? 二分探索ですね

同様にできます. 具体的には, $f(X)$ := $A$ を適当に xor を取ったもので $X$ 以上が何個作れるかという関数を考えます.

この値が $\lfloor N/2 \rfloor + 1$ 以上であれば, 中央値が X 以上に大きくすることができます.

なのでこの $f(X)$ を実装することができれば, 答えで二分探索をすることによって正答が得られます.

これは $X$ を上位 bit から見ていき, 再帰的に数えていくことで実装できます.

終わりに

判定関数の実装, どこで練習できますか...?

Books

www.youtube.com

ARC105 B - MAX-=min

初めに

atcoder.jp 解けなかったので

敗因

最小値が変わらないような操作はまとめてしまってよいなみたいなことを考えた。

(正直、眠くて頭が働いていない...)

当然 WA でした... (でもどんなケースが WA なのかは分からない...)

解法

gcd は変わりません.

終わりに

なるほどなあ.

AGC037 A - Dividing a String

初めに

atcoder.jp 解けなかったので

敗因

keisuke6 と相談,

6「貪欲でよくね」

5「でも aaaaa とかバグらない?」

6「たしかに」

解法

方針はほぼ同じ. 3 文字を分割する際に 1, 2 で切るか 2, 1 で切るかどちらかを選ぶことができるが,

3 文字の直前とこの 3 文字の前半が一致することはないので ( 3 文字の直前が 1 文字なら 2, 1 で切断し、 2 文字なら 1, 2 で切断すればよい.)

公式 editorial にあるような漸化式がなりたつ. これを実装すればよい

終わりに

普通に頭いいじゃん

ABC298 F - Rook Score

初めに

atcoder.jp 解けなかったので

敗因

解法

座標圧縮などをして $N \times N$ のグリッド上の問題に言い換えておきます.

また行を固定した際(行 $i$ とします)に, 列をどう決めるかを考えます.

まず列(列 $j$ とします)の総和を求めておきます.総和の大きい順に選んでいっていけばよいのですが, $A_{i \, j}$ を引かなければいけません. しかし, $A_{i \, j} = 0$ のとき, $0 \le A_{i \, j}$ より, そこで探索を打ち切ってしまってよいです. よって, 列をみる数は高々 $2N$ 回になることが分かります.

よって $O(N)$ でこの問題が解けました.

終わりに

おもしろい

codefesthanks2017G - Mixture Drug

初めに

atcoder.jp 解けなかったので

敗因

精選 150 問を解いています.

半分全列挙の問題というところはヒントとして知っていたけれど, 解法がよく分かりませんでした...

Unite 部分が難しくて解決方法がまったく思いつかなかった.

解法

グラフ上で考えて $A_i$ と $B_i$ を辺でつなぐ. 最大独立集合は? と言い換える.

解説の図のように, ある部分集合を決めてしまえば, それを独立集合かどうか判定した上で, その集合に含まれる頂点と辺でつながれている頂点を除いたものの最大独立集合は? と言い換えられる.

この問題の本質は, 異なる部分集合 $S, \, T$ が存在して, 独立集合 $s \in S, \, t \in T$ が存在したとき, 集合 $s \cup t$ は, 集合 $S \cup T$ 内でも独立集合であるという性質による.

あとは, ある部分集合内での最大独立集合を求めておけばよくて, これは bitDP などで事前に計算しておくことができる.

$isok[s$ ] := $s ( \in V1 )$ が独立集合であるかどうか

$u[s$ ] := $s ( \in V1 )$ と辺でつながれていない頂点 $u_i ( \in V2 )$ の集合

$dp[u$ ] := $u ( \in V2 )$ の部分集合での最大独立集合のサイズ

終わりに

バグらせまくりましたが...

ABC295 E - Kth Number

初めに

atcoder.jp 解けなかったので

敗因

分からない...

0 以外の数字を sort して, そこに 0 を変化させた数字を挿入するみたいな考えをしましたが, 全部 0 の時にうまく行かなかった.

解法

期待値に縦横反転(造語)を適用する.

要するに $P( A_k = x )$ だと考えづらいので $P( x \le A_k )$ とすることで, $x$ 以上の項が $N - K + 1$ あるときと言い換えることができ, 計算が簡単になる!

終わりに

縦横反転は数学をしていたときにうまくできてうれしくなったことがあります (このツイートなんですがこのツイートのリプライ先が誤りを含んでいたので新しくツイートしなおしました(具体例で))

ABC296 D - M<=ab

初めに

atcoder.jp 解゛け゛ま゛せ゛ん゛で゛し゛た゛...

敗因

最初は変な風に誤読をしていて 2 ペナをしました.

そのあとある数 $x$ が与えられるのでそれが $[1, N ]$ に存在するふたつの数の積で表せるかを判定する関数みたいなものをつくりました.

当然, 最後の方は $N \cdot ( N \, - \, 1 )$ と $N \cdot N$ の間にはそのような $x$ は存在しないので最悪 $O( \, N \, )$ になります.

このことに気づいたのが 22:00 くらいでした.

かなり焦っていたのもあってうまく思考できず... 完全に敗北です.

解法

a を固定します. そうすると b が $O( \, 1 \, )$ に定まります. $a \, \le \, b$ として一般性を失わないので結局 $O( \, \sqrt{M} \,)$ となって十分高速です. atcoder.jp

終わりに

あーあ