コンテストページ
Dashboard - Codeforces Round #613 (Div. 2) - Codeforces
解法
✔ A - Mezo Playing Zoma
行ける中で一番左と一番右を考えると、その間はすべていけます。
✔ B - Just Eat It!
全体以外で、総和が最大になる区間を求めたいです。全体も許容するのであれば、今までの最小を管理しながら適宜答えを更新していけばよいです。全体を除外するために、今持っている最小がインデックス 0 であるかどうかも管理します。いいですか？ 等号でもこのフラグは更新しましょう！（泣）
✔ C - Fadi and LCM
最適解においてはかならず答えの 2 数は互いに素になります。またこのときこれらの積は X ですから、X の互いに素な2 数への因数分解を全探索です。
✔ D - Dr. Evil Underscores
桁を上から見ていきましょう。ビットがすべて立っていたり、全て降りていたりするものは、X を調整すれば下ろすことができます。一部だけが立っているような桁 p を探します。そのような桁は、答えに於いてもどうしても立ってしまいます。
選択肢は 2 つあります。桁 p の bit を反転するかしないかです。必要ならこの操作をしたとしましょう。さて、下のほうの桁の bit たちを決めましょう。桁 p の bit の立っていない項については、そもそも小さいですから、どうなろうと知ったことではありません。逆に立っている項については全力で最小化する必要があります。したがって、立っている方のグループに限って桁の下の方だけ考えた場合に帰着します。
計算量のお話です。これではどんどん分岐していって終わらないのではないかと思いきや、各項が高々ワードサイズ回しかチェックされませんから、間にあります。
✔ E - Delete a Segment
注意力場合分け枠です。
知りたいことは 2 つです。まずはそもそももともといくつの連結成分があるのか、そして各区間について、それを除くといくつ区間が増えるのかです。
各区間について状況を場合分けします。
Case 0: 他のどの区間とも重なりがない（正の距離を持っている）場合
この場合はむしろ減ります。-1 ポイントです。
Case 1: 重なりがある場合
この場合は、連結成分が消えることはありません。代わりに、分裂する可能性があります。
分裂する可能性があるのは、この区間だけで頑張ってカバーしてくれている区間です。それらの区間について、左側と右側がとうなっているのか、状況を見ていきましょう。全部で 4 通り、(2 or 0) -> 1 -> (2 or 0) です。
Case 1 - 0: 2 -> 1 -> 2 の場合
ここで連結成分が分かれます。+1 ポイントです。
Case 1 - 1: 2 -> 1 -> 0 or 0 -> 1 -> 2 の場合
連結成分が縮むだけです。0 ポイントです。
Case 1- 2: 0 -> 1 -> 0 の場合
他の区間と重なりを持っているという過程から、この場合はありえません。
まとめ
結局、2 -> 1 ->2 で +1 して、0 -> 1 -> 0 で -1 をすればよいです。
実装
イベントソートです。 同じ点に始点と終点が来た場合は、始点が優先されるように工夫です。
初め以外で重複度が 0 になったら、標準スコアに +1 です。 1 になるところは加点の機運なのですが、ちょっと待ってほしいです。一つだけ先に忠告しておくことがあります。それはこの分岐に潜む謎の落とし穴、場合分けの闇・離れ小島の存在です。
といっても実は簡単で、2 -> 1, 1 -> 0 のうちどちらかを +1 点、もう一方を -1 点扱いにすればよいです。
✖ F - Classical?
解けませんでした。爆速で通していた olphe さん、なんですか？
考えたこと
GCD を全探索することで、ログを犠牲に「互いに素なペアの積の最大値」を求める問題に帰着します。 やり方です。10 万個のお部屋を用意します。各項の方々には、それらの約数のお部屋全てに分身して入っていただきましょう。お部屋を全探索です。約数の数は少ないですから、分身したってログ程度しか増えません。ところで、「互いに素なペアの積の最大値」というのはどう求めたら良いのでしょう。
戦いの記録
10 万ですよ？ GCD の計算にログが掛かるとしても、全探索のタイマー打ち切りに、夢を見てしまいます。
はい、おつかれさまでした〜！
そうです。こんなのが通るならもっと AC がなされています。悲しいですね。
結果
36 位です。
ちょっと良さめかなくらいの感触だったのですが、D, E が案外通されなくて温めりました。素晴らしいですね。ただ F には手も足もでなくて泣いてしまいました。Div. 2、こんなに難しいのですか！？（泣）
