セキュリティ・キャンプ2021 L-IIトラック 応募課題2

kadai2-1.py

#!/bin/python3
import numpy as np

n=1024

def polymod(a):
    # 分かりやすさのため a = a_{2n-1} X^{2n-1} + a_{2n-2} X^{2n-2} + ... + a_1 X + a_0 とみることにする（問題文と逆に係数を並べる）。
    # このaに対してナイーブに割り算を実行する。
    # すなわち、除算を実行して a = (X^n + 1)Q + R の形に書けたとき
    # Q = a_{2n-1} X^{n-1} + a_{2n-2} X^{n-2} + ... a_{n+1} X + a_n
    # R = ( a_{n-1} X^{n-1} + a_{n-2} X^{n-2} + ... + a_0 ) - ( a_{2n-1} X^{n-1} + a_{2n-2} X^{n-2} + ... + a_n )
    # とできることがわかる。
    # 具体的なQとRを求める考え方の手順を以下に示す。
    # 商はn-1次であり、割る多項式 X^n + 1 の係数で0でないのはn次と0次の項だけであることを考えれば、aを割る多項式が X^n + 1 のとき商を計算する上で考慮が必要なのはn次の項のみである。
    # すなわち、商の係数を最高次から決定していくが、0次まで決定して商が確定するまでの間に、割る多項式 X^n + 1 の0次の項である1の部分は商の係数の決定に全く影響を与えない。
    # ゆえに、商としてはaの2n-1次からn次までの項をX^nで割ったものを持ってこればよいことがわかる。
    # また、余りもn-1次であり、余りにはaのX^{n-1}次から0次までの項に対してQを引いたものを持ってこればよいことがわかる。
    # 実装としては係数の配列aの0番目からn-1番目までの部分をn番目から2n-1番目の部分で引けばよいので以下のようになる。
    # 計算量はスライスの配列長に比例し、O(n)であることがわかる。
    return a[:n]-a[n:]

a = np.array([int(input()) for i in range(2*n)],dtype=np.int64)
res = polymod(a)
for i in res:
    print(i)

kadai2-2.py

#!/bin/python3
import numpy as np

l = 4

def decomposition(a):
    # 基数16を宣言しておく。
    p = 16
    # 答えを格納する配列をresとする。
    res = np.zeros(l, dtype=np.int8)
    for i in range(l):
        # 割り算を行う。aをpで割った余りをrとし、aをpで割った商を再びaとする。
        # ここで、この割り算によって余りrを得るという操作は、i回目の割り算が、はじめに与えられたaのi桁目のp進数における値r（を10進数に直したもの）を持ってくる操作とみることができる。
        r = a % p
        a = a // p
        # 余りrは[-8,8)の範囲にあってほしいので、rが8以上となった場合はrから16を引くことでその範囲に納める。
        # その場合、この余りrに対応する商の値aが1大きくなるので1を足す。
        if r > 7:
            r -= p
            a += 1
        # 答えの配列に値を格納する。
        res[i] = r
    return res


# 元のコードでは入力の受け取りの際にエラーが発生した（AttributeError: module 'numpy' has no attribute 'int8_t'）。
# 問題文によれば入力はuint16_tとなっていたため、numpyでそれに対応しているnp.uint16に修正を行った。
a = np.uint16(input())
res = decomposition(a)
for i in res:
    print(i)