2022/3/19に開催されたAtCoder Regular Contest 137に参加しました。
先週のABCコンテストでなんとか連敗をストップすることができ、レートも4桁に復帰しました。
今回はARCということで、問題セットによっては0完爆死もあり得るかというところですが、なんとか2完いけたらという気持ちで臨むこととしました。
Rated参加します。とりあえず目標は2完以上ということで。
— devgenjin77 (@devgenjin77) 2022年3月19日
AtCoder Regular Contest 137 - AtCoder https://t.co/XISLNwgbtC
今回の結果
で、今回はなんとか2完を確保することができましたー。
パフォーマンスは緑上位ぐらい出てくれまして、レートは上昇。なんとか連勝することができましたとさ。
2完4ペナでも緑パフォまで出てくれて、なんとかレート上昇となりました😂😂
— devgenjin77 (@devgenjin77) 2022年3月19日
次のABCも頑張ります✊
devgenjin77さんのAtCoder Regular Contest 137での成績:1512位
パフォーマンス:1153相当
レーティング:1027→1040 (+13) :)#AtCoder #ARC137 https://t.co/z0dX3DoGF6
振り返り
ペナが多めだったのが反省点です。
A問題
初手のA問題から、よくわからん問題。。まさかの0完もあるかと冷や汗をかきました。。
20分ぐらい経とうとしたところで、とりあえずなんか出さねば、ということで嘘解法でも通らないか試してみることに。
まず、とし、になるまで、を1引いていくやり方を実装。これはサンプルが通ったものの、投げてみたらWA。。
それならばと、今度は逆にになるまで、を1足していくやり方を実装。が、、これも投げてみたらWA。。
が、この2つのプログラムがともに実行時間が100ms切るぐらいだったので、結局答えが見つかるまで全探索してもTLEしないのでは??
ということで、結論としては、愚直に全探索を実施するのが正解だったようです。。
のとる値を以上且つ、となる最小の値の範囲とし、のとる値を、以下且つ、となる最大の値で全探索を実装し、なんとか問題なくACが取れましたとさ。
32分45秒の2ペナという、かなり残念なタイムで1完。
提出コード
https://atcoder.jp/contests/arc137/submissions/30234767
B問題
1回操作することで作れるスコアの最大値と最小値の範囲のスコアは任意に作成できる。よって、作成できるスコアの最大値と最小値を求めることにする。
で、当初最小値のスコアを作るためには、が最大限連続する箇所をに置き換えればよく、また、最大値を作るにはが最大限連続する箇所をに置き換えればよい、というふうに考えておりました。これの実装はサンプルが通ったのですが投げてみたらWAという結果。。
実装のバグかと思い少し変えたものを投げてみるも、これもWA。。
WAの原因が全く思いつかずで、これは詰んだかと思いましたが、よくよく考えてみるとの部分列をflip操作するとスコアが上がるよね、ということに気づいてしまう。そもそも解法が全然間違っていました。。
ということで、スコアの最小値を作るには、の個数 - のの個数が最大となる部分列を求めればよい。また最大値も同じ要領で、の個数 - のの個数が最大となる部分列を求めればよい。
これで、実装後提出したら、やっとこさACが取れました。
73分29秒の4ペナという、だいぶ微妙なタイムですが、とりあえず2完を確保。なんとか爆死を免れたかというところです。
C問題
順位表をみると、AC数が300行かないぐらいの問題だったので、だいぶ諦めモードというところではありましたが、とりあえず考えてみることに。
とはいうものの、いろいろなケースを考えてみるも、最善の戦略が何になるのか、どの要素が勝敗に絡むのかというところが全く見当がつかず。
このまま考えても時間切れになるだけというところで、とりあえず嘘解法でもよいから投げてみることに。数列をとりあえずソートして、隣同士の差分を求めることで、次に選ぶことができる数の種類数を求めてみる。この種類数の偶奇で先手後手どちらが勝ちかを決めてみることに。
で、これで通る程世の中は甘くないようで、WA×6を喰らってあえなく終了。これで時間切れとなりましたとさ。
とはいえ、嘘解法でも、AC×36は取れているので、惜しいところは行っていたのかなーという印象です。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
これで、直近2連勝!なんとか連敗で減らした分の半値以上戻しに成功しました。
総括
今回のA,B問題は、もう少しよく考えればペナ無しで解けたかというところ。最近考察が雑になりがちな傾向があるようなので、正確性を重視して考察できるようにしないといけないですね。
今回一応、比較的良いパフォーマンスが出たものの、できれば水色を安定して出したいところなので、引き続き精進していこうと思います。
ということで、また次回も頑張ります。