UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)参加記

2022/9/17に開催された、UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)に参加しました。

atcoder.jp

参加前時点で、Ratedコンテスト3連敗中という状況でした。今回のコンテストは、この悪い流れを断ち切るべく、まずは連敗を止めようという気持ちで臨むこととしました。

今回の結果

今回は、なんとか5完という結果を残すことができましたとさ。

ABC269結果
ABC269結果

パフォーマンスは、水色にギリ届かずというところでしたが、なんとか現レートを上回りました。なんとか連敗脱出に成功です。

振り返り

Eに時間が掛かりすぎだった感があります。

ABC269提出結果
ABC269提出結果

A問題

A - Anyway Takahashi

簡単な計算問題と、固定文字列出力を行うだけのシンプルな問題。

やるだけの実装をして提出。問題なくACが取れました。

1分26秒で1完。

提出コード

https://atcoder.jp/contests/abc269/submissions/34919787

B問題

B - Rectangle Detection

グリッド上の四角形の四隅を求める問題。なんか、PaizaのCかBぐらいに出てきそうな感じ。

解法としては、グリッド上を2重ループで走査し、以下の要領で計算すればよい。

  • Aは#が出てくる行の最小値

  • Bは#が出てくる行の最大値

  • Cは#が出てくる列の最小値

  • Dは#が出てくる列の最大値

あとは、実装して、一度の提出でACが取れました。

8分7秒で2完。ここまでは、まあまあのタイムです。

提出コード

https://atcoder.jp/contests/abc269/submissions/34925918

C問題

C - Submask

Nを2進数で表した時、1となる位は15個以下との制約があるので、1となる位をbit全探索して、xを構築していけば良い。

あとは、実装して提出。問題なく一発でACが取れました。

20分13秒で3完。

提出コード

https://atcoder.jp/contests/abc269/submissions/34932002

D問題

D - Do use hexagon grid

連結成分の数を答えるということで、Union-Findを使う系の問題であることはわかった。

あとは、この大戦略のマップのような六角形のマップの連結を、どうやって判定するかで少々悩んでしまう。

しかし、よくよく考えると、四角形のグリッドを移動するときに使う4通りの移動方法をdx,dyの配列で実装するのと同じ要領で、6通りの移動方法を決めればよいということに気づく。

あとは、実装して提出。問題なくACが取れました。

32分48秒で4完。

提出コード

https://atcoder.jp/contests/abc269/submissions/34936553

E問題

E - Last Rook

忘れた頃にやってくる、インタラクティブ問題。

今回は、二次元グリッド上に配置されている、どのルークにもぶつからないようにルークを置ける点を見つけるという問題。

当初考えた解法は、二分探索の要領で解く方法。

まず、グリッドを縦に半分に切った領域の左側にあるコマの配置数を求め、半分に切ったどちらにルークが置ける余地があるかを求める。

次に、その領域を横に半分に切って、縦の場合と同じ要領で、半分に切ったどちらにルークが置ける余地があるかを求める。

が、これで実装して、自作のテストケースで色々試してみたが、どうしても正解に辿り着けていない。。

ここで大きな勘違いをしていたことに気づく。要は、シンプルに、縦に半分に切っていく二分探索を行うことで、新たに配置できるルークのjの位置を求め、次に横に半分に切っていく二分探索で、iの位置を求めるのが正解だった模様。

結局、最初の考察が大間違いだったが仇となり、大幅に時間をロスしたものの、最後はなんとか実装してACを取り切ることができました。

81分59秒で5完。この時点で、順位表を見ると、多分今回は負けはないかな?という位置でした。

提出コード

https://atcoder.jp/contests/abc269/submissions/34948569

F問題

F - Numbered Checker

残りが20分弱あるので、なんとか解けるかと問題を見ましたが、解法にたどり着けず。

ここで、時間切れとなりましたとさ。

G問題

G - Reversible Cards 2

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

Ex問題

Ex - Antichain

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

これまでの実績

ほんの僅かではありますが、これまでの負け分を少し取り戻しました。

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

総括

なんとか連敗を止めることはできましたが、E問題で大分もたついたのが、今回の反省点。とくに、最初の考察時点で破綻していたのを実装まで進めたのは大きな痛手でした。

やはり、考察が雑なので、まぐれで当たれば良い結果がでるものの、当たらなければ今回のように大幅に時間ロスをするという事態を引き起こしているような気がします。

考察の精度を高めていくのが、今後の大きな課題ですな。

ということで、また次回も頑張ります。