2025年3月9日日曜日

Codeforces Round 1005 (Div. 2)

　Dまで。

コンテスト後のツイート

E. Mycraft Sand Sort

　解説AC。
　簡単なのかと思ったら、全然簡単ではなくて、解説など色々参考しても理解するまでずっとかかってしまった。（なお、解説の方法は理解していないし、自分がやった方法に嘘の疑いもある）

　Cは与えられたものと同じものを使うしかなく、Pの個数を求める。

　P_iとP_jが交換可能なのは、

・iとjが隣接しており、同じ色なとき

　だけではなく、

・iとjが同じ色で、iとjの間にあるもの全てが、P[i]やP[j]より小さいとき（これは、上の条件を内包している）

　と気付かなくてはいけない。

　コンテスト中はここにも辿り着いていなかったが、それをどう数え上げれば良いかが難しい。

　解説とは（多分）違う、左右を管理する方法でやった。

　P[i]が小さい方から見ていき、隣合っている同じ色がどの範囲までか、を見て、その要素数を答えにかける。その後、index iを削除する。

　削除というのは、左右を管理し、

・RIGHT[LEFT[i]]=LEFT[i]
・LEFT[RIGHT[i]]=RIGHT[i]

　のようにするということ。まあ、左右を管理するときはよく使う手法ですね。

　ここで、毎回同じ色がどこまでか？　を調べるとTLEするので、Union-findでくっつけ、Unionできる端の値をもっておく。
　しかし、そうすると、その端の値は既に消えていることがある。そのときは再計算（消えていないindexまでLEFT,RIGHTをたどる）してACした。

　最後の再計算するところの計算量が怪しいけれど、今回はACできた。危ないテストケースはありますか？




　
時刻: 0 件のコメント:
ラベル:

2025年3月8日土曜日

yukicoder contest 459

　ABの二完。Cを考えているうちに寝てしまった。Cは一応自力で解けたけど、寝なかったら解き終っていたかというと微妙なところ。


No.3050 Prefix Removal

　自力AC。

　もし、Aの要素全てを使い切るとすると、満足度の変化は、

・最初の操作で全てのiに対して+A[i]
・選ぶpより大きい全てのiに対して+A[i]

　のようになる。
　これを最大化するためには、Aの後ろからの累積和を取って、大きい方から選んでいけば良い。ただし、最初に0を必ず選ばなくてはいけないことに注意。

　ここまで分かったら、後はAのうち何個使うか？　という部分。
　これがなかなか思いつかなかったのだが、heapqを使えば全探索できることに気付いた。やや思いつきにくいし面倒ではあるけれど、何度もしたことがある方法だった。

　上手くやれば全探索できるのでは？　と考えてみなくてはいけないねぇ。

　

No.3051 Make All Divisible

　テストケースは見たけど、一応自分で考えてAC。

　まず、

・sum(A)がkで割り切れる
・max(A)<=sum(A)/k

　のとき、この操作で全てを0にすることが可能（ということは考えているうちに思い出した）。

　なので、各A_iをA_i%kに置き換えた数列でこの条件を満たせば一番良い。

　そして、満たさない時は、現在のAの中で最も小さい数で、かつ、+kしても最初のAの値以下であるようなものに+kして、条件を満たすかを見ていく。

　計算量は分からなかったが、この方法でACできた。


　




時刻: 0 件のコメント:
ラベル:

2025年3月7日金曜日

Codeforces Round 997 (Div. 2)

　Cまで三完。


D. Unique Median

　こたつがめさんの放送の振り返りを見てAC。アイディアは自然だが難しい。解法を理解するまでに、三回放送を見返した。

　コンテスト中は、中央値が1～10それぞれになるときに、場合の数を求めるという方針を考えていた。
　中央値がaのとき、aを0、a未満の数を-1、aより大きい数を1としたとき、（1の個数と-1の個数の差）が(0の個数)/2切り捨て以下になれば良い、というところまでは分かったが、数え上げに持っていけず。

　そうではなく、k以下で-1、kより大きいとき+1として、累積和を取らなくてはいけなかった。
　こうすると、区間和が0のとき、k以下のものの個数とkより大きいものの個数が等しくなるため、goodでない配列の個数を求められそう。（Zero-Sum Ranges系の処理ですね）
　これに加えて、「kが中央値になるため区間内にkが存在する」という条件が必要になる。これは二分探索で処理できる。


時刻: 0 件のコメント:
ラベル:

2025年3月1日土曜日

yukicoder contest 458

　Eまで五完。Eまではすらすら解けたが、Fが分からず考えこんだところで睡魔に襲われてしまった。


No.3040 Aoiスコア

　自力AC。

　DPを考えていたがうまくいかず、三頂点のpathなら列挙できると気付きAC。
　結構苦戦した。眠りに落ちる前に一度解けたと思ったが、そのときはDPを考えており、それではダメだった。

No.3041 非対称じゃんけん

　解説AC。

　bitsetの利用は考えたけれど、bit_countの部分が速くならないためダメだと思ってしまった。その部分も1/64になるんでしょうか？
　PyPyではTLEだったけれどPythonだとAC。

No.3042 拡大コピー

　自力AC。

　こういう問題で重心を考えるのは定石ですね。

No.3043 括弧列の数え上げ

　苦労したが自力でAC。

　括弧列の個数がカタラン数であることは分かっているので、calc(x):長さxの括弧列Sのf(S)の総和を、最初の(と何番目のindexが対応するかで場合分けして計算した。

　一番外側で"("と")"が対応している長さxの括弧列Sたちのf(S)の総和は、長さx-2の括弧列たちの総和に、その個数*(x-2)/2（閉じカッコの数）だけ足したものとなることを利用した。

　難しかったし、解説の方法も簡単ではない気がするのだが、AC人数を見ると解けなくてはいけない問題だったのか。

No.3044 よくあるカエルさん

　自力AC……と言っていいのかな。

　「すごろくであるマスに止まる確率」と検索したら、DPで求められるということが出てきて、それなら行列累乗で求められると気付いた。
　検索しないとDPと気付かなかったのは良くない。

No.3045 反復重み付き累積和

　解説AC。

　解説を参考にしたけど、行列ベースで考えていた。

　長さ4の数列A（1*4の行列として見ている）に対して、重みkの累積和を一回取る操作は、

1 k k^2 k^3
0 1 k     k^2
0 0 1     k
0 0 0     1

　という行列を右からかけることに対応している。

　このx乗がどうなるかというと、実験すると、これらのk^nなどのところに、Combi(n+x-1,x)という二項係数を掛け合わせたものになる。

　のだが、これだと三乗になってTLE。

　解説を見ると、この行列計算はFFTで計算できるらしい。
　それを見てAC。

　行列計算のうち、どのようなものが形式的ベキ級数的に表せるのかを知っていると良いのかもしれない。


時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)