こんにちは、KCPC代表のm1uneです！今回はABC381の感想記事を書きます。
コンテスト前の私のレートは1563で、1885 perfが出せれば入青ということで、それを目標にしていました。
前回のABC380で2018 perfを出せているので、今回もうまい具合に頑張ろうという気持ちでしたが…… 結果としては見落とし、誤読、嘘解法のオンパレードとなってしまいました。
目次
ABC381
ABC381は珍しく金曜日に開催されましたが、これはABC230以来、約3年ぶりのことだそうです。
平日開催ということもあって普段よりも参加者数は少なかったようです。（前回のABC380ではA問題の正解者数が9709人だったのに対し、今回のABC381でA問題の正解者数は5892人）
さて、コンテストが始まり問題一覧ページを開くと、そこには異様な光景が！
1122ばっかりでなんだか嫌な予感。何はともあれ、早速A問題から解いていきます。
A問題
問題文: A - 11/22 String
KCPCメンバー(rated 参加)のAC数: 5/5
150点とA問題にしては少し高めの点数設定ですが、いつもに比べて特に難しいということもなさそう。
文字列の長さが偶数ならNoで、奇数のときに前半が1、中央が/、後半が2になっていればYesでそうでないならNoです。
上記をそのまんま実装して（後述のRLEを使った方が楽だったかも）、2:19に提出、無事AC。
B問題 見落とし
問題文: B - 1122 String
KCPCメンバー(rated 参加)のAC数: 5/5
文字列が3つの条件を見たすかどうか判定せよという問題で、これ自体は何も難しいことはありません。
しかし、なぜか私はここで2つ目の条件を見落としてしまい、各文字が2回ずつ含まれていればいいと勘違いしてしまいました。
これでもサンプルは通ってしまうので、提出するもWA。問題文を読み返してみて、見落としに気づきました。
コードを修正し5:19に提出、無事AC。
C問題
問題文: C - 11/22 Substring
KCPCメンバー(rated 参加)のAC数: 5/5
RLE（ランレングス圧縮）を使えばこの問題は簡単に解けます。RLEは最近のコンテストで頻出なので、ライブラリとして整備しておいた方がいいと思います。
ランレングス圧縮をした後、1...1/2...2となっている部分のうち一番長いものを探せば良いので、すべての長さ1の'/'の列に対してその左側に'1'、右側に'2'が来ているときにその'/'を用いて構築できる11/22文字列の長さを求めればよいです。
ということでそれを実装して12:03に提出して無事ACしたのですが………
実はこの提出コード、'/'の列の長さが1であることを判定するのを忘れてしまっているため、
4
1//2
という入力に対して3を返してしまいます。（正しくは1）
これはテストケースが弱くて助かりましたが、とってもダメですね…。まだafter_contestも追加されていないようですが、多分いずれ追加されるんじゃないかな？
D問題
問題文: D - 1122 Substring
KCPCメンバー(rated 参加)のAC数: 5/5
連続部分列で1122数列となるようなものは、偶数番目はじまりか奇数番目始まりかで分けて考えると考えやすいです。
2個ずつで数字が続いている部分列を列挙して（このさい数字の重複は問わない）、ここで列挙した部分列それぞれの部分列のうち数字の重複していない最長の1122数列を、尺取り法で求めることができます。
以上のことを実装して25:20に提出、無事AC。
やたらたくさんafter_contestが追加されたようですが、これなんなんですかね？（無事通過していました）
E問題その1 誤読
KCPCメンバー(rated 参加)のAC数: 3/5
問題のE問題。B問題で見落としをしていまっていたこともあり、ここは注意して問題を読むべきところなのですが、11/22文字列の定義はさっき見たな〜ということで飛ばし読みをしてしまいました。
その結果、ここで求めないといけないのは11/22文字列である最長の(連続とは限らない)部分列なのですが、これを連続部分列と誤読。せっかく太文字にして強調してくれているのに…
誤読に気づかないまま、35分ほどを連続部分列の場合の解法の構築に費やしてしまいました。連続部分列の場合、この問題は各スラッシュがなす11/22文字列の長さをセグ木に載せて、区間内の両端のスラッシュについて調整を加えることで解くことができます。
結局この誤読に気づいたのは、サンプルでテストを実行したときで、そのときにはすでに10時近くなっていました。あーやってしまったーーと思いましたが、残り40分でできる限りのことをするしかありません。
ここで私には2つの選択肢がありました。E問題を諦めてF問題にいくか、E問題をもう一度頑張るか。戦略としては点数の高いF問題が取れた方がいいのですが、一瞬F問題を見てbitDPぽいな〜でも遷移わからないな〜にしかならなかったのでE問題に再度集中することにしました。
E問題その2 嘘解法
さて、連続とは限らない部分列を求めよということですが、なんとなくいい感じに真ん中の方のスラッシュを選んだ方がいいんじゃないかな？という直感がありました。そこで以下のようなグラフを考えると、答えのスラッシュの位置は三分探索で求まりそうだと考えました。
三分探索を使うのは初めてだったので三分探索が想定解法の問題の解説を見ながら実装するも、全然答えが合わず、添字間違いなどを疑って色々しますが、なにも改善しません。
ロジックに間違いがあるのかもしれないと思って上のグラフをもう一度にらんでみても、何が間違っているのかがわからず結局そのままコンテストが終了してしまいました。
コンテスト終了後も通らない理由がわからずTwitter(X)で訊いてみたところ、物理好きさんにダメなケースを教えてもらいました。
///////////1/2// みたいな時に綺麗に見つけられない
— 物理好き (@butsurizuki) 2024年11月22日
そう、三分探索では狭義単調増加・狭義単調減少が成り立っていないと（平坦なところがあると）適切に探索ができないのです。私はそれを知らなかったため、ロジックの誤りに気づけませんでした。といっても、三分探索で全然合わない時点で何かほかの解法を模索するべきでしたね…。
コンテスト結果
結果として、ABCD4完となってしまいました。perfは1302で、レート差分は1563→1539の-24となってしまいました。F問題のbitDPの筋をもうちょっと詰めていればワンチャン解けたかもな〜とも思いますが、これは結果論ですね。
KCPCブログはなぜか負け率が高く、前回の記事でjastawayさんが負け続きの流れを打ち切ってくれたのにまた負けてしまいました。次の人、頑張ってくれ〜！w
誤読や見落としに関しては2週間前のABC379でも酷い目にあっているので、本当に気をつけないとまずいです。
今回のコンテストで学んだこと:
問題文をちゃんと全部読む！！！！！！！！！！！
三分探索は平坦なところがあるときは使えない
以上です！最後まで読んでいただきありがとうございました！今日のARCも頑張りましょう！
