D1までとF1で五完。
コンテスト後のツイート
F1 pを素数として、(p-1,p)にはたどりつける。素数と素数の区間は200くらいなので、そこを基準にDFSすれば間に合う。PyPyでsetを使ってdfsしたため結構時間制限が危ない。
— titia (@titia_til) August 11, 2024
F2. Court Blue (Hard Version)
自力AC。F1と同じ方法でできた。
F1では、nに一番近い素数を基準にDFSしたわけだけど、それに加えて、mに一番近い素数を基準にDFSしたらAC。nowをmin(p-1,m)から小さい方へ動かしていき、(p,now)からxのプラス方向やyのプラス方向にどこへ行けるか調べていく。それで、x成分がnにたどりつけたら探索をやめる。
これをx,y逆転させてもう一回やる。
これでACできたけど、n=mの場合と違い、正当性はやや怪しい。
（追記）正当性は大丈夫そう。n<mでnに一番近い素数を基準にするときが問題なのだけど、mがある程度大きいなら、mに近い素数をpとして、(n,p)にたどりつけるので問題ない。nとmが近いときは、上記の方法で多分大丈夫。
0 件のコメント:
コメントを投稿