ブログ名

ながたかなです!

Hello 2020 解法

コンテストページ

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 で書き直して、それでも通らなかったので † 行列式ソート † を実装し始めたのですが、間に合いませんでした。なんですか??

ツイッターの様子

被害者の会です。

会員募集中です。

そしてこちらは不幸を呪っている方です。

おそらく真相です。

お説教です。

はい……

そして輝くウルトラながたかなです。

D の珍回答です。

反例が見つかったようです。

こちらは悲しみに暮れる卵生ホエールさんです。