スポンサーリンク

AtCoder Beginner Contest 238の感想

Monoxer Programming Contest 2022(AtCoder Beginner Contest 238) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

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')



 

コメント

タイトルとURLをコピーしました