ABC292

6完。E遅いしGHわからんし。前半は簡単で高速に解けた。

A - CAPS LOCK

'A'を足して'a'を引けばいい。

B - Yellow and Red Card

イエローカード換算で何枚かをN人ぶん持つ。

C - Four Variables

ABが何になるかを全探索。N以下(未満でよかった)の正整数すべてについて約数の個数がわかれば掛け算して足していくだけ。O(N*log(N))になりそうだったので少し考えてそうした。実装も少し楽だと思う。長さNのvectorを持って、1以上N以下のiについてiを約数に持つ位置すべてに1を足す。

D - Unicyclic Components

辺の個数を持ったUnionFind。解説見たらUnionFindしたあとで辺を数えていてなるほど。

E - Transitivity

パスがあるとあらゆるショートカットが作られる。ループは完全グラフになる。SCCして、その強連結成分に到達できる頂点からは辺が来る。強連結成分内は全部の辺がある。これを全部足すと最終的に辺の数がわかるので、Mを引けば答え。DAGで、その頂点に到達できる頂点数がDPでできそうなのにできず、また、Nが小さいから愚直に辺を追加してもいいかと思うも方針が浮かばず、21:31にあきらめてFへ。

残り20分弱、めちゃくちゃ通されてるのでさすがに何かできるはず。到達できる頂点数は2乗でいいならDPできることに気づいた。それを実装。bitsetを使う(速度ではなく書きやすさのため)。15分あるので頑張って書く。けっこう苦戦したが5分残してAC。

解説なるほどねー。高速な解法がありそうなときに、Nが小さいとわかっていても何も見えなくなる。1回のDFS(というと違うな各頂点からDFSして訪問済みだったらやらないO(N)のやつ)でなんとかすることしか考えてなかった。Nが小さいことは忘れていなかったのに。

F - Regular Triangle Inside a Rectangle

サンプルにネタバレされた(親切すぎるだろ(まあ考察の助けにはなってもデバッグの助けにはならないか))。改めて考える。△の左下の頂点が原点にあると思って原点を中心として反時計回りに回していくと、天井はだんだん高くなり右側の壁はだんだん左に来る。サンプルにあるように15度まではそれが続く(観察によるもので証明はできない)。そこを越えると対称性を考えると同じことしか起こらない(自信なし)。そこで、AがBより大きくならないようにswapして、0度から15度を二分探索。左下を原点にしたことで、座標が三角関数で簡単にわかる。けっこう時間食ってしまった。

G - Count Strictly Increasing Sequences

全部'?'の場合は仕切りを入れるやつになるが。少なくともそれを計算する能力を持つコードを書く必要がある。少し考えてわからないのでExへ。

Ex - Rating Estimator

考えていくと、B=0のケースを考えればいいとわかる。累積和が初めて0以上になった位置を知りたい。遅延セグ木でできるかと思ったけどできない。Nが大きめとはいえ平方分割ならいけそうと思ったけどほんとに解けてるかわからんし実装に1時間はかかりそう。なんとでもなりそうな見た目なんだけどなあ。あきらめてEへ。