C. Hacking Numbers
こたつがめさんの放送の振り返りを見てAC。
こんなの思いつかない。初手で掛け算すること自体を考えなかったので厳しい。
D. D/D/D
自力AC。
偶奇に分けて、最大何歩歩けるか？ 各マスまで最小で何歩でいけるか？ を求めればOK。
titiaのノート
2025年5月19日月曜日
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)