-
-
Save watagashi0619/45323dee57665210390f890a79c0f849 to your computer and use it in GitHub Desktop.
セキュリティ・キャンプ2021 L-IIトラック 応募課題2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment