AtCoder Regular Contest 116 参加記

2021/3/28に開催されたAtCoder Regular Contest 116に参加しました。

atcoder.jp

昨日のABCでは、2完フィニッシュで少し冷えたので、今回はなんとかレート上昇をという気持ちで臨みました。

今回の結果

で、今回の結果は2完というなんとも微妙な結果に。。

ARC116結果

ARC116結果

現レートに微妙に届かないパフォーマンスとなり、結局レートは微減となりました。

振り返り

Bでだいぶやらかしてしまいました。

ARC116提出結果

ARC116提出結果

A問題

A - Odd vs Even

見た目上、各ケースに対してO(1)程度で解答しなくてはいけなさそうな問題。

 

よって、各ケースで約数を列挙するというようなことはできないため、なんらかの法則性を見つけないといけなさそう。ということで、とりあえず1〜20程度まで手計算で結果を計算してみたところ、奇数の時はOdd、偶数の時は、SameとEvenを繰り返すパターンになってました。

 

よって、4で割り切れる時はEven、奇数の場合はOdd、それ以外はSameとする解法を投げてみると、これが見事にACとなりました。証明もそこそこの状態だったので、早めにこのパターンが見つけられたのは運がよかったのかもしれません。

B問題

B - Products of Min-Max

数列Aをソートすると、i \lt jのとき、A_i \times A_j2^{j - i - 1}回加算されることになる。よって、これを全てのi,jのパターンで計算すればOKかということで実装してみましたが、これが投げてみるとTLE。。

 

小手先の改善でなんとかなるかということで、色々試してみるもののTLEは取れず。どうも2重ループが取れないとTLEも無くならないという結論になる。

 

で、紙上で色々式展開を試してみて、やっと公式解説の通りの計算方法が分かり、2重ループも取れたところで無事ACが取れました。

C問題

C - Multiple Sequences

考察を進めていくと、どうも数列の最後の数字が、1からMまでそれぞれの場合の個数を合算するのでは?というアイデアが思い浮かぶ。

 

が、、結局思い浮かんだのはそこまで。あとの具体的な実装のイメージは思い浮かばずで時間だけが過ぎてゆき、結局時間切れとなりました。

 

んで、解説をみると、二項係数を使ってパターン数を計算するのが想定解だった模様。このアイデアに至ればACも取れたかと思うと残念でなりません。

D問題

D - I Wanna Win The Game

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

E問題

E - Spread of Information

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

F問題

F - Deque Game

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

これまでの実績

今週土日とも、やや冷えで終了。ここにきて、停滞ムードが漂ってきました。。

コンテスト実績

コンテスト実績

総括

3月はほとんど土日がコンテスト対応でした。ここ最近レートは上昇傾向にありましたが、ここにきて停滞ムードになりつつあります。当面は、3月中のコンテストでACできなかった問題を中心に埋めていくことを優先して精進をしていこうと思います。

 

また、次回も頑張ります。