A – Exponential or Quadratic
問題文そのまま実装。
n = int(input())
ans = 2 ** n > n ** 2
print('Yes' if ans else 'No')
B – Pizza
手順通り実装する。
どこに切れ込みが入っているかを把握するための配列を用意する。
円は360度なので、値0で長さ360の配列を用意し、切れ込みが入った場所を1とする。
A度回転させるという作業を、配列をAずらすと解釈する。
K個のスライスを得るにはO(K)かかるが、最悪でもK=360なので充分間に合う。
しかし、配列を定義し直す度にメモリを消費するので、入力が大きかったり制約が厳しい問題だとこのアプローチは厳しいかもしれない。
n = int(input())
a = list(map(int, input().split()))
degree = [0] * 360
degree[0] = 1
for i in a:
degree = degree[-i:] + degree[:-i]
degree[0] = 1切れ込みが入っている場所が分かったので、角度のみを取り出す。
12時方向に切れ込みを入れるという手順があるため、処理をしやすいよう最後に360度を追加する。
angle = []
for i in range(360):
if degree[i] == 1:
angle.append(i)
angle.append(360)最後に、それぞれのなす角度を計算して最大値を出力する。
ans = 0
for i in range(1, len(angle)):
ans = max(ans, angle[i] - angle[i - 1])
print(ans)C – digitnum
1,2,3…9の時、答えに1+2+…+9を加算する。
10,11,12,…99の時、答えに1+2+…+90を加算する。
100,101,102,…999の時、答えに1+2+…+900を加算する。
以上より、ある桁数の整数がX個あるとすると、答えに1+2+…+Xを加算すればいい、という法則が分かる。
1から始まるX個の等差数列の和は X(X+1)/2 になるので、O(1)で計算できる。
x = end - start + 1
val = x * (x + 1) // 2
ans += val最初の値は1,10,100,…から始まるが、最後の値はNが9999…より小さいケースが考えられるため、9, 99, 999,…Nになることに注意する。
keta = len(str(n))
start = 10 ** (keta - 1)
end = min(n, int('9' * keta))等差数列の和を全ての桁で求めて加算すれば答えになる。
ここで、終わりの数を求めるためにnと比較したいが、桁数を変更させる過程でnそのものの値を変更してしまうとループ毎に比較できなくなってしまうため、m=nとして別の値を用意しておく。
また、今回は余りを出力するので、計算途中にmodを取っていく。
PythonのintはC++のlong longと違って上限がないので最後にmodを取るだけでもいいのだが、桁数に応じてメモリ消費量が増えるので途中でmodが取れるところがあれば取っておく。
n = int(input())
mod = 998244353
ans = 0
m = n
while m > 0:
keta = len(str(m))
start = 10 ** (keta - 1)
end = min(n, int('9' * keta))
x = end - start + 1
x %= mod
val = x * (x + 1) // 2
ans += val % mod
m //= 10
ans %= mod
print(ans)
D – AND and SUM
いきなり2進数で考えると分かりにくいので、まずは適当な10進数の足し算123+888=1011を考える。
1の位と10の位は繰り上がる（2+8, 3+8）が、100の位は繰り上がらない(1+8)。
ここで、足し算＝「繰り上がる桁」＋「繰り上がらない桁」に分解できると考える。
1の位を考えてみると、3+8の結果10の位に繰り上がりフラグを立て、1の位が1となる。
10の位は20+80の結果100の位に繰り上がりフラグが経ち、10の位が0になる。
つまり、繰り上がりフラグがある桁の数を加算する、ということに気づく。
「繰り上がらない桁」はシンプルに100+800＝900と計算できる。
以上のことを踏まえて問題に戻る。
2進数の足し算において、1+1は繰り上がって0になり、1+0または0+0は繰り上がらない。
ANDは両方が1の時に1を返す演算なので、x AND y の結果は「足し算すると繰り上がって0になる桁がどこなのか」というフラグを得る事ができる。
繰り上がりがあると次の位に値を加算することになり、2進数の場合は次の位が2倍になるため、 2 ( x AND y)が「繰り上がる桁」の結果になる。
反対に、「繰り上がらない桁」は x XOR y で求めることが出来るため、x+y=(x XOR y)+2(x AND y)という式変形が出来る。
ここで、x+y=sという条件から(x XOR y)+2(x AND y)=sとなり、x AND y = aなので(x XOR y)+2a=sとなる。
以上より、与えられた条件は以下の通り整理できる。
x AND y = a
x XOR y = s - 2a変数がaとsの2種類あるため、連立方程式を解くように解を求める条件が2つ欲しくなる。
x XOR yは繰り上がらない桁を表すため負の値になることはなく、s-2a>=0といえる。
また、「繰り上がる桁」と「繰り上がらない桁」は一致しないため、「繰り上がる桁」AND「繰り上がらない桁」= 0 になる。
この2つの条件を満たすかどうかが答えになる。
t = int(input())
for _ in range(t):
a, s = map(int, input().split())
xor = s - 2 * a
if xor >= 0 and xor & a == 0:
print('Yes')
else:
print('No')
コメント