2022/9/17に開催された、UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)に参加しました。
参加前時点で、Ratedコンテスト3連敗中という状況でした。今回のコンテストは、この悪い流れを断ち切るべく、まずは連敗を止めようという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年9月17日
現時点でRated3連敗中なので、とりあえずは連敗を止められるように頑張ります。
UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) - AtCoder https://t.co/jh80aCVROP
今回の結果
今回は、なんとか5完という結果を残すことができましたとさ。
パフォーマンスは、水色にギリ届かずというところでしたが、なんとか現レートを上回りました。なんとか連敗脱出に成功です。
5完緑パフォで連敗阻止😂
— devgenjin77 (@devgenjin77) 2022年9月17日
次も頑張ります✊
devgenjin77さんのUNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)での成績:1591位
パフォーマンス:1196相当
レーティング:1110→1119 (+9) :)#AtCoder #UNICORNプログラミングコンテスト2022(ABC269) https://t.co/97dwQXw8ru
振り返り
Eに時間が掛かりすぎだった感があります。
A問題
簡単な計算問題と、固定文字列出力を行うだけのシンプルな問題。
やるだけの実装をして提出。問題なくACが取れました。
1分26秒で1完。
提出コード
https://atcoder.jp/contests/abc269/submissions/34919787
B問題
グリッド上の四角形の四隅を求める問題。なんか、PaizaのCかBぐらいに出てきそうな感じ。
解法としては、グリッド上を2重ループで走査し、以下の要領で計算すればよい。
は#が出てくる行の最小値
は#が出てくる行の最大値
は#が出てくる列の最小値
は#が出てくる列の最大値
あとは、実装して、一度の提出でACが取れました。
8分7秒で2完。ここまでは、まあまあのタイムです。
提出コード
https://atcoder.jp/contests/abc269/submissions/34925918
C問題
を2進数で表した時、となる位は個以下との制約があるので、となる位をbit全探索して、を構築していけば良い。
あとは、実装して提出。問題なく一発でACが取れました。
20分13秒で3完。
提出コード
https://atcoder.jp/contests/abc269/submissions/34932002
D問題
連結成分の数を答えるということで、Union-Findを使う系の問題であることはわかった。
あとは、この大戦略のマップのような六角形のマップの連結を、どうやって判定するかで少々悩んでしまう。
しかし、よくよく考えると、四角形のグリッドを移動するときに使う4通りの移動方法をdx,dyの配列で実装するのと同じ要領で、6通りの移動方法を決めればよいということに気づく。
あとは、実装して提出。問題なくACが取れました。
32分48秒で4完。
提出コード
https://atcoder.jp/contests/abc269/submissions/34936553
E問題
忘れた頃にやってくる、インタラクティブ問題。
今回は、二次元グリッド上に配置されている、どのルークにもぶつからないようにルークを置ける点を見つけるという問題。
当初考えた解法は、二分探索の要領で解く方法。
まず、グリッドを縦に半分に切った領域の左側にあるコマの配置数を求め、半分に切ったどちらにルークが置ける余地があるかを求める。
次に、その領域を横に半分に切って、縦の場合と同じ要領で、半分に切ったどちらにルークが置ける余地があるかを求める。
が、これで実装して、自作のテストケースで色々試してみたが、どうしても正解に辿り着けていない。。
ここで大きな勘違いをしていたことに気づく。要は、シンプルに、縦に半分に切っていく二分探索を行うことで、新たに配置できるルークのの位置を求め、次に横に半分に切っていく二分探索で、の位置を求めるのが正解だった模様。
結局、最初の考察が大間違いだったが仇となり、大幅に時間をロスしたものの、最後はなんとか実装してACを取り切ることができました。
81分59秒で5完。この時点で、順位表を見ると、多分今回は負けはないかな?という位置でした。
提出コード
https://atcoder.jp/contests/abc269/submissions/34948569
F問題
残りが20分弱あるので、なんとか解けるかと問題を見ましたが、解法にたどり着けず。
ここで、時間切れとなりましたとさ。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
ほんの僅かではありますが、これまでの負け分を少し取り戻しました。
総括
なんとか連敗を止めることはできましたが、E問題で大分もたついたのが、今回の反省点。とくに、最初の考察時点で破綻していたのを実装まで進めたのは大きな痛手でした。
やはり、考察が雑なので、まぐれで当たれば良い結果がでるものの、当たらなければ今回のように大幅に時間ロスをするという事態を引き起こしているような気がします。
考察の精度を高めていくのが、今後の大きな課題ですな。
ということで、また次回も頑張ります。