AtCoder Regular Contest 137 参加記

2022/3/19に開催されたAtCoder Regular Contest 137に参加しました。

atcoder.jp

先週のABCコンテストでなんとか連敗をストップすることができ、レートも4桁に復帰しました。

今回はARCということで、問題セットによっては0完爆死もあり得るかというところですが、なんとか2完いけたらという気持ちで臨むこととしました。

今回の結果

で、今回はなんとか2完を確保することができましたー。

ARC137結果
ARC137結果

パフォーマンスは緑上位ぐらい出てくれまして、レートは上昇。なんとか連勝することができましたとさ。

振り返り

ペナが多めだったのが反省点です。

ARC137提出結果
ARC137提出結果

A問題

A - Coprime Pair

初手のA問題から、よくわからん問題。。まさかの0完もあるかと冷や汗をかきました。。

20分ぐらい経とうとしたところで、とりあえずなんか出さねば、ということで嘘解法でも通らないか試してみることに。

まず、x=L, y=Rとし、gcd(x,y)=1になるまで、yを1引いていくやり方を実装。これはサンプルが通ったものの、投げてみたらWA。。

それならばと、今度は逆にgcd(x,y)=1になるまで、xを1足していくやり方を実装。が、、これも投げてみたらWA。。

が、この2つのプログラムがともに実行時間が100ms切るぐらいだったので、結局答えが見つかるまで全探索してもTLEしないのでは??

ということで、結論としては、愚直に全探索を実施するのが正解だったようです。。

xのとる値をL以上且つ、gcd(x,R)=1となる最小の値の範囲とし、yのとる値を、R以下且つ、gcd(L,y)=1となる最大の値で全探索を実装し、なんとか問題なくACが取れましたとさ。

32分45秒の2ペナという、かなり残念なタイムで1完。

提出コード

https://atcoder.jp/contests/arc137/submissions/30234767

B問題

B - Count 1's

1回操作することで作れるスコアの最大値と最小値の範囲のスコアは任意に作成できる。よって、作成できるスコアの最大値と最小値を求めることにする。

で、当初最小値のスコアを作るためには、1が最大限連続する箇所を0に置き換えればよく、また、最大値を作るには0が最大限連続する箇所を1に置き換えればよい、というふうに考えておりました。これの実装はサンプルが通ったのですが投げてみたらWAという結果。。

実装のバグかと思い少し変えたものを投げてみるも、これもWA。。

WAの原因が全く思いつかずで、これは詰んだかと思いましたが、よくよく考えてみると(0,0,0,1,0,0,0)の部分列をflip操作するとスコアが5上がるよね、ということに気づいてしまう。そもそも解法が全然間違っていました。。

ということで、スコアの最小値を作るには、1の個数 - 0のの個数が最大となる部分列を求めればよい。また最大値も同じ要領で、0の個数 - 1のの個数が最大となる部分列を求めればよい。

これで、実装後提出したら、やっとこさACが取れました。

73分29秒の4ペナという、だいぶ微妙なタイムですが、とりあえず2完を確保。なんとか爆死を免れたかというところです。

C問題

C - Distinct Numbers

順位表をみると、AC数が300行かないぐらいの問題だったので、だいぶ諦めモードというところではありましたが、とりあえず考えてみることに。

とはいうものの、いろいろなケースを考えてみるも、最善の戦略が何になるのか、どの要素が勝敗に絡むのかというところが全く見当がつかず。

このまま考えても時間切れになるだけというところで、とりあえず嘘解法でもよいから投げてみることに。数列Aをとりあえずソートして、隣同士の差分を求めることで、次に選ぶことができる数の種類数を求めてみる。この種類数の偶奇で先手後手どちらが勝ちかを決めてみることに。

で、これで通る程世の中は甘くないようで、WA×6を喰らってあえなく終了。これで時間切れとなりましたとさ。

とはいえ、嘘解法でも、AC×36は取れているので、惜しいところは行っていたのかなーという印象です。

D問題

D - Prefix XORs

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

E問題

E - Bakery

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

F問題

F - Overlaps

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

これまでの実績

これで、直近2連勝!なんとか連敗で減らした分の半値以上戻しに成功しました。

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

総括

今回のA,B問題は、もう少しよく考えればペナ無しで解けたかというところ。最近考察が雑になりがちな傾向があるようなので、正確性を重視して考察できるようにしないといけないですね。

今回一応、比較的良いパフォーマンスが出たものの、できれば水色を安定して出したいところなので、引き続き精進していこうと思います。

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