モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)に参加しました。
結果
A,B,Cの3問ACでパフォーマンスがXXXでした。
A - Exponential or Quadratic
nが最大でになるのでを実際に計算するのは難しいので愚直に計算して比較するのはTLEになるので無理。
高校の数学でこんな不等式を見たときは両辺対数をとってごにょごにょしてたのを連想して、両辺2の対数をとって式変形した。
最終的にはif文でを評価してYesかNoかを表示させた。
B - Pizza
最終的に何度のところに切れ込みが入っているのかを計算してから、切れ込み間が何度かを計算して最大値を求めて解いた。
回転させて切れ込みを入れるって言うのはつまり、今切った部分から度プラスした角度に切れ込みを入れることなので、まずは360の剰余計算をしながらの累積和を計算して、番目の切込みは0~360度のどこに切れ込みを入れているのかを計算する。
次にN個の切り込みに始点の0度と終点の360度を追加した合計N+2本の切れ目をソートする。
各中心角はx番目の切込みの角度とx+1番目の切込みの角度の差になる。
全部の中心角を計算して最大値を出力すればOK。
C - digitnum
結構難しかった。コンテストの大変の時間を考察と実装とバグ取りで消費した。なんとかAC出来たから良かったけど難しかった。
N <なので愚直に計算するとTLEになるので無理。なので賢く計算する必要がありそう。
問題文を読んでも全く方針が思いつかなかったのでxが小さい範囲でf(x)を手計算してみた。
するとxが1桁のときはf(x)=x、2桁のときはf(x)=x-9、3桁のときはf(x)=x-99、・・・となることに気づいた。
つまりNの桁数をkとすると、f(1)からk-1桁目までのf(x)の和は比較的簡単に計算できそうだし(等比数列の和の公式を利用)、k桁目のf(x)の和は1から(N-9999・・・9)+1までの和になる。
なので後は頑張って実装した。
Nの桁数を求めて(k桁とする)、桁数に応じて1~9までの和、1~90までの和、1~900までの和、・・・をk-1桁まで求める。
次に9がk-1個続いた数字を作ってNから引く(計算結果をN'とする)。最後に1からN'+1までの総和を求めてk-1桁までの和に足す。随時998244353の剰余を計算しながら上記を計算すればAC出来た。