第13回PAST（バチャ）

ネタバレ回避用

https://scrapbox.io/files/6429462f2ef648001b8dc388.png

L, O以外を解いて88点でした。

典型や典型的な発想パターンが問われている問題が多く、いい勉強になりました。

何となく上級は取れそうで、エキスパートも上振れか精進で取れそうなので、今度お布施としてリアルタイム受験しようと思います。

# A - メダル

ABC-Aだとlong longが不要なので、それよりは難しいですね。

# B - 分数比較

無駄にすべて整数で処理しようとして、最初に符号が異なるパターンを処理しようとして、int fugou = A/abs(A) * B/(abs(B);をしてA=0で1ペナ出しました（あの）

# C - 三つ組の積

rep(k, N) rep(j, k) rep(i, j) st.insert(A_i * A_j * A_k);

で簡潔に書けます。

# D - 坊主めくり

素直にシミュレーション。

# E - 括弧列

有名問題。ロボてりーには解けません。

スタックに1種類しか入らないので実際にstack<char>を用意しなくてもint cnt;で十分。

F - 平均順位

67分＋13ペナでした（はい？）

数学的にも素直に解くことができて、分からなければ二分探索でも良いので、誤差を処理できますかという問題。

入力を1000倍すると整数で処理できて、最悪ケース（4位を1e12回取ってから1.001位を目指す場合）でも3e15回くらいなので、1000倍してもlong longに収まります。

しかしdouble X; cin >> X; X *= 1000;とすると、1.001が1000になったりして困ります。まさかそんな初手で失敗してると思わずドハマりしました……。コンテスト中はlong long X2 = (X + 0.0005) * 1000としてgot a kotonaki。解説のように、string型で受け取るのがスマートだと思います。

G - 区間和

rightを固定した時の最善のleftを考えると、累積和 - 累積minを全探索すれば良いです。

H - 桁差の和

各桁の数字は10通りしかないので、桁ごとの個数を数えながら計算すれば十分高速です。

I - 背の順

DAG判定です。PASTでもACLが使えるので、atcoder::scc_graphを用いると秒です。

実際、AからEが20分で、GからIが10分なので、この辺まではABC-Cとか簡単めのABC-Dかなという感じです。

J - 横断

直線と線分の交差判定です。

幾何ライブラリを使うためにa, b, cが0かどうかでぐちゃぐちゃ場合分けしましたが、解説がめっちゃシンプルですね。

ap+bq<cかap+bq>cかというのはそれはそうで、これはその場で考えて実装した方が良さそうです。

K - 整数屋さん

上手く全探索する箇所と貪欲にやれば良い個所を考えるやつです。

桁和は81通りなので、これを全探索することを考えます。

桁和を固定すると、その時の答えの理論値が分かります。

桁和の制約を満たしながらできるだけ理論値に近い値になるよう上から貪欲に考えれば良いです。

難しめの回のARC-Aっぽい。

L - 区間

間に合いませんでした。

区間幅が自身より真に小さいものしか真部分集合にならないですが、区間幅を（圧縮して）広げてみても高速に求まりそうにありません。

L, Rを頂点として、含む区間に有向辺を書くとどうなるか実験します。法則が見えたら更に整理するために二次元座標にプロットしてみると、LISでやる発想パターンなことが見えると思います。

M - 木と区間

「その頂点に到達可能な(i, j)はいくつあるか」をDFSで行きがけに数えました。主客転倒。

現在の頂点に到達するために必要な条件は「iはl以下、jはr以上」みたいな形になっています。

これにさらに辺kが加わる場合、「iはmin(l, k)以下、jはmax(l, k)以上」みたいになります。

N - 数列と関数

Mo’s algorithmを知っていますか？私は最近知りました。

現在の区間のソート済み列をmultisetで管理することで、伸び縮みした際の値の変化が高速に求まります。

ところで単純な種類数などと異なり、最初に例えばleft=2、right=3のクエリを処理する場合、leftを先に伸ばすと壊れます（壊れました）

O - シフトとシフト

分かりませんでした。

タイプ1のクエリは実際には処理せず、XORは遅延セグ木に乗るので、タイプ2を遅延セグ木に上手く乗せられますかという問題に見えます。

ここでDが十分小さいので、0≦i≦D-1桁シフトした値の配列をセグ木に乗せて各クエリO(DlogN) で十分間に合うという話でした（解説AC）

提出コードをカンニングしないとmappingやcompositionが書けなかったので、遅延セグ木にチートシート以外のものを入れる練習をした方が良さそうです。PAST上級本にそういうのも載ってるらしいので読みます。