2020-07-26 課題

メモ：先に進む前に録画してあるか確認しよう

自分用メモ

Matplotlib

\begin{align} f(x) = \frac{4}{\pi} \left( \sin x + \frac{1}{3} \sin 3 x + \frac{1}{5} \sin 5 x + \cdots \right) \end{align}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-3, 3, 1001)
y = (4 / np.pi) * (np.sin(x) + np.sin(3*x) / 3 + np.sin(5*x) / 5 + np.sin(7*x) / 7 + np.sin(9*x) / 9)
y1 = np.ones(len(x))
y2 = -1 * np.ones(len(x))

plt.plot(x, y, label="finite fourier")
plt.plot(x, y1, label="y=1")
plt.plot(x, y2, label="y=-1")

plt.grid()
plt.legend()
#plt.axes().set_aspect('equal', 'datalim') # アスペクト比を合わせる
plt.show()

TeX の記録

\begin{align} \lambda_k = 4 \pi \left(\frac{\Gamma (\frac{m}{2} + 1)}{\binom{m}{p} \mathrm{vol}(M)} \right) k^{m/2} + o (k^{m/2}). \end{align}

競プロ、AtCoder

ABC085C - Otoshidama

日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。 青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が $N$ 枚入っていて、合計で $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。 N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「 10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

入力・出力例 1

1
2
3
9 45000

4 0 5

お年玉袋に 10000 円札 4 枚と 1000 円札 5 枚が入っていれば、合計枚数が 9 枚、合計金額が 45000 円になります。 5000 円札 9 枚という可能性も考えられるため、0 9 0 も正しい出力です。

入出力例 2

不適格な場合の出力チェックにあたる。

1
2
3
20 196000

-1 -1 -1

合計枚数が 20 枚の場合、すべてが 10000 円札であれば合計金額は 200000 円になり、そうでなければ 195000 円以下になるため、196000 円という合計金額はありえません。

入出力例 4

変なアルゴリズムを組むと指定計算時間内に終わらない。

1
2
3
2000 20000000

2000 0 0

基本方針

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def solve(N, Y):
    for x in range(N+1):
        for y in range(N-x+1):
            z = N-x-y # z のループはせずにこれで固定
            if 0 <= z <= 2000 and 10000*x+5000*y+1000*z == Y:
                return "%s %s %s" % (x, y, z)
                exit() # ヒットしたので処理終了
    # ここまで来たら不適格だったと判断
    return "-1 -1 -1"

print(solve(9, 45000)) # 4 0 5
print(solve(20, 196000)) # -1 -1 -1
print(solve(1000, 1234000)) # 14 27 959 他にもありうるはず
print(solve(2000, 20000000)) # 2000 0 0

1
2
3
4
0 9 0
-1 -1 -1
2 54 944
2000 0 0

ABC049C - 白昼夢

英小文字からなる文字列 $S$ が与えられます。 $T$ が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで $S=T$ とすることができるか判定してください。

$T$ の末尾に dream dreamer erase eraser のいずれかを追加する。

例

1
2
3
erasedream

YES

erase dream の順で T の末尾に追加することで S = T とすることができます。

1
2
3
dreameraser

YES

1
2
3
dreamerer

NO

1
2
3
4
5
6
7
8
9
import re
#S = input()
def solve(S):
    # 正規表現を使って特定 4 文字列の繰り返しだけかどうかを判定する
    return "YES" if re.match("^(dream|dreamer|erase|eraser)+$", S) else "NO"

print(solve("erasedream")) # YES
print(solve("dreameraser")) # YES
print(solve("dreamerer")) # NO

1
2
3
YES
YES
NO

メモ

文字列 S を dream, dreamer, erase, eraser に分解していくことを考えます。先頭から分解していこうとす ると、例えば dreamer まで読んだとき、dream で切るべきなのか、dreamer で切るべきなのか判定するこ とができません。(dreameraser は dream eraser と切らなければならないので、dreamer まで読んだときに dream で切らなければいけない場合が存在することが分かります) 逆に、後ろから読んでみましょう。4 つの単語を後ろから読むと、それぞれ maerd, remaerd, esare, resare となります。この 4 つの文字列は、ある文字列が他の文字列の接頭辞 (prefix) になっていないため、後ろか ら読んで当てはまるものが見つかれば即座に分解するしかありません。(参考: 語頭符号) S を最終的に分解す ることができなかった場合 NO を、そうでない場合 YES を出力します。

IT 基礎知識

7 章 ネットワーク

OSI参照モデルとは｜ファイアウォールの種類をわかりやすく解説

セキュリティ

もう 1 つ参考：ネットワーク各レイヤーのセキュリティを強化するには

  • トランスポートモード：パケットのペイロードだけを暗号化し、それにIPヘッダを付けて開いて送信する。

  • トンネルモード：IPヘッダを含めて暗号化されるため、ネットワーク間の安全な接続に用いられる。

  • 「SSL」「TLS」「SSH」といった第4層の通信プロトコルを使用すると、データを暗号化することによって傍受などから守ることが可能になる（「SSL」は「セキュア・ソケッツ・レイヤー」、「TLS」は「トランスポート・レイヤー・セキュリティ」、「SSH」は「セキュア・シェル」の略）。特に機器をリモートで管理するためにネットワーク接続を行う際に十分考慮に入れるべきものである。