AtCoder Beginner Contest 238 参加記録
タグ:
AtCoder Beginner Contest 238に参加しました。
結果はAC2完でした。終了直後にB問題解けたの悔しすぎる…。
レーティングは273→312まで上がりました。とりあえず茶色になるのが直近の目標です。
A - Exponential or Quadratic
問題文の通りに書くだけです。
n = int(input())
if (2**n > n**2):
print("Yes")
else:
print("No")
B - Pizza
「ピザを時計回りに回転させて切り込みを入れる」=「ピザを固定したまま包丁を反時計周りに移動させて切り込みを入れる」だと気付くのが鍵！あとは最初の切り込みから何度の位置に切り込みが入るか調べて、切り込み間の角度の最大値を計算すればOK。
これに気付けたのは良いものの時間ギリギリで結局正解できず…。
悔しい！
n = int(input())
an = map(int, input().split())
s = [0, 360]
current = 0
for a in an:
current = (current + a) % 360
s.append(current)
s.sort()
ans = 0
for i in range(len(s)-1):
ans = max(ans, s[i+1] - s[i])
print(ans)
C - digitnum
愚直に計算したら当然TLEになりそうなので、うまく計算する方法を考えます。こういう系統の問題は具体的な数値を入れてパターンを探せば良さげ。
実際にやってみます。まずnが9のとき、
f(1)=1, f(2)=2, … ,f(9)=9となり、
f(1)+f(2)+…+f(9)は初項1、公差1、項数9の等差数列の和になるから、
f(1)+f(2)+…+f(9)=9(9+1)/2
続いてnが99の数のとき、
f(10)=1, f(11)=2, … ,f(99)=90となり、
f(10)+f(20)+…+f(99)は初項1、公差1、項数90の等差数列の和になるから、
f(10)+f(20)+…+f(99)=90(90+1)/2
一般化できそうな部分が出てきました。
f(1)+f(2)+…+f(n)をnの桁数に応じて分割するとうまく計算できそうです。
例えばn=103のときは、
f(1)+f(2)+…+f(103)
={f(1)+f(2)+…+f(9)}+{f(10)+f(20)+…+f(99)}+f(100)+…+f(103)
=9(9+1)/2+90(90+1)/2+f(100)+…+f(103)
このように分割できます。
太字の部分はnの桁数に応じたループで、残りの部分は等差数列の和の公式を使って求められます。
これを踏まえてコードを書くと以下のようになります。
n = int(input())
digit = len(str(n))
sum = 0
for i in range(1, digit):
m = 9*10**(i-1)
sum += m*(m+1)/2
res = (n-10**(digit-1)+1)*(n-10**(digit-1)+2)/2
print((sum+res) % 998244353)
やったぜ！！！！！！と思って意気揚々とテストするもnの桁が小さいうちは正解になりますが、nがクソでか整数になるとなぜか不正解に…
色々調べてこの記事を見つけました。
Python3で巨大な浮動小数計算の結果が変だったので理由を調べてみた
float型でクソでか整数を扱うと誤差が生まれてしまう、とのこと。上記のコードの中に2で割っている箇所がありますが、この計算結果がfloatになってしまっていたので誤差が生じていたようです。「/」の箇所を「//」へ変更し、計算結果がfloatになるのを防いでおきます。
n = int(input())
digit = len(str(n))
sum = 0
for i in range(1, digit):
m = 9*10**(i-1)
sum += m*(m+1)//2
res = (n-10**(digit-1)+1)*(n-10**(digit-1)+2)//2
print((sum+res) % 998244353)
これで正解になりました。
D~Ex
問題文すら見ていないので省略。
感想
意外と茶色イケるんじゃね…？と思いはじめた今日この頃。時間はかかったものの、今回のC問題を解けたのは自信になりました。
引き続き精進していきます。