Dまで四完だが、Dは（予想通り）Hackされた。
コンテスト後のツイート
D 次に使う要素を持ってDP。雑にCounterを使って書いたら、PyPy3-64だとTLEしたが、PyPy3だと通った。
— titia (@titia_til) January 8, 2023
E A[i]>B[i]のとき、A[x]/xとB[i]/(x-1)を比較するなどしてダメな場所を更新。xの値は平方分割して、上からと下からの二通りやる。セグ木でやったらTLEした。もっと高速な方法がありそう。
D. Different Arrays
Counter（dict）のDPはやはり遅い。
ちゃんと配列を使いましょう。（ratedだったらそう書き直したと思うが、unratedなので……）
E. Game of the Year
解説ツイートを見てAC。
平方分割しか思いつかなかったが、もっと良い方法があった。
・xでダメならxの約数でもダメ
ということを利用する。これだとPyPyでもTLEにならず、ACできる。
0 件のコメント:
コメントを投稿