115. 【入水】AtCoder参加記録（AtCoder Beginner Contest 253）

21回参加でレート 1221 です。水色になりました！

今日はとりあえずいつもの記録用記事を書いて、入水記事はまた別に書こうと思います。

今回はパフォーマンス 1701 です（自己ベスト）。

ABCDEFを通して、GExは未解答です。Eで2ペナ。

各問題の感想など。

A

1分32秒。

やり方は色々あると思いますが、ソートして真ん中の値と を比較する方法にしました。

B

3分22秒。

マンハッタン距離を出せばOKです。

C

10分43秒。

Dictionary で各値がいくつ含まれているかと、MultiSet でキーを昇順・降順それぞれ保存していい感じに実装します。

D

7分17秒。

包除原理の簡単なやつを使う問題。

「1～Nの和」から、「Aの倍数 または Bの倍数」の数を引けばいいです。

E

初回提出15分17秒、そこからACまで7分51秒。

として DP。最小ケースで範囲外アクセスすることに気付けず、無駄に2ペナ。これはもったいなかったです。

F

53分30秒。終了28秒前の提出…！

色々考えましたが、最終的に以下のような思考にたどり着きました。

• クエリ1 のみなら遅延評価セグメント木で計算が間に合う
• そもそも慎重に考える必要があるのは「クエリ3」の対象となっている成分のみ
• ある成分が「乱される」のは「クエリ2」の影響による場合のみで、出力の直前にある「影響するクエリ2」のみに依存している
• クエリ3 で対象とする行と、そこに影響するクエリ2 を予め覚えておき、「影響するクエリ2」実行後の値・セグ木のその成分の値を記憶しておく。クエリ3 にたどり着いたとき、「クエリ2実行後の値 + セグ木の現在値 - セグ木の過去値」を出力する

時間が無かったので入力例1 が合っているのを確認して即投げしましたが、WAが出ずジャッジが通っていく様を見て「うおお…」ってなってました。

G, Ex

見てないです。

前回「まだ水色遠いな～」と言っていましたが、運良くFを通せて無事入水できました！！最近は青diffを中心に解いていて、今日初めて自力で通すこともできましたが、その成果が出てきたように思います（今日のFも青中位寄りのdiffでしたね…）。

もともと緑くらいのパフォはコンスタントに出していて実質緑からのスタートでしたので、ようやく成長が表に出始めた感じがあります。というわけで、初めてのまともな（？）色変記事を別にまとめようと考えています。

とりあえず、色が変わって嬉しい！