Codeforces Round #618 (Div. 1) 解法

コンテストページ

https://codeforces.com/contest/1299

解法

✔A - Anu Has a Function

これは差集合演算ですから、先頭をどれにするかだけです。先頭を全探索です。それ以外のものすべての or を取って f をしましょう。

✔B - Aerodynamic

n が偶数で、「対辺」が逆ベクトルのときに、「流体力学的に良い」（？）です。

✔C - Water Balance

暫定的に区間に分けましょう。長さと合計値の組をスタックに積みます。新しいものもとりあえず積んで、それからスカッシュをしましょう。平均値が強単調増加になっていて欲しいです。なっていなければスカッシュです。

ARC 001 D - レースゲームを AC した私には、このようなスタックの使い方は、余裕です！

✖ D - Around the World

0 からの辺はひとりぼっちまたはペアです。頂点に重みをつけながら DFS をして、サイクルを見つけたらそこの差分を根に憶えさせます。ひとりぼっちなところは、このなかで 0 が作れるかを見ればよいです。ペアになっているところは、まず 0 を含むサイクルを見ないで作れるなら、両方消すしかありません。これを入れてやっと消せるならば、片方消すので十分です。

非空な部分集合の xor を 0 にできるかどうかは、場合の数を浮動小数点数型でナップザック DP をして、1 かどうかを見れば良いです。

なのですが、Wrong answer on pretest 5 をしていますね。一体何を見落としているのか。そもそも問題文がややこしくて勘違いをしているという説もあります。

ツイッターのご様子

A

A上位bitからみる解法を理解した、自分の解法の方が素直な気がするけど上位bitからみる方が実装軽そう
— ふっぴー (@fuppy_kyopro) February 9, 2020

A にしてはかなり難しかったと感じたのですが、この解法は私はわかりません。情報求むです。

C

C は当事者の気持ちになると出来ます。貯水槽に済んでいる方から頼まれてどこの水門まで開けるのかを判断しに、水門順番に見てに行くのですが、これを素直にすると同じところを何度も見ることになって辛いですから、上手に「引き継ぎ」をしてこれを避けるようにするとうまく行きます。
— ながたかな (@ngtkana) 2020年2月9日