7完84:02 + 1ペナ 125位
逆転してるExに早めに手を付けたのがよかった、Eは反省
A CAPS LOCK
前回isupperが出てたので、今回はちゃんとtoupperを使った
(AC 0:58)
B Yellow and Red Card
それぞれの人が何枚カードをもらったか管理しておけばいい
レッドカードはイエロー2枚分と考えると実装がちょっとだけ楽？
(AC 2:47)
C Four Variables
Cなのに要求知識高くてびっくりしたら、実は想定ではなかった
AB = KとなるABのペアの数が1≦K≦Nでわかれば、あとはK, N-Kの個数の和を計算すればよくなるので、「AB = KとなるABのペアの数」を求めることにします
これも解き方いろいろあると思うんですが、ぼくは調和級数でやることにしました
A=1~Nで全探索して、B=1~Nの二重ループをします
ただし、AB > Nになれば調べる必要がないので打ち切ると全体でO(NlogN)です
もっとストレートにやるなら、約数列挙そのものなのでO(N√N)でも解けますね
(AC 5:05)
D Unicyclic Components
辺の個数を持ちながらUnionFindをします、こういうの最近も出た気がする
(AC 8:45)
E Transitivity
考察1本のEだった、詰まりすぎ
まず、「a->b, b->cがあったとき、c->a」にできると誤読します(え？)
こうすると、トポロジカルソートの後ろから見るといい気がしますが、なかなか考えがまとまらず時間がたってしまいます...
よくよくみると「c->a」ではなく「a->c」であることに気づいてびっくりします
改めて考えると操作は「aから距離2の頂点cに対して、a->cの辺を張る」と言い換えられます
もう少し考えると、たとえば距離が3の点については、距離が2の点に張った辺を用いることで距離2で到達できて、また辺を張ることができます
こうしていくと、操作は「aから距離2以上の頂点cに対して、a->cの辺を張る」と言い換えられます
これだけでも解けるんですが、「距離1の頂点にはもともと張ってあるだけ」と考えると、aから辺を張るのは「aから距離1以上の頂点」=「aから到達できる頂点」であることがわかります
よって、各頂点から毎回BFSなりDFSなりして到達判定をしてあげればO(NM)で計算できます
自分のところに戻ってくるところに間違って加算してしまって考察があっているのに悩んでしまった...
(AC 41:30)
F Regular Triangle Inside a Rectangle
この位置にある幾何なので、計算式一発ではないんだろうな(もしくはそれはあるけど、想定ではない)と思います
とりあえずよくわからないので「長方形 正三角形 内部」と調べると、正方形の中を三角形を動かしている画像がたくさん見つかります
それらから、三角形の傾け方をいろいろ調べて中にはまればよさそうだなと思って詰めていきます
1つの角を長方形の角に固定し、三角形の傾ける角度をθとします
すると、三角形の辺の長さをLとしたとき
横の長さはLcosθ、縦の長さはLcos(30°-θ)になります
※正三角形の1つの角度は60°であるため、90-60-θ
長方形内に入るためには、A ≧ Lcos(30°-θ)、 B≧Lcosθになる必要があります
ここで 0≦θ≦30°の範囲で、θが大きくなるとcosθは小さくなっていくので、
θはB≧Lcosθを満たす中で最も小さなθ(大きなcosθ)をとりたいです
そうすると条件を満たす可能性がある中でcos(30°-θ)が最小になります
よって、正三角形の1辺の長さLを二分探索する中で、それが達成できるか判定するためにθの二分探索をおこなえばよいです
epsの誤差を適当に1e-5にしたら、出力誤差が1e-9であることを忘れていて精度ミスで1敗
(AC 64:18)
G Count Strictly Increasing Sequences
とりあえず制約が小さいので雑に考えてみます
まず1番大きい桁は明らかに単調非減少になっている必要があるので、0,1,2,3,4,5,6,7,8,9の位置を探索できないかな～と思いますが、40C9ですでにかなり大きな値になってしまうので少し厳しそうです
1個決めるときに前の値が必要になると思うんですが、それを知ろうと思ったら2個前で...となって難しくなってしまい、わかりませんでした
Exもそれなりに解かれているのでそっちに向かいました
(AC --:--)
Ex Rating Estimator
見るだけ見るか～と思って、目を通します
レーティングがBを超える条件はA1~Aiまでの和 / i ≧Bなので、これを変形して
A1~Aiまでの和 ≧B*i
さらに変形して
A1~Aiまでの和 - B*i ≧ 0となります
こうすると、左側の式がはじめて0以上になるindexを求めればいいことが分かります
「クエリが与えられて更新がいる」＆「はじめてtrueになるindex」を処理したいので、遅延セグメント木がうまくできそうです
ここまでいくと後はそんなに難しくなくて、あらかじめ各ノードに -B*iをセットしておいて、それぞれのクエリでは区間addなどを用いて更新してあげればよいです
はじめて0以上になるindexについては、区間maxの遅延セグメント木を用意したうえで(セグメント木上の)二分探索をしてあげればよいです
ちなみに、AtCoderではC++のような高速な言語だと、普通に二分探索してO(N (logN)^2)でも間に合うことが多いです
(AC 84:20)
総括
Ex初ACめでたい
