AtCoder Regular Contest 107 参加記

2020/10/31に開催されたAtCoder Regular Contest 107に参加しました。

atcoder.jp

ARCは過去3回参加して全て2完終了なので、そろそろ3完以上を達成したいなーという気持ちで臨みました。

今回の結果

で、結局今回も2完で終了となりました。

ARC107結果

ARC107結果

今回は、手応えからしてレートマイナスもありうるかなーという感じでしたが、なんとかHighest更新です。

振り返り

Bで時間かけすぎ。C以降は歯がたたずでした。

ARC107提出結果

ARC107提出結果

A問題

A - Simple Math

\sum_{a=1}^A\sum_{b=1}^B\sum_{c=1}^C abcを計算する問題。

式通りに愚直に計算するとTLEするやつだが、式変形すれば、

\sum_{a=1}^Aa \times\sum_{b=1}^Bb \times \sum_{c=1}^Ccとなるので、簡単な等差数列の和を求める公式を当てはめればOK。

あとはmodの計算を実装してAC。 

B問題

B - Quadruple

整数N,Kが与えられた時、以下の条件を満たすa,b,c,dの組の個数を求める問題。

  • 1 \le a,b,c,d \le N
  • a + b - c - d = K

2番目の式を(a + b) - (c + d) = Kと変形する。

また、f(x) := a + b = x且つ1 \le a,b \le Nを満たす整数a,bの組の個数と定義すると、求める答えは、

\sum_{x=K+2}^{2N} (f(x) \times f(x - K))

となる。ということで、あとはf(x)の関数の実装さえ適切に行えばOKのはずだったが、効率悪い実装をしたため、一度TLEを喰らってしまいました。

再度実装を見直してなんとかAC。

 

と、なんか簡単そうに書いてるが、本番では大分考察と実装に苦労しており、開始から60分経っての2完達成でした。

C問題

C - Shuffle Permutation

で、C以降は全然わからず。

 

まー問題の意味はなんとなくわかるが、どーやったら数え上げれらるん?という感じで思考がまとまらずでした。

D問題

D - Number of Multisets

1を最大限使えるだけ使った時の場合の数を数え上げ、あとは1を使う個数を1つずつ減らしていく感じのDPかという思いつきはありましたが、如何せん実装できずで諦め。

E問題

E - Mex Mat

問題すら見れてません。

F問題

F - Sum of Abs

Eと同じです。

これまでの実績

一応6連続でレート上昇ですが、そろそろ天井が見えてきた感があります。実力の方が上がっていかないと、これ以上は厳しいという印象です。

コンテスト実績

コンテスト実績

総括

ARCの参加は4回目ですが、全てABの2完止まりなのはいただけません。いつかは3完以上できるように直近のARCのC問題を中心に精進していきたいと思います。

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