イバコの生存記録

いまは競プロ(AtCoder)記事がメインです。

61. AtCoder参加記録(AtCoder Beginner Contest 238)

現状です。5回参加でレート 596 です。ここから正しいレートが出るのかと思っていましたが、9回参加しないとダメみたいです。

 

f:id:ibako_piyo:20220205230742p:plain

f:id:ibako_piyo:20220205230847p:plain

 

今回はパフォーマンス 900 でした。ABCを通して、DでWA、EFGExは未解答です。

 

f:id:ibako_piyo:20220205231026p:plain

 

各問題の感想です。

A

これA問題か…?と疑う難易度でした。先週の件があったので何回かリロードしてました。

「やるだけ」では  n が大きすぎるので WA なり TLE なりが発生します。数学的に何らかの数以上から常に成り立つことを示せそうだとは思いましたが、もう少しプログラム的に工夫して通しました。

 n^2 は long の範囲内に収まるので、これは予め計算します。 
その後、 2^n を「順番に 2 を掛けていく」ループで処理しつつ、 n^2 より大きくなった時点で Yes を出力して終了します。

 2^n \gt n^2 となる最小の  n は、まぁ早くに出てくるだろうと予想はつくのでこれで通ります。

 

B

これもBにしては難しいです。

「切込み入れた角度リスト」を用意します。最初に 0 を突っ込みます。「回転」操作でリストにある数字を全て、回転角だけプラスします(ただし 360 の Mod を取ります)。「切込み」操作で 0 を突っ込みます。

これで切込みリストが出来たので、数字の小さい順に並べて、順番に次の要素との差を見て最大角を求めます。

ただし、これだけでは不十分で、リスト内最大の角と最小の角に対して特別な計算が必要です。たとえば、350度と10度に対して入った切込みの間の角は、20度になります。

 

C

やっぱりCにしては難しいです。

桁数ごとに考える問題なので、それで実験してみます。

1~9 は9個あり、10~99 は90個あり、100~999 は900個あります。それぞれの  f(x) は、1~9 で1~9、10~99 で1~90、100~999 で1~900 です。

ここから、ある  k 桁の数字を全部採用するなら、 \sum_1^n k の公式より  \frac{1}{2} \cdot 9 \cdot 10^{k-1} (9 \cdot 10^{k-1} + 1) が加算されます。

ただし、今回は mod を取る問題なので単純な割り算が出来ず、どちらが偶数になるかで場合分けしてやる必要があります。1桁の場合のみ例外的な処理になります。

これを、 N の桁数を  k として  (k-1) 桁までやってあげた後、 k 桁目については  N - 10^{k-1} + 1 までの和を求めてあげればOKです。

いや難しいっすね。

 

D

普通にやると計算量的に無理です。

ビットごとに見ていけば良さそう(最大512bit)とは気付いたのですが、何かバグらせてテストケースが2つ通りませんでした。悲しい。

 

E, F, G, Ex

見る余裕がありませんでした。

 

 

今回の問題セットは数学がテーマだったと思いますが、それにしても難しかったと思います。このレベルでパフォーマンス900出ているので…。

4完安定するようになりたいですね。