ABDの三完。終了10秒前にDを通して青落ちを免れた！ かと思いきや、その後、Dが（本質的に）嘘解法だったことが発覚！
コンテスト後のツイート
D 深さが低い方から見ていく。[l,r]で同じ深さから出る山の種類・個数を見て二項係数で計算。同じ山の判定方法が分からず、A[j]>A[j+1],A[j-1]になるA[j]を列挙したりしていた。それにさらにr-lの長さの条件も加えたらAC。
— titia (@titia_til) March 9, 2025
上手いhash値を求めれば良いとは思ったけど、上手くやれないまま無理矢理AC！
C - Cost to Flip
一応自力AC。
三分探索解と比較して、バグ探しを頑張った。
コンテスト中は、(1,1)→(0,0)→(0,1)と変化させるものの個数で三分探索できる気がしたが、それでは上手くいかず。なら、差分計算するしかない！ と書いたもののWAが出て、諦めてDへ行った。
しかし、差分計算するしかない、というのは正しい。
愚直解（三分探索解）とランダムケースで比較し、どうにかAC。
この問題では、AHC的な能力を問われている気がした。差分計算は山登りや焼きなましをするとき重要。
AHCでも、差分計算の立式が下手で失敗していることは結構ある。足りないのは状況整理能力だろうか……。
なお、差分計算の失敗だけでなく、（三分探索で失敗したのに）凸性が保たれていると勘違いして実装していた。これも反省。せっかく差分計算しているのだから、全探索しないと。
D - Reverse Brackets
嘘解法でした。
ARC194のD、自分の提出は嘘解法ですね。
— titia (@titia_til) March 9, 2025
28
((()()())(()))((()())(()()))
で2を返します。（正解は4）
自分のハッシュだと、「((()()())(()))」と「((()())(()()))」を区別できないので、答えが1/2になってしまう。
コンテスト中は時間なかったけど、落ち着いて考えていれば気付けたはず……。
E - Swap 0^X and 1^Y
解説放送を見てAC。
標準形（辞書順）を考えるという方針をまず考えたけど、それで正しいのかが分からず解説を見てしまった。
実はそれで正しく、どうやって高速に標準形を求めるか？ という問題だった。swapできるものを最初にまとめておくという方針は分かりやすいですね。
あまり考えずに解説を見てしまったけど、考えたら気付いたのかなぁ。
0 件のコメント:
コメントを投稿