Loading web-font TeX/Main/Regular

2025年3月30日日曜日

AtCoder Beginner Contest 399

 　Eまで。

コンテスト後のツイート

F - Range Power Sum

　解説AC。

　「積の和典型」とも呼ばれる、組み合わせに帰着して解く問題。この解法、何度見ても解けるようにならないのだが……。
　コンテスト中に「積の和典型」で検索したのに解けておらず、辛い。





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

yukicoder contest 462

　AHCがあるのでAだけ解いて撤退した。


No.3075 Mex Recurrence Formula

　自力AC。

　実験するとN+1周期になると分かった。MEXを求めるところを愚直にやってしまったためTLEしたが、heapqを使えば良いと気付きAC。

No.3076 Goodstuff Deck Builder

　自力AC。これは迷わなかった。

　コストが大きい方から使うのが良い。残りのコストと、カードを使った回数をもってDPすればOK。
時刻: 0 件のコメント:
ラベル:

2025年3月27日木曜日

Codeforces Round 1013 (Div. 3)

　全完。
　Div. 3も最近は全完を逃していたことが多いので、今回は全完できて良かった。

コンテスト後のツイート

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

2025年3月24日月曜日

AtCoder Regular Contest 195 (Div. 2)

　三完はしたがレートは落ちた。Bは同じ解法で通している人を何人か見かけた。

コンテスト後のツイート

B - Uniform Sum

　嘘だと思ったが、（嘘かもしれないけど）それほど嘘ではなかった。

　A, Bがdistinctだとすると、S=A[i]+B[j]が何個ずつ現れるかをカウントすれば、それを見るだけで判定できる。
　今回はdistinctじゃないのでもう一工夫必要だが、大体それで良かった。

　distinctなら上手くできるのでは？　と考えるべきでした。

D - Swap and Erase

　解説AC。

　コンテスト中に考えていた貪欲（左から見ていき、A[0]==A[2]ならA[1]とA[2]をswapする）がどういうときまずいのか気付けなかったのが敗因。

　たとえば、

・1 2 1 1 1

　のときまずかった。A[0]とA[1]をswapしなくてはいけないときもある。

　Aの各要素が高々一回しかswapされないというのは言われてみれば自然だし、貪欲でダメと分かればDPしようと思えた可能性はあるかもしれない。

E - Random Tree Distance

　解説AC。解説放送も見た。

　まず、lcaを考える（u,vの距離を、D[u]+D[v]-2*D[lca]とする。D[x]は1からxまでの距離です）のはすべきだった。lcaがどこにあるか分からないから、lcaを考えることで状況が良くなるとすぐには思えないけれど、これはまずして良いですね。

　あとは、D[lca(u,v)]が、u<vのときvの値によらないと気付けるか、だが、これは実験していれば気付けるかもしれない。しかし、その後、D[lca]に関する漸化式を立てる部分が理解できず、解説を見ながら悩んでしまった。lcaが再帰的に決まっていく、と考えれば難しい式ではないのだが……。

　発想があった方が良い部分（D[lca(u,v)]が、u<vのときvの値によらないと気付く部分）もあるけれど、それ以外の定石的な部分でも詰まっているので、その部分はどうにかしたい。
　
時刻: 0 件のコメント:
ラベル:

2025年3月23日日曜日

AtCoder Heuristic Contest 044

　98位。

　コンテスト中バグらせて書き終わらなかった方針を最後まで書いていれば30位くらいにはなったので、惜しかったといえば惜しかった。

コンテスト後のツイート




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

Codeforces Round 1011 (Div. 2)

　Cまで三完というまずい成績。

コンテスト後のツイート

D. Serval and Kaitenzushi Buffet

　解説AC。
　heapqを使って上手くやる問題だと見てすぐ思い、それはあっていたのだが……。

　後ろから見てheapqで、それまでで最も良いのを出していく感じだと考えてしまったが、これだと上手くいかない。

　寿司を取る回数の最大回数が決まり、その回数だけ取るべき、というのが重要。そうすると、一回目、二回目……について、どの範囲の寿司から取れるかが定まり、heapqで答えを求めることができる。

　各回について、どの範囲の寿司を取ることができるかと考えなくてはいけなかった。愚直解（DP）と比較し、自分の解法がどういうケースで落ちるかも分かったのだけど、答えにたどりつけず。こういうときはどうすれば良いのだろうか……。

E. Serval and Modulo

　解法ツイートを見てAC。
　kはsum(A)-sum(B)の約数になる。言われてみれば確かに……。



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

2025年3月22日土曜日

yukicoder contest 461

　EHJの三問が解けず。

コンテスト後のツイート

No.3068 Speedrun (Hard)

　解説AC。

　二つ固定すれば、残り二変数については連立方程式になり、解ける。気付かなかったのはまずい。

No.3071 Double Speedrun

　自力AC。

　斜め向きにDPしていけば良い。ちょっと雑に書いたらPyPyで間に合わず、ChatGPTにRUSTに直してもらいAC。

No.3073 Fraction Median

　解説AC。気付けなかったのは悔しい。

　「中央値」というのを見て二分探索でどうにかしようとしてしまったが、それだと上手くいかない。よく問題を見ると、x/yとy/xの両方が含まれるので、この中央値は大体1。つまり、1以下で最大の数を求めれば良いと分かる。





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

2025年3月15日土曜日

yukicoder contest 460

　11ペナを経てA一完。


No.3056 Disconnected Coloring

　1の周り、もしくは、Nの周りだけ青にすれば良いだろう、という方針はすぐに立ったが、そこからが長かった。
　どういう場面でWAになるか分からず、submitデバッグも経てなんとかAC。

No.3057 Tree Distance Set

　自力AC。コンテスト後、落ち着いて考えたら思いついた。

　2頂点の間に辺がある状況から、もう一点、それらから等しい距離Dの頂点を作りたいなら、その辺の中央に頂点を作り、そこから辺を伸ばして、新たな点を加える（そして、それのみSに加える）とすれば良い。
　そうして作った木は、「2頂点の間に辺がある状況」を維持しているのでその後も再帰的に作れる。

No.3058 Deque and Brackets

　解説AC。

　hamamuさんの解説ツイートが分かりやすかった。
　分かってしまえば難しくない問題なはずなのに、「後ろから見る」というキーワードを見ても自力で解けなかった。

　こういう貪欲系は、調子いいと解けたりするんだけど、安定させるにはどうしたらいいのかなぁ。
　
時刻: 0 件のコメント:
ラベル: ,

2025年3月13日木曜日

Codeforces Round 1009 (Div. 3)

　Fまで。D以降どれも難しい印象。
　と思っていたら、Fはシステムテストで落ちた。

コンテスト後のツイート


F. Counting Necessary Nodes

　ちゃんとメモ化してAC。
　tupleでメモ化しようなどとしたのが浅慮でした。ちゃんと整数でメモ化したら通った。

G. Game With Triangles: Season 2

　区間DPなのは良いけれど、円環だということを意識する必要はなく、シンプルな区間DPで良いと気付けなかった。（自分が書いたコードは結構複雑……）

　それに気付けていればもっと簡単に書けたねぇ。


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

2025年3月10日月曜日

AtCoder Regular Contest 194 (Div. 2)

　ABDの三完。終了10秒前にDを通して青落ちを免れた！　かと思いきや、その後、Dが（本質的に）嘘解法だったことが発覚！

コンテスト後のツイート

C - Cost to Flip

　一応自力AC。
　三分探索解と比較して、バグ探しを頑張った。

　コンテスト中は、(1,1)→(0,0)→(0,1)と変化させるものの個数で三分探索できる気がしたが、それでは上手くいかず。なら、差分計算するしかない！　と書いたもののWAが出て、諦めてDへ行った。

　しかし、差分計算するしかない、というのは正しい。
　愚直解（三分探索解）とランダムケースで比較し、どうにかAC。

　この問題では、AHC的な能力を問われている気がした。差分計算は山登りや焼きなましをするとき重要。
　AHCでも、差分計算の立式が下手で失敗していることは結構ある。足りないのは状況整理能力だろうか……。

　なお、差分計算の失敗だけでなく、（三分探索で失敗したのに）凸性が保たれていると勘違いして実装していた。これも反省。せっかく差分計算しているのだから、全探索しないと。

D - Reverse Brackets

　嘘解法でした。


　コンテスト中は時間なかったけど、落ち着いて考えていれば気付けたはず……。
　

E - Swap 0^X and 1^Y

　解説放送を見てAC。

　標準形（辞書順）を考えるという方針をまず考えたけど、それで正しいのかが分からず解説を見てしまった。

　実はそれで正しく、どうやって高速に標準形を求めるか？　という問題だった。swapできるものを最初にまとめておくという方針は分かりやすいですね。
　あまり考えずに解説を見てしまったけど、考えたら気付いたのかなぁ。
　







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

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できた。

No.3052 Increasing Sliding Window Minimum

　解説AC。

　二乗DPになりそうなのは分かる。
　DP[i][j]を、左からindex iまで埋め、使っていない数字の個数がj個のときの個数としてできそう、と思いかなり長いこと取り込んだがWAが取れず解説を見た。

　すると、小さい数字から埋めて行くのが正解だった。
　考え方は似ていたが、それだと、次の数字がどこのindexにまで入れていい、ということが分かるため、最初から分かっている数字を扱いやすい。

　DP[i]をindexいまで置くことが可能なときの個数、と定義してやったが、この定義の仕方が悪く、n=2のときに例外処理をしなくてはいけない実装になってしまったが、無事AC。
　DP[i]を、今までの数字で一番右に置いたindexがiのときの個数、とすべきだったか。
　




時刻: 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)