AtCoder Beginner Contest 189 参加記

2021/1/23に開催されたAtCoder Beginner Contest 189に参加しました。

atcoder.jp

前回は、なんと灰色diffの問題を落としてしまい痛恨の茶色転落。

今回は、とりあえず緑に復帰できるようにと言う気持ちで臨みました。

今回の結果

そんなこんなで奮闘した結果、今回も安定の4完で終了です。

ABC189結果

ABC189結果

が、、パフォーマンスの方は上々の結果で、なんとか緑に復帰することができました!

振り返り

C問題でやや手間取りまして、結局E問題を解く時間もありませんでした。

ABC189提出結果

ABC189提出結果

A問題

A - Slot

 C_1 = C_2且つC_1 = C_3かどうかを判定するだけ。問題なくAC。

B問題

B - Alcoholic

 お酒の量がV_imlで、アルコール度数がP_i%の時、アルコールが何ml入っているかを計算して合算する問題。

そのまま計算すると、小数以下の値の計算で誤差が出ておかしくなる可能性もあるので、全て整数演算で済ますように工夫すればよい。

ということで、アルコール摂取量の上限Xを100倍し、V_i \times P_iの合計値と比較すれば問題ない。こちらも問題なくAC。

C問題

C - Mandarin Orange

 区間の最小値を求めるということで、セグ木使わせる系の問題!?と少し戸惑ってしまった。ここ最近のABCコンテストのCにしては、少し難易度が高めなんじゃね?

とか思いつつ、とりあえず使い慣れないセグ木を使ってみたら、これがサンプルすら通りません。

デバッグしながら、色々悩んでみたが、どうもセグ木の使い方が間違ってたということが判明。間違いを修正してなんとかサンプルが通る実装を完成させました。

んで、意気揚々と提出してみたら、これがなんとTLE。。。

それから、ループの回し方をなんとか小手先で修正してみたらなんとか1sec超えの結果ではありましたが、なんとかACを取ることができました。やれやれ。。

コンテスト後に改めて見直してみると、実はセグ木使わなくてもOKだったり、普通に工夫してループ回せば200ms程度でACできてたりと、全然考察がイケてないことが判明しましたー。まだ精進が足りないねえ。

D問題

D - Logical Expression

 見た目結構むずそうだったので、気後れしたが、なんとか解法を思いつきました。

 dp[i][j]=i回目の演算が行われた時にTRUE(j=1)、またはFALSE(j=0)になる場合の数として、漸化式を以下のようにしたDPを考えました。

S_i = ANDのとき

  • dp[i][1]=dp[i-1][1]
  • dp[i][0]=2^{i+1} - dp[i-1][1]

S_i = ORのとき

  • dp[i][0]=dp[i-1][0]
  • dp[i][1]=2^{i+1} - dp[i-1][0]

これで最後に、dp[N][1]を出力すればOK。

一瞬、今回Dはムリかもなどと考えていたが、なんとか4完は確保できました。

E問題 

E - Rotate and Flip

DでACを取ったのが、残り時間あと20分と少しというところ。

順位表では明らかにEの方がAC数が多かったので、とりあえず残り時間はE問題に賭けることにしました。

 しかしながら、問題を見てみると実装が重そうな問題で、TLEを避けようと思ったら、クエリをソートするとかしないと難しそうな雰囲気。実装をあれこれ悩んでるうちに、時間切れとなりました。

F問題

F - Sugoroku2

問題文すら見てません。

これまでの実績

再度の緑復帰、しかしながら少しでも気を緩めてしまえば再度茶色転落の危険があるので、まだまだ喜んではいられません。

コンテスト実績

コンテスト実績

総括

今回のABCや最近のARCなどを見ると、今年は少しコンテストの難易度が上がっているような気がします。参加者のレベルが上がるのに合わせて問題も難しくしているような印象ですが、だとすると、自分もレベルを上げ続けていかないと現状のレートを維持するのも難しいという事になるのでしょうか。

ま、いろいろ考えるところはありますが、とりあえずは日々精進していくしかないというところでしょう。

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