はじめに
はじめまして、みうね(m1une)です。KCPC（京都大学競プロサークル）のブログを開設しました！
これから毎週、KCPCメンバーの有志が交代でABCの感想や考えたことなどを記事にしてこのブログに挙げていく予定です。
また、ABC以外についての記事も、不定期で上げていければいいなと思っています。
京都大学に在籍している競プロerでKCPCに興味がある方は、私のTwitterまでご連絡ください！
目次
ABC372
参加前の私のレートは1394で、直近の目標としては入青があるので目標perfは1600を目安にしていました。
当日は少し風邪気味だったため多少の不安はあったものの、コンテスト参加に支障をきたすほどではなかったのでいつも通りratedで参加しました。
以下、コンテストで取り組んだ順に問題を紹介していきます。（といっても前から順番通りです）
A問題
問題文: A - delete .
KCPCメンバー(rated)のAC数: 11/11
diff: 46
問題を見て、最初C++のstring.erase()をset.erase()みたいに要素を指定して消したりできないのかな？と思って書いてみたらコンパイルが通らなかったのでできないらしい。
そこで、方針変更して空文字列Tを用意してSの手前から順に S[i] == '.' でなければ T += S[i] としました。
1度方針変更をはさんだので多少無駄な時間をかけてしまったが1:23に提出、無事AC。
B問題
問題文: B - 3^A
KCPCメンバー(rated)のAC数: 11/11
diff: 131
Mを3進数に直してやればいいな！ということに気づき、Mを3進数に変換した後いい感じにAを構築。
無事サンプルも通り、4:29に提出。
C問題
問題文: C - Count ABC Again
KCPCメンバー(rated)のAC数: 11/11
diff: 341
C問題なので、どうせ全探索でいけるんじゃない？と思って制約をみると、 $ O(NQ) $ は無理そう。
1回のクエリで更新されるのは1文字だけなので、その周りだけ見てABCの部分文字列の増減を調べると良さそう。
よって、はじめに一回部分文字列ABCの数を全て調べて、そのあと各クエリごとに文字変更前に変更する文字が部分文字列ABCの構成員になっているなら答えをひとつ減らし、変更した後の文字が部分文字列ABCの構成員になっていたら答えをひとつ増やせばよさそう。
以上のことを実装して12:13に提出、無事AC。
D問題
問題文: D - Buildings
KCPCメンバー(rated)のAC数: 11/11
diff: 901
「間」の定義が曖昧だけど、入出力例を見る限りでは、端っこは含まないらしいということがわかった。（端は含まないということは問題文に明記して欲しかったかも）
なんだこれ、増加部分列の長さを求めればいいのかな？と思って実装を始めかけるが、入力例1をみてこれが間違っていることに気づく。
そこで、各ビルが答えに及ぼす寄与を考えると、ABC371Eと同じように解けないかなと考えた。
各$i = 1 \ldots N $ について、$i$よりも大きい数字が最後に出てきたindexというのを考えると、このindexは区間加算&1点取得が可能なデータ構造があれば管理できることがわかる。
よって遅延セグメント木で上述のindexを管理し、答えをimos法で管理するとこの問題を解くことができる。
以上のことを実装して23:48に提出、無事AC。
順位表確認
ここで一度順位表を確認した。すると、もう解けたと思っていたはずのB問題がなんと(1)になっていた！
びっくりして自分の提出を確認してみると、誤ってAの最大値を9にしてしまっていることに気づき修正。26:01に再度提出し、無事ACした。
ここで順位表を確認していなければ気づくのはもっと後になっていたかもしれず、恐ろしい… みんなはちゃんと自分の提出がACになっているかどうか確認しましょう。
E問題
問題文: E - K-th Largest Connected Components
KCPCメンバー(rated)のAC数: 9/11
diff: 1042
atcoder::dsuを使えばよさそうだな〜と思った。 $ 1 \leq k \leq 10 $ なので各リーダーについて連結成分の上位10個の頂点番号を持てばよさそう。
そこで $ N \times 10 $ の2次元vectorを作り、dsuでmergeする際に前のleaderがもつ頂点番号から大きい順に頂点番号を新しいleaderに持たせればよい。
ここで、岩井星人さんのツイートでmergeする際leaderは前の2つのいずれかのleaderになるとは限らないというものを見て、それでも問題ないように今回は実装した。しかし、C++のatcoder::dsuの場合は新しいleaderは元のleaderのいずれかになるようである。Rustのdsuではそうはなっていないのか…？
また、内部的に各連結成分ごとに代表となる頂点を 1 つ持っています。辺の追加により連結成分がマージされる時、新たな代表元は元の連結成分の代表元のうちどちらかになります。 (https://github.com/atcoder/ac-library/blob/master/document_ja/dsu.md より引用)
以上のことを実装して40:13に提出、無事AC。
F問題
問題文: F - Teleporting Takahashi 2
KCPCメンバー(rated)のAC数: 5/11
diff: 1728
Mが小さい。疎なグラフなので、隣接行列を疎行列とみなせるので行列累乗で解けるのではないかと思った。しかし、実装を進めるうちに、もとの隣接行列が疎行列であったとしても累乗すると密になってしまうことに気づき、挫折。ここまでで30分ほど浪費してしまった。
いったん問題文をもう一回見返して入出力例を見直してみたところ、これはDP配列全体を毎ターン時計回りにひとつずつずらしていくと解釈すれば更新がM回で済むから間に合うなということに気づく。
ということでターンごとにM本の辺をひとつずつみてDP配列を更新するコードを書き、サンプルも通ったので79:22に提出するが、WA×15で合わず。
考え方が合っているか再度確認して、コードで怪しそうなところを探したが、結局このWAの原因はコンテストが終わるまでわからなかった。
コンテスト後
ツイッターで解答と考え方は同じはずなのにWAが出ると嘆いていたら、FFの人に原因を教えてもらった。ありがとうございます。
インラインDPでやりがちなミスだが、DPを更新する際に、更新前の情報を参照しなければならないところを更新後の情報を参照してしまっているところがあった。このミスは前にもした覚えがある（確かEDPC）ので、要反省である。
また、G問題にも取り組んでみた。赤diffではあるものの、考え方自体は凸包とfloor_sumの組み合わせでそこまで難しいわけではない。ただ、実装がかなり大変で普通に実装すると浮動小数点まみれになって少数誤差で死にそうである。解答はうまいこと少数を回避しており、それを見ながらではあるが自分でも実装してみた。
コンテスト結果
結果的に私はA-Eの5完（40分+1ペナ）でperfは1495であった。Bの1ペナによりperfが35ほど下がっているのは勿体無いが、それ以上にFを通せなかったのが悔しい。
インラインDPの更新には気をつけましょう。
あと今日のARCの配点怖すぎです(A問題600点)
