AtCoder Regular Contest 130 参加記

2021/11/28に開催されたAtCoder Regular Contest 130に参加しました。

ARCはめちゃくちゃ久しぶりの参加。ここ最近は基礎を固めようということでABCコンテストに絞って参加するようにしてきましたが、この前日に行われたABC229は都合がつけられず不参加となり、あまり間を開けたくなかったのと、そろそろARCも参加してみようかなーという気まぐれが合わさり、今回参加することになりました。

これまでのARCの最高記録は3完というところ。直近のARCも問題ぐらいは目を通していたのですが、この難易度ぐらいだと2完はできればレート維持は可能かな、という感じだったので、とりま2完が目標ということで臨んでみることにしました。

久々のARC参加。なんとか2完できるように頑張ってみます！
AtCoder Regular Contest 130 - AtCoder https://t.co/liOJDl2ets
— devgenjin77 (@devgenjin77) 2021年11月28日

今回の結果

で、今回はなんとか2完を確保できました。とりあえず有言実行です。

が、、なんとパフォーマンスはギリギリ緑にのった程度しか出ず、久しぶりのレート減という結果になりました。。

2完取れたもののギリギリの緑パフォでレートは微減となりました😢
連勝は途切れましたが、また気持ちを切り替えて、次頑張ります。
devgenjin77さんのAtCoder Regular Contest 130での成績：1193位
パフォーマンス：868相当
レーティング：931→925 (-6) :(#AtCoder #ARC130 https://t.co/SoDhOrGJ4s
— devgenjin77 (@devgenjin77) 2021年11月28日

振り返り

A、B問題ともなんとか解けたという体たらくでした。

A問題

A - Remove One Character

初っ端のA問題から問題の理解に苦しみましたが、サンプルをみると、同じ文字が連続する回数を見ていけば良さそうという印象。

文字列を先頭から見ていき、同じ文字が2連続以上した場合連続した回数をリストに追加。あとは、リストに追加した回数 $K$ に対して、初項１、公差１、項数が $K - 1$ の等差数列の和を答えに加算していくことで解けそうかと。

で、ここまでの考察とか等差数列の公式をググったりという作業で時間はかかりましたが、なんとかACを取ることが出来ました。

提出コード

https://atcoder.jp/contests/arc130/submissions/27570725

B問題

B - Colorful Lines

与えられたクエリを順番に処理するためには、どの色が上塗りされて消されたかという情報を逐次更新していく必要があり、マス目の大きさやクエリ数の制約からすると愚直にこれを行うのは難しそう。

だからといって、これを解くために必要な典型アルゴリズムがあるのかもよくわからずで、いろいろ思考を廻らせるも解決策が見えずで、20分以上時間を浪費しましたが、最後のクエリから逆順で処理をしていき、１列を塗る場合は、これまでに塗った行数分のマス目を、１行を塗る場合は、これまでに塗った列数分のマス目を引いてやることで上手く計算ができることに気づいた。

あとは、塗った列番号、行番号をそれぞれ別のSetで管理し、クエリのタイプごとに差し引くマス目を求めることで実装、なんとかACが取れてくれました。

これでなんとかノルマの２完達成。このときはまさかレートが冷えるとは思いもしませんでした。。