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を置けば良い。

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。

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

　しかし、中央に重なりがある場合も、それと独立に、二項係数で表せると気付くのは難しかったと思う。

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

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）

　Fまで。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY） Fまで
C A[i]*（iより右の和）を足し合わせる
D BFS
E 一番右にあるAより左にあるBの個数で場合分け
F 線分の間を+1すると、クエリは階段を何段上り下りするかになる。実装はセグ木で。
G Mo's algorithmと思ったが分からず。

— titia (@titia_til) May 10, 2025

G - Range Shuffle Query

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

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

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

Codeforces Round 1024 (Div. 1)

　ABDの三完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1024 (Div. 1) ABDの三完。
A 中央からぐるぐる
B (偶数番目の転倒数＋奇数番目の転倒数)の偶奇は不変。
D 尺取り。LIS/LDSのDPで、最初の要素を消したときにどちらかのDPの一ヶ所が消える→LISかLDSかは、以前どちらを増やしたか見る。A[i]に近いものを消せばOK。SortedSetで実装。

— titia (@titia_til) May 11, 2025

C. 23 Kingdom

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

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

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

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

AtCoder Beginner Contest 404（Promotion for Engineer Guild）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 404（Promotion for Engineer Guild）Eで右側へ行けると誤読して時間を食う。Gは牛ゲーに見えるけど、どういう最短経路に帰着できるか分からず。
B 回転四通り試す。
C 次数は2か？　全頂点繋がっているか？
D 2^(2*N)全探索
E すぐ左の1へ行くまでの手数を求めていく。

— titia (@titia_til) May 3, 2025

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。

　牛ゲーは、解説を見れば理解できるけど自力で構成するのは難しい。

　牛ゲーじゃないかと思ったときは、けんちょんさんのこの記事を見るのが良いかもしれない。

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

　ABDの三完。

コンテストへのリンク

No.3134 二分探索木

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

　二分探索木を構築する部分が難しい。

　単純な方針だとできなそうに思えたため、SortedSetを使う方針を考えたら上手くいった。

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

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

No.3137 Non-Intersect Chord Triangle Game

　解説AC。

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

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

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY） Fまで。
C Xがクエリ2で指名されたか、(X,Y)がクエリ3で指定されたか。
D Counterを使い、連結成分ごとDP
E Trie木
F 最初BFSで全列挙しようとしたりしてダメ。そのまま掛け算できるかで分けるとDPできる。

— titia (@titia_til) April 27, 2025

G - Odd Position Sum Query

　解説放送を見てAC。

　この前のこたつがめさんの解説放送で、セグメント木≒Binary Trieだという話を聞いていた。知識はあったので解けなくてはいけない問題だった。

　ただ、そもそも、値が小さければ普通のセグメント木で解ける、ってこと自体思いついてなかったんだよね……。