titiaのノート

E 最大値・最小値を持ってrootから木DP
F x/gcd(x,y),y/gcd(x,y)の約数列挙してDP
G 「4 1 4」のとき、1を作った後だと、4は2からしか作れない（2に1を足していって作るのが最適）。左右どちらかが存在するとき、何手かかるかは分かる。最初にどこを作るか決め、左右から累積和で計算。
— titia (@titia_til) May 26, 2025

2025年5月27日火曜日

AtCoder Beginner Contest 407（Promotion of AtCoderJobs）

　ABCDFの五完。コンテスト終了後すぐにGは通った。

コンテストへのリンク

コンテスト後のツイート

E 左カッコは、残っている要素の最小値と対応させれば良いのでは？→WA。という嘘から抜け出せず。
F 三角形を描きどの部分に影響するかを見る。[l,r]の範囲だとその中で最大値を取るものが、長方形領域に影響する。imos法で表せる。
G 最小費用流。一個もおかないケースを忘れてWA。コンテスト後AC。
— titia (@titia_til) May 24, 2025

E - Most Valuable Parentheses

　解説AC。

　結構思いつきにくいと思う。

　別の方針からこの解法へ行きつくこともできるようだけど、

　「index iまでのうち"("は少なくとも何個含まれるか？」という考え方は身に着けておきたい。

　括弧列の定石の一つなのだろうけど、身に着いていなかった。

G - Domino Covering SUM

　自力AC。

　これは焦っていなければコンテスト中に通せていたはず。落ち着こう。

2025年5月26日月曜日

AtCoder Regular Contest 198 (Div. 2)

　Bまで二完。レートが落ちたが黄色には残った。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 198 (Div. 2) AB二完。
A 偶数
B 実験すると、(1,2,1)や(1,1,1)減らせる。減らしたときXがマイナスにならなければYes。ただし、Z=0でYが奇数のときはダメ。
C 左端から合わせる。最後の辻褄合わせは(0,+1,-1)や(0,-1,+1)を四手・六手で構築できて勝ったと思ったんだけど、WA。
— titia (@titia_til) May 25, 2025

C - Error Swap

　自力AC。惜しいようで惜しくなかった。

　大まかな考察は合っていたけど、詰めなくてはいけない箇所が残っていた。

　左端から揃えていく、という解法でやった。index iを揃えようとするとき、B[i]+1に一番近いA[k]を探して、A[k]が小さいなら左回り、大きいなら右回りに回転させて、B[i]+1になったらクエリ(i,j)を投げる、という方法でやっていた。

　だが、A[i]=B[i]+1となったときに(i,i)と投げられないのが問題だった。(i,N),(N-1,N)とすれば(i,N-1)とできるのだが。ここに気付いていなかった。

　ここを修正してAC。

　あと20分くらいは必要だったか。

D - Many Palindromes on Tree

　自力ACはしたが大変だった。

　問題の内容を理解するのがちょっと大変だが、理解できれば解法そのものは難しくない。(i, j)間の距離が大きいペアから、A[i][j]=1なら、一つ近づけて(i', j')も1にし、Union-findでくっつける、という操作をする。

　その上で、今度はその逆順で答えを構成していく。

　しかし、この順番を構成する部分（上の(i', j')に対して、(i, j)が何かを前計算したりする）の実装で苦戦。さらに、ちゃんと実装してもMLEになり、PyPyでは通せなかった。二次元配列にしていたり、tupleで実装しているのを整数化したりすれば解消されるのかもしれないが……。

　RUSTに直してもらいAC。今回は、Gemini Canvasを使ってみたら、一発だった。

2025年5月19日月曜日

Codeforces Round 1025 (Div. 2)

　C1までの三完。C2を考えていたら寝てしまった。

コンテストへのリンク

C. Hacking Numbers

　こたつがめさんの放送の振り返りを見てAC。

　こんなの思いつかない。初手で掛け算すること自体を考えなかったので厳しい。

D. D/D/D

　自力AC。

　偶奇に分けて、最大何歩歩けるか？　各マスまで最小で何歩でいけるか？　を求めればOK。

2025年5月17日土曜日

yukicoder contest 467

　ABCEの四完。Dは、問題の意味がぱっと理解できなかったから飛ばしたけど、分かっても難しかった。

コンテストへのリンク

No.3143 Colorless Green Parentheses Sleep Furiously

　WAが出た後、テストケースを見てAC。

　カッコ列が正しくなければダメ、というのはOK。その上で、

　できるだけ少ない個数の1を加えたとき、何個加えることになるかを知りたい。

　()なら、(1+1)+1にしなくてはいけないが、

　()()なら(1+1)+(1+1)で良い。

　(())なら、((1+1)+1)+1にしなくてはいけないが、

　(()())なら、((1+1)+(1+1))にする。

　カッコ列の対応を考えて、その対象範囲に自分のカッコだけしかないときは、()+1としなければならない、というのがなかなか気付きにくいポイント。

　実装では、最初に、どの"("がどの")"と対応しているかindexの対応を調べておき、((...))となっているようなら、後ろか前かに+1を置けば良い。

No.3145 Astral Parentheses Sequence

　解説AC。難しい。

　括弧列の個数（カタラン数）をDPで求める方法を応用するとこの問題のDPも導ける。ただ、括弧列の個数を求めるDPがそれほど明らかではないため、それと似た方法でこれもいけるというのは直感的に分かりづらい。

No.3146 RE: Parentheses Counting

　解説AC。難しい。

　解説の最初にある漸化式（三乗の計算量になるやつ）を自力で出そうとしていたが、それすらできなかった。

　ネストの深さが0の部分がカタラン数の積になるっていうところが思いつかない。ここは主客転倒で考えているのか。

　その後の、計算量削減の式変形も難しい。カタラン数が満たす漸化式を知っていればいけるかもしれないが。

　自力で解くには、実験→oeisしかなかった気がする。

No.3147 Parentheses Modification and Rotation (RM Ver.)

　解説AC。

　解説を見てしまったけど、これは自力で解けて良かった。括弧列の累積和（いつものやつ）を使い、最大値・最小値から答えが導ける。

　タイプ1が右回転なのがちょっと引っ掛けな気がした。S[1:]+S[0]だった方が直感的に分かりやすい。

登録: 投稿 (Atom)