E 最大値・最小値を持ってrootから木DP
— titia (@titia_til) May 26, 2025
F x/gcd(x,y),y/gcd(x,y)の約数列挙してDP
G 「4 1 4」のとき、1を作った後だと、4は2からしか作れない(2に1を足していって作るのが最適)。左右どちらかが存在するとき、何手かかるかは分かる。最初にどこを作るか決め、左右から累積和で計算。
2025年5月28日水曜日
Codeforces Round 1027 (Div. 3)
全完。若干遅刻したのに良い順位で嬉しい。
コンテスト後のツイート
2025年5月27日火曜日
AtCoder Beginner Contest 407(Promotion of AtCoderJobs)
ABCDFの五完。コンテスト終了後すぐにGは通った。
コンテスト後のツイート
E 左カッコは、残っている要素の最小値と対応させれば良いのでは?→WA。という嘘から抜け出せず。
— titia (@titia_til) May 24, 2025
F 三角形を描きどの部分に影響するかを見る。[l,r]の範囲だとその中で最大値を取るものが、長方形領域に影響する。imos法で表せる。
G 最小費用流。一個もおかないケースを忘れてWA。コンテスト後AC。
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二完。
— titia (@titia_til) May 25, 2025
A 偶数
B 実験すると、(1,2,1)や(1,1,1)減らせる。減らしたときXがマイナスにならなければYes。ただし、Z=0でYが奇数のときはダメ。
C 左端から合わせる。最後の辻褄合わせは(0,+1,-1)や(0,-1,+1)を四手・六手で構築できて勝ったと思ったんだけど、WA。
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]だった方が直感的に分かりやすい。
No.3148 Min-Cost Destruction of Parentheses
01 on Treeの類題ということはツイートで知っていたのに、大分時間がかかってしまった。この自分のコードなどを参考にしてどうにかAC。
当時のコードはちょっと不思議なことをしていた。大体同じだけど、今のコードの方が自然な気がする。
括弧列から木を作るパートはスタックで行えば良い(参考)。この部分で詰まらないようにしたい。
2025年5月15日木曜日
AtCoder Regular Contest 197 (Div. 2)
Dまで四完。
コンテスト後のツイート
D setとして、A[i]がA[j]を含むならiはjの親。木を作ったときAになるか十分条件をcheck。A[i]=A[j]の重複度の階乗の積が答え。
— titia (@titia_til) May 4, 2025
E - Four Square Tiles
解説AC。
二項係数でどうにかするのでは? という気持ちになるのが大切だったか? 中央の重なりがない場合については、そういう気持ちになれば求められたと思う。
しかし、中央に重なりがある場合も、それと独立に、二項係数で表せると気付くのは難しかったと思う。
ただ、中央に重なりがない場合が二項係数で表せたなら、正しい答えも二項係数の足し引きで表せるのでは? と思って実験し、正しい答へ辿り着けた可能性はあるか。
2025年5月14日水曜日
AtCoder Beginner Contest 405(Promotion of AtCoder Career Design DAY)
Fまで。
コンテスト後のツイート
AtCoder Beginner Contest 405(Promotion of AtCoder Career Design DAY) Fまで
— titia (@titia_til) May 10, 2025
C A[i]*(iより右の和)を足し合わせる
D BFS
E 一番右にあるAより左にあるBの個数で場合分け
F 線分の間を+1すると、クエリは階段を何段上り下りするかになる。実装はセグ木で。
G Mo's algorithmと思ったが分からず。
G - Range Shuffle Query
ACできなかったのは仕方ないが、Mo+セグ木の解法は自力で思いつかなくてはいけなかった。
平方分割するとセグ木を使うより計算量が良くなることは知らなかった。頭に入れておきたい。
ところで、Moを書くときは、区間を広げた後、縮めていくように書くべきだということも知らなかった。今回、PyPyでTLEを取ることができず、ChatGPTにRUSTに直してもらったのだが、それが原因で配列外参照が起こってしまった。原因が分からず大分苦労した。
登録:
投稿 (Atom)