AtCoder Regular Contest 132 参加記

2021/12/26に開催されたAtCoder Regular Contest 132に参加しました。

atcoder.jp

2021年最後のRatedコンテストなので、とりあえず目標はレート上げ。気分良く今年の締めくくりができればという気持ちで臨むこととしました。

今回の結果

で、肝心の結果ですが、なんとか2完が確保できたというとこです。

ARC132結果
ARC132結果

パフォーマンスは、現レートよりちょい悪というところでして、結果としてはレート-1というなんとも中途半端な内容となってしまいました。

振り返り

B問題をめちゃくちゃ苦労してなんとか通すことが出来ました。

ARC132提出結果
ARC132提出結果

A問題

A - Permutation Grid

一読して、初手から解法がよく分からん問題がきたかという印象。制約条件より、2次元配列を生成して中身を埋めてから実行するというのも大分苦しそうである。

それでも、A問題からいきなり諦めるわけにはいかないということで考察をしていく。まずは条件を満たす塗り方がちょうど一通り存在するということで、各条件においてどういう塗り方となるかを考えると、R_iC_jnの行と列は全て黒で確定し、その次に、R_iC_j1の行と列について、先に塗ったマス以外は全て白で確定することはわかった。

次に同様の要領で、R_iC_jn - 1の行と列、次にR_iC_j2の行と列という具合に塗る色のが特定できる。この要領でサンプルケースを実際に塗ってみると、以下のように問題文の説明と同様の塗り方ができる。

 42315
5#####
2#...#
3#.#.#
4###.#
1....#

後はこの図を見た時に、白のマスと黒のマスでなんらかの法則性があるかを見てみると、どうも黒のマスのみR_i + C_jの値が大きくなりそう。ということで、答えはR_i + C_j \gt nの場合は黒、それ以外は白ということでした。

あとは実装して、ACを取ることができました。

提出コード

https://atcoder.jp/contests/arc132/submissions/28171316

B問題

B - Shift and Reverse

こちらも一読して、解法がよく分からん問題がきたかという印象。考えてはみるものの何も分からずで時間だけが溶けていきました。

で、30分以上あれこれと考えてみたところ、問題文の操作で並び替えができるのは元々昇順で並んでいる数列を何回かシフトするか、一度だけ逆順にひっくり返すリバース操作を行ったものなので、配列中の1の位置と、全体として昇順、降順どちらで並んでいるかという事に着目すればよいというのがやっとのことでわかりました。

で、元の入力が昇順の場合は、1が先頭になるまでシフトするか、一度リバースした後 1が最後尾になるまでシフトして再度リバースする操作のどちらかで、操作回数が少なくなるものを選択すれば良い。

また、元の入力が降順の場合は、 1が最後尾になるまでシフトしてからリバースする操作か、先にリバースをしてから1が先頭になるまでシフトする操作のどちらかで、操作回数が少なくなるものを選択すれば良い。

とここまで考察するのに小一時間かかってしまったのですが、あとは実装をするのみ。なんどかバグらせてWAを出したのち、やっとのことでACを取ることが出来ました。

前回より大分遅めの、開始100分弱で2完達成です。

提出コード

https://atcoder.jp/contests/arc132/submissions/28177702

C問題

C - Almost Sorted

残りが20分程度あったので、問題には目を通してみたものの適切な手法が思いつかずでした。

D問題

D - Between Two Binary Strings

ワンチャンあるかと思い、問題だけは覗いてみたものの何も分からず。

E問題

E - Paw

問題すら見ておりません。

F問題

F - Takahashi The Strongest

問題すら見ておりません。

これまでの実績

2021年最後のRatedコンテストは、やたら苦労した挙句にレート-1というなんとも微妙すぎる結果となりましたとさ。

コンテスト実績
コンテスト実績

総括

今回のARCでは、AB問題もすぐには解法が見出せずで、苦労させられました。そんな中でも諦めずに地道に問題に取り組むことでなんとか最低限の結果は確保できたのは、それなりに自分が成長した結果なのかという感じが致します。

今年1年間AtCoderに取り組んだ結果としては、レートが200少々上がったという結果でした。途中競プロに取り組めない時期もあり、レートがダダ下がりになる時期がありましたが、後半にかけて精進を継続することでなんとか巻き返しが出来たのは非常によかったですね。

来年も精進を継続して、少しでも上の色、レートに到達できるようにしていこうと思います。

ということで、また来年も頑張ります。