A~C 3完 66:05 247位
B通されすぎてやばかったけどCを瞬殺してプラス
A Sum equals LCM
ARCはAからちゃんと考察しないといけない
Sumの部分については、+1を繰り返すことでLCMを変化させずに1ずつ調整できるので、問題は「LCM=N, Sum ≦ Nにできるか？」に言い換えられます
これは、LCM = NとしたときにSumを最小化してくださいということなので、最小化を考えます
Nを素因数分解して、N = 2^3 × 5^2のようになったとすると、2^3, 5^2は必ず必要で、逆にそれだけ存在していればよいです
つまり、Sumを最小化しようとすると、素因数ごとに必要なものを足していくことになります
これを愚直にやるとO(√N)で通ります
もう少し考察すると解説みたいに素数のべき乗か否かになるけど、そこまでしなくてOK
(AC 4:57)
B Slinding Window Sort 2
通されすぎ～～～～
一つ一つ考察していきましょう
まず、選んだ区間は昇順ソートするので、もともとの数列より辞書順で小さくなることはありません
なので、「どこまで損をしないようにできるか？」の勝負になります
とりあえずいろいろ考えていると下の2つに気づきます
・一番後ろの区間を選ぶのはそれなりに強そう → P1 ~ PN-Kまでは動かさなくてよいからそこまでで損するパターンすべてに勝てる
・区間の中身が単調増加になっているものがあれば、そこを選ぶともとの順列と変わらないので最適となるものの1つ
ここまででそれなりに解けていそうですが、{3,2,5,4,1} (K = 3)のようなケースで困ります
これは最後の区間で操作すると、{3,2,1,4,5}になります
しかし、最善なのは[2:4]で操作した{3,2,4,5,1}です
このようなパターンはなぜ起こるか考えます
まず、最後の区間([3:5])を選んだ時にそれ以前のところは変化しない必要があります
よって、[2:4]の例だと、[2:2]にあたる区間は以下の条件を満たす必要があります
・単調増加である
解説ではこれを満たす最も左の区間にすれば最善であると示していますが、それが示せなかったのでもう少し工夫をしました
「区間[i:i+K-1]と区間[j:j+K-1] (i < j)を比較した時、どちらが辞書順で大きくなるか？」をO(logN)程度で求められればよいので、それを考えます
先ほどの議論と同様に、[i:i+K-1]で操作した方がよいのは、以下の条件が成り立つときです
区間がかぶっていない時
・[i:i+K-1]は単調増加
区間がかぶっている時
・[i:j-1]は単調増加
・[i:j-1]の最大値 < [j:i+K-1]の最小値
よってこれを実装すると、最適なものの1つであるiが求まるのであとはそこの区間でソートしてあげればよいです
(AC 50:14)
C Social Distance on Graph
こっちのほうが簡単だと思ったけど...
2色に塗るということでまず二部グラフだったらどうなるか考えます
直感的には二部グラフで同じ側にあるものを同じ色で、違う色にあるものを違う色で塗るのが最善な気がします
↑では同じ色のところに到達するまで2手かかりますが、そうでないとすると1手で到達する箇所ができてしまうので損するだろうなと思うので、二部グラフの時は解けた(ということにします)
では、二部グラフでない一般のグラフの時を考えます
二部グラフで最善っぽい解が出ているので、二部グラフに帰着させたくなります
二部グラフに帰着させるためには、いくつか辺を取り除かなければいけませんが、その辺は同じ色同士を結ぶ可能性があるので、wiが大きいものから取り除いていくのが最善になります
よって二分探索を用いて、「重みK以上の辺を取り除いたときに二部グラフになるか？」を求めればよいです
これを満たす最大のKがわかったならば、答えはmin(K, 取り除いたグラフでの最小値)になります
取り除いたグラフでの最小値は単純で、二部グラフであることは保証されているので、それぞれの頂点についてつながっている辺の重みをソートして、小さいもの2つの和を計算すればよいです
(AC 66:05)
D Substring Comparison
めっちゃ2-SATみたいな見た目してる～
→うまく辺つなげばいけそうだけど思いつかない...
→2-SATじゃありませんでした (完)
全然解けなかった...こういうの解けると強いな
総括
ARCちょっとずつ勝てていい感じ
