ABC459参加記

はじめに

おはようございます。Twil3akineといいます。初めての記事、緊張します。本当のところを言うと、約1ヶ月ぶり(4/18)のRatedだったので割と緊張しました。マジで緊張しました。半分怪しい4完で無事に温まったので、OKです。

[レートが温まっている図]

なお、記事中に掲載しているURL先のコードはコンテスト後に綺麗に整形したコードです。
あと、私はRustaceanなので、そこらへんはご了承ください。_( ・ ω ・ )_
今回は少しレイアウトを模索してます。そこもご了承ください。

問題ページ: A - Hell, World!

Aは安心のAを体現した問題でしたね。もちろん皆さん for文 を用いて $X$ 文字を削除しましたよね？

私はもちろん難しいメソッドとかは知らないので、for文 でいい感じにやりました。

問題ページ: B - 459

私はこの問題を許しません(1敗)。~~めんどくさいB問題よりかはいいんですけど、~~ ちゃんと凝視しながらコードを書かないとWAになるような問題ってすごいこう…嫌じゃないですか？

嫌じゃない…？まぁそういう人もいますよね。

Rustはこういうパターンマッチングは結構強いのでこういうところはとても好きですね。

ちなみに、元ネタはスマホのフリック入力らしいですね。そう聞いたら、いい問題…なのか？

問題ページ: C - Drop Blocks

まず、懺悔ポイント1です。正攻法がわからなかったので、セグメントツリー略してセグ木を使わせていただきました。

完全に言い訳なのですが、C問題でセグ木使いたくないなぁ、絶対に何か正攻法があるはずなんだけどなぁ、なんなら絶対これなんやろうけどなぁ、でも実装がわけわからんからなぁと考えた結果、セグ木になりました。

まぁ、本当にここ2,3日以内にライブラリに入ったことに起因する、『使い方がわかってない』によって、3ペナを出したのはまた別のお話…

ここから真面目なお話

クエリ1の『全部のマスに1つ以上のブロックがあるとき、全マス1つずつ取り除く』と言うのは、本当に全部のマスのブロックを1つずつ取り除くのではなく、『全マス何個取り除いたのか』を変数として持っておくと良いです。
クエリ2について、和を持つセグ木(RSQ)を使用することで、まず max_right で何回ブロックを取り除いたのかを取得し、その数を u と置くと、『y+u 個以上ブロックが積まれていないマスの個数』を取得し、全体のマスから引くと求めるものを得られる、と言うことになります。

正攻法については、おいおいやっていこうと思います。

nsubaru に言われて、max_right を実装しておいて本当に良かったなぁ。と言う気持ちです。感謝感激雨霰ですね。

さて、ここが懺悔ポイント2となり、ここまでしか解けなかったのですが、 $\sum\limits S \leq 10^6$ なので、スタックとかそこらへんの $O(N)$ だろうと考えたのですが、一向にわからないので、謎貪欲を考え、それが通らなかったらもう帰ろうと言う感じでいました。

謎貪欲の詳細

出現回数が最も多い文字を取得(pop)し、解答配列の最後尾と比較し、違うならその取り出した文字を、同じ文字なら取り出した文字は Heap に戻し、その次に Heap に入ってる文字を取り出して答え配列に追加。
追加した文字の出現回数を -1 し、Heap に戻す。
解答配列の最後尾と最初に取り出した文字が同じ時に、残りの Heap が空になった時、No を出力し、次の $S_{i + 1}$ に進む。

これで実装して、提出すると AC になります。

ただ、コンテスト後にサークルメンバーに教えてもらったのですが、奇数文字目を先に埋めて、偶数文字目を埋めていく貪欲で通るらしいですね…流石に目から鱗案件でした。

（これ以降の問題文は割愛します。）

次に私が記事を書くのは私が入緑した時でしょう… ここまでお読みいただきありがとうございました。またお会いいたしましょう。