ABC327 参加の感想

概要

ABC327のリンクですよ！

今回は ABCDEF の 6 完 (63:15 + 10:00(2WA))。まあちょっと遅かったと思う。 区間クエリだと思ったら臆せず遅延セグ木を貼ろう。普通のセグ木でもできるだろうとかそういう解は求めない方針で。

A - ab

ba も ok なことを考える。

B - A^A

オーバーフローに気をつけて全探索。

C - Number Place

普通に全部見るだけ。

D - Good Tuple Problem

各連結成分に二部グラフ判定を行えばよい。

E - Maximize Rating

後ろからやる。このとき、dp[i][k]... 現在 i までを考え終え、k 個のコンテストを選んでいる状態で レーティング計算式の左の項の分子を最大化したものを計算する。これを最大化すれば $R$ も最大化される。

そのため、これをちゃんと遷移させて実装すると解ける。

F - Apples

やり方わかってたんだから、何も考えず遅延セグ木を使えば良いんだよう。

2 次元座標の中にあるりんごを長方形の範囲にどのくらい入れられるかを考える。 この時、とりあえず $W$ を無視して $t$ の座標を尺取りしながら現在の持っている $x$ 座標を考えることにする。 すると、その $x$ 座標たちの中で $W$ の範囲をとったときに最大いくらまで伸ばせるかという問題になる。

これは、$[x, x+W)$ までの区間に +1 するのを各 $x$ に行い、このときに区間の最大値を見ることができればいいことがわかるので、 これは遅延セグ木で実装できることがわかる。 なんか賢くやろうとして imos 法を BIT に持たせてクエリの位置が工夫できるかと考えていたら、時間がかかっておまけに WA も出た。 何も考えず遅延セグ木を貼るんだ。

G - Many Good Tuple Problems

複雑すぎる。二部グラフを形成すればいいわけだが、連結成分がどうなっているとか、どうやったら特有の二部グラフになるのかとか 数え上げするための条件がいくつかあり、どうやって解くんだとなった。

感想

最近はちょっとコンテストに心を奪われ過ぎだと思う。もっと冷静にならんかねぇ。 あまりにも集中しようとしてピリピリしすぎだ。これじゃ考察もうまく行かないんじゃないかなぁ。 まあ今回は解けるものは解いたからなんともという感じだけど、速解きできなかったのがちょっと悔やまれる。 決して爆死ではないけどね。

今パフォーマンスが出た。1927か。あれ上がったｗ +1 だけど。