コンテストページ
Dashboard - Hello 2020 - Codeforces
A - New Year and Naming
1 減らしておいて剰余です。
B - New Year and Ascent Sequence
ascent を持たないものを数えます。まずそれ自体 ascent を持つような区間は消しておき、min と max のリストを作ると、min_i ≧ max_j が条件なので、片方を全探索、もう片方の個数を二分探索です。
C - New Year and Permutation
2 次元で考えて、サイズ k の framed range の出現場所は (n-k+1)2 通り、それを実現する置換の数は k!(n-k)! 通りなので、これらを掛けて足し合わせます。
D - New Year and Conference
A 日程で被ることと B 日程で被ることが同値であるか確認です。片方ずつ見れば良いので、まずは A -> B を見ます。A をイベントソートして、開催中のイベントに対応する B 日程の交叉を保持して、空でなければよいです。これの実装がわからなかったのですが、遅延セグメント木（区間加算、区間 max）でなんとかなることに気づき、貼りました（はい！？）
E - New Year and Castle Construction
点 p が四点の凸包に含まれることと同値です。点 p を全探索です。条件を満たしていない方を数えるとよくて、それは相対座標の偏角が 180 度未満の範囲に固まっているときなので、偏角最小が何であるかで分けて数えることで、尺取り法でカウントすることができます。はい、通らなかったので、long double で書き直して、それでも通らなかったので † 行列式ソート † を実装し始めたのですが、間に合いませんでした。なんですか？？
ツイッターの様子
被害者の会です。
E:四角形に点pが含まれるとき、その4つの点から作れる4種類の三角形のうち丁度2つにpが含まれることに気付くと、三角形の数え上げになる
— こるとん (@kyort0n) January 4, 2020
これは偏角ソートを使えば余事象でok
...と思いきや、atan2で角度に直すと精度が足りない deltaxとdeltayで管理する 何故-1e5<=x, y<=1e5にしなかった writerやめ
long double にしたら pretest は通りました
— ymatsux@ゲームアカウント (@ymatsux_game) January 4, 2020
long doubleでやっても死んだんだよな 何でだろ
— こるとん (@kyort0n) January 4, 2020
long double PI = std::acos(-1)を
— Mister (@mistterpp) January 4, 2020
long double PI = 3.14159265358979323846338328L;
にしたらpretest通ってガン萎えした
会員募集中です。
そしてこちらは不幸を呪っている方です。
欲を言えば浮動小数点数使ってない人間も落ちてほしい
— こたつがめ (@kotatsugame_t) January 4, 2020
おそらく真相です。
偏角sortというよりも+piが大体やばいはず
— heno (@heno_code) January 4, 2020
お説教です。
というか1e9の点を偏角ソートするライブラリを、作ろうね！
— よすぽ (@yosupot) January 4, 2020
はい……
そして輝くウルトラながたかなです。
Hello 2020 E - New Year and Castle Construction、AC です。私は一体何と戦っていたのでしょう……（遠い目）https://t.co/Vq4qnFJfRu
— ながたかな (@ngtkana) January 4, 2020
D の珍回答です。
は？？？？D通ったけど(意味不明過ぎる，何をしたかというとaとbでそれぞれの区間に重ならない区間の数を数えて一致してるか数えただけ)
— 💣卵生ホエール🐳 (@323O65281) January 4, 2020
反例が見つかったようです。
これはいかがです？
— laycrs (@laycrs) January 4, 2020
4
1 1 1 1
1 1 2 2
2 2 1 1
2 2 2 2
こちらは悲しみに暮れる卵生ホエールさんです。
完全に個数で投げた自分が悪いんだけど個数で通ってほしくなかったな...
— 💣卵生ホエール🐳 (@323O65281) January 4, 2020
