Cまで三完。
No.2495 Three Sets
コンテスト後自力AC。
A, B, Cを大きい順にソートしておき、それぞれ何個取るべきかを三分探索で求めたらACできた。
コンテスト中にこの方針は思いついたもののあまり自信がなくて実装せず、コンテスト後に実装したらAC。
No.2496 LCM between Permutations
WAが出て、WAが出たtestcaseを見てデバッグしてAC。
(1, i)を全て聞いてみる。
それで、Bの中に1があるところを特定できれば簡単。そうでなければ特定できたもののうち最も大きい素数を考え、そのindex indを使って(i, ind)を聞く。
そういう感じで、AかBかで特定されていない場所が二個以下になるまで聞く。
そうしたら、片方が1と分かるので、それを利用する。
……みたいにしてACできたが、多分、Hackできますね。（多分できなそう。追記しました）
解説を読むと、N/2より大きい素数の位置がN+1回あれば見つけられることを利用していた。そういう素数の位置が分かると良いことには気付いていたが、N回で見つけられなかったとき、もう一回で見つけられるとは気付いていなかった。なるほどです。
（追記）
自分の解法は正当な気がしてきた。N/2より大きい素数をpとして、(1, i)を全部聞いたとき、A[i]=pならばBは二要素以外全て明らかになる。それ以外だったら、Bの中のpが最大の素数になる。
だから、正しそう。
No.2497 GCD of LCMs
解説AC。
一般グラフの単純パスたちの持つ性質を考えるという問題が、ダイクストラで解けるとは考えもつかず、結構びっくりした。
とはいえ冷静に考え直すと、一般グラフのサイクルとかを扱うのは難しい（サイクル基底を使う、とかはあるけれどそういう問題ではなさそう）し、何か上手いことをして最短距離問題に持ち込むくらいしかないのかもしれない。
0 件のコメント:
コメントを投稿