コンテスト後のツイート
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]だった方が直感的に分かりやすい。
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に直してもらったのだが、それが原因で配列外参照が起こってしまった。原因が分からず大分苦労した。
2025年5月13日火曜日
Codeforces Round 1024 (Div. 1)
ABDの三完。
コンテスト後のツイート
Codeforces Round 1024 (Div. 1) ABDの三完。
— titia (@titia_til) May 11, 2025
A 中央からぐるぐる
B (偶数番目の転倒数＋奇数番目の転倒数)の偶奇は不変。
D 尺取り。LIS/LDSのDPで、最初の要素を消したときにどちらかのDPの一ヶ所が消える→LISかLDSかは、以前どちらを増やしたか見る。A[i]に近いものを消せばOK。SortedSetで実装。
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まで五完。
コンテスト後のツイート
AtCoder Beginner Contest 404（Promotion for Engineer Guild）Eで右側へ行けると誤読して時間を食う。Gは牛ゲーに見えるけど、どういう最短経路に帰着できるか分からず。
— titia (@titia_til) May 3, 2025
B 回転四通り試す。
C 次数は2か？ 全頂点繋がっているか？
D 2^(2*N)全探索
E すぐ左の1へ行くまでの手数を求めていく。
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頂点で茜ちゃんが勝つ、と正しく把握できたら考察を進められそう。
登録:
投稿 (Atom)