Processing math: 0%

2025年5月28日水曜日

Codeforces Round 1027 (Div. 3)

 全完。若干遅刻したのに良い順位で嬉しい。

コンテスト後のツイート


2025年5月27日火曜日

AtCoder Beginner Contest 407(Promotion of AtCoderJobs)

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

コンテスト後のツイート

E - Most Valuable Parentheses

 解説AC。
 結構思いつきにくいと思う。

 別の方針からこの解法へ行きつくこともできるようだけど、
 「index iまでのうち"("は少なくとも何個含まれるか?」という考え方は身に着けておきたい。
 括弧列の定石の一つなのだろうけど、身に着いていなかった。

G - Domino Covering SUM

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

2025年5月26日月曜日

AtCoder Regular Contest 198 (Div. 2)

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

コンテスト後のツイート

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]だった方が直感的に分かりやすい。

2025年5月15日木曜日

AtCoder Regular Contest 197 (Div. 2)

 Dまで四完。

コンテスト後のツイート

E - Four Square Tiles

 解説AC。

 二項係数でどうにかするのでは? という気持ちになるのが大切だったか? 中央の重なりがない場合については、そういう気持ちになれば求められたと思う。

 しかし、中央に重なりがある場合も、それと独立に、二項係数で表せると気付くのは難しかったと思う。
 ただ、中央に重なりがない場合が二項係数で表せたなら、正しい答えも二項係数の足し引きで表せるのでは? と思って実験し、正しい答へ辿り着けた可能性はあるか。

2025年5月14日水曜日

AtCoder Beginner Contest 405(Promotion of AtCoder Career Design DAY)

 Fまで。

コンテスト後のツイート

G - Range Shuffle Query

 ACできなかったのは仕方ないが、Mo+セグ木の解法は自力で思いつかなくてはいけなかった。

 平方分割するとセグ木を使うより計算量が良くなることは知らなかった。頭に入れておきたい。

 ところで、Moを書くときは、区間を広げた後、縮めていくように書くべきだということも知らなかった。今回、PyPyでTLEを取ることができず、ChatGPTにRUSTに直してもらったのだが、それが原因で配列外参照が起こってしまった。原因が分からず大分苦労した。

2025年5月13日火曜日

Codeforces Round 1024 (Div. 1)

 ABDの三完。

コンテスト後のツイート

C. 23 Kingdom

 解説を見たがそのままは理解できず。

 使う個数xを固定した場合、「x,x-1,...,1の順に、できるだけ左にあるものを貪欲に使う」「x,x-1,...,1の順に、できるだけ右にあるものを貪欲に使う」として取ったものを合わせれば良いことは分かった。

 それを三分探索すればACできるというコメントを見て、AC。PyPyじゃ間に合わないので、ChatGPTにRUSTに直してもらった。

 もっと良い方法があるようだが理解できていない。




2025年5月7日水曜日

AtCoder Beginner Contest 404(Promotion for Engineer Guild)

 Eまで五完。

コンテスト後のツイート

F - Lost and Pound

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

 分割数全部調べる方法は理解できたけれど、DP内でDPする方法の方が理解できず苦戦した。

 結局自分で(再帰で)書いて見たらACコードは書けたけど、かなり難しく感じた。

 残りターンT回、残り押さなくてはいけない回数K回のときの勝率をcalc(T,K)、とし、
(残りターンT回のとき)残りボタンを押す回数M回、kai回押す場所を決め、残り押さなくてはいけない回数x回のときの勝率をcalc2(M,kai,x)という関数を定義し、計算した。

 引っ掛かっていたのは、kaiという変数が必要なこと。
 kai回当たらなかった場合、当たりのボタンはN-kai個の中に含まれるので、当たりの確率は上がっているはず。

 解説や解説放送のDPではこれをどう処理しているのかが分からなかったので、必要ないのか? と思ったけど、やっぱり必要でした。
 snukeさんのコードだと、26行目に(n-i)を掛けているのがそれに当たるんですね。

 再帰だと(多分)同等なコードが書けるけど、このDPを書くのは難しい……。確率DPは再帰じゃないと書けないかもしれない。

 

G - Specified Range Sums

 解説放送を見てAC。

 牛ゲーは、解説を見れば理解できるけど自力で構成するのは難しい。
 牛ゲーじゃないかと思ったときは、けんちょんさんのこの記事を見るのが良いかもしれない。


2025年5月3日土曜日

yukicoder contest 466 オムニバスコンテスト

 ABDの三完。


No.3134 二分探索木

 自力AC。コンテスト中は思いつかなかった。

 二分探索木を構築する部分が難しい。
 単純な方針だとできなそうに思えたため、SortedSetを使う方針を考えたら上手くいった。

 使ってなさそうな提出もあるけど、大抵の提出では使ってそうだし、まあ良いかな(?)

 ※逆順列のCartesianTreeを作ると良いらしいです。

No.3137 Non-Intersect Chord Triangle Game

 解説AC。
 葵ちゃんの行動を誤読していたのでそもそもダメだが、正しく捉えていたとしても解けたとは思えない。

 小さく、かつ弦のない円で実験したとき、2頂点、6頂点で茜ちゃんが勝つ、と正しく把握できたら考察を進められそう。