Atcoder 灰diff埋め ABC-like004~ABC-like006 振り返り
ARC-like005 B - Contests【AC】
1問目が3つ，2問目が5つ，3問目が2つ存在したとき開催できるコンテストの最大値は2回です．なぜなら，異なるコンテストの間で問題の重複があってはいけないので，3つコンテストを開催しようとすると3問目が重複してしまうためです．つまり，この問題は1問目となる問題の個数，2問目となる問題の個数，3問目となる問題の個数をそれぞれ数え，その最小値が答えとなります．
問題の個数を数えるにはfor文を使って全ての問題に対し，if文を使って問題の条件分岐をさせます．
4行目のa, b, c = 0, 0, 0はpythonのアンパック機能を用いた書き方になります．pythonはこのように並べることによって同時に変数を入れる事ができます．
この書き方は他にも応用が効きます．例えばaとbの値を入れ替える処理を考えます．1つはc = bというようにbの値をcに入れておき，b = a a = cとするやり方があります．しかしこれではaとbの値を入れ替えるだけで3行も使ってしまいます．そこでアンパック機能を使います．a, b = b, aと書くのです．こうすることで，1行で処理を完了することができ，シンプルで見やすいコードにする事ができます．
N = int(input()) A, B = map(int, input().split()) P = [int(i) for i in input().split()] a, b, c = 0, 0, 0 for p in P: if p <= A: a += 1 elif p <= B: b += 1 else: c += 1 print(min(a, b, c))
PyTorch実戦入門 第3章 演習問題 解答まとめ
1
import torch a = torch.tensor(list(range(9))) print(a.size()) print(a.storage_offset()) print(a.stride()) >>torch.Size([9]) >>0 >>(1,)
a
.view()を使うと，
b = a.view(3, 3) print(b) >>tensor([[0, 1, 2], [3, 4, 5], [6, 7, 8]])
となります．3*3の行列に変形されたことが分かります．同じストレージを共有しているかどうかを確認するにはid()関数を使います．これは，Pythonが持っている関数で，オブジェクトのidを返します．このidが等しければ同じストレージを共有していることになります．
print(id(a.storage()) == id(b.storage())) >> True
同じストレージを共有しているため，このようなことが起こります．
import torch a = torch.tensor(list(range(9))) b = a.view(3, 3) a[0] = 10 print(a) print(b) >>tensor([10, 1, 2, 3, 4, 5, 6, 7, 8]) >>tensor([[10, 1, 2], [ 3, 4, 5], [ 6, 7, 8]])
a[0]を10に書き換えたことにより，aが[10, 1, 2, 3, 4, 5, 6, 7, 8]となっているのはいいのですが，bも先頭が10に書き換わってしまっています．同じストレージを使っているためです．値を書き換える際は気をつける必要があります．
b
c = b[1:, 1:] print(c) print(c.size()) print(c.storage_offset()) print(c.stride()) >>tensor([[4, 5], [7, 8]]) >>torch.Size([2, 2]) >>4 >>(3, 1)
2
a
a = torch.tensor(list(range(9))) print(torch.cos(a)) >>tensor([ 1.0000, 0.5403, -0.4161, -0.9900, -0.6536, 0.2837, 0.9602, 0.7539, -0.1455])
関数をaに適用してもエラーが出ません……公式の回答によるとaをfloat型にしないと動かないようですがそうしなくても動きます……バージョンが変わったことにより動くようになったのでしょうか……？
b
エラーがでないため省略
Atcoder 灰diff埋め ABC-like001~ABC-like003 振り返り
ARC-like001 B - Different Distribution【AC】
一見難しそうなパズルのように見えて，当たり前の事実を積み重ねるだけで答えが求まる問題でした．
クラスでテストを行い，b点を取った人が上位a番目という情報がN個あった時，クラスの人数としてあり得る最大値を求める問題です．
まず，a番目という情報があった時点でクラスはa人以上いる事が確定します．クラスに5人しか居ないのに上位6番目となることは有り得ません．上位6番目の人がいるなら必ずクラスは6人以上です．よって答えはN個の情報の中でのaの最大値以上であることは確定します．
a'=max(a)としたとき，答えはa'以上となります．a'に対応するbをb'とします．a'は与えられた情報の中で最も悪い順位であるので，b'は与えられた情報の中で最も悪い点数です．b'より悪い点数の人がいると考えてもa番目の情報と矛盾することはありません．b'より悪い点数の人はa'より大きい値になるからです．クラスの人数の最大値を求めたいので，b'-1, b'-2, ..., 1, 0点のパターンが最大です．これはb'個になります．よって答えはa'+b'になります．
N = int(input()) ans = 0 A = 0 for _ in range(N): a, b = map(int, input().split()) if a > A: ans = a+b A = a print(ans)
Atcoder ABC256 振り返り
B - Batters【AC】
マスをAAで表し，そのマスにコマが置かれていることを1，置かれていないことを0として表します．AA[j]が1ならAA[j]を0にしてAA[j+A[i]]を1にします．AA[j+A[i]]が4以上ならPに＋1します．これは，マスを決められた分だけ前に動かす操作をしています．これを繰り返す事で求まります．
N = int(input()) A = [int(i) for i in input().split()] P = 0 AA = [0 for i in range(4)] for i in range(N): AA[0] = 1 for j in range(3, -1, -1): if AA[j] == 1: AA[j] = 0 if j + A[i] > 3: P += 1 else: AA[j+A[i]] = 1 print(P)
C - Filling 3x3 array【AC】
ぱっと見どう解けば良いか分からずこの問題を飛ばしましたが，制約が30以下であることをヒントに考えます．これだけ制約が小さいと，全探索をしても間に合いそうです．
各行に対して, h1, h2, h3のルールを守るような数字の並びを全て列挙します．例えば，h1=3なら[1,1,1]のみですし，h1=4なら[1,1,2],[1,2,1],[2,1,1]です．これの全列挙のやり方は1<=i<=30, 1<=j<=30でループさせ, i+jがh1未満なら，[i, j, h1-i-j]とすれば良いです．
h1, h2, h3について各パターンの候補を全て列挙したら，それらを全て組み合わせ，w1, w2, w3を満たしていれば成立することになります．
num = [int(i) for i in input().split()] h1_list = [] h2_list = [] h3_list = [] for i in range(1, 30): for j in range(1, 30): if i + j < num[0]: h1_list.append([i, j, num[0]-i-j]) for i in range(1, 30): for j in range(1, 30): if i + j < num[1]: h2_list.append([i, j, num[1]-i-j]) for i in range(1, 30): for j in range(1, 30): if i + j < num[2]: h3_list.append([i, j, num[2]-i-j]) ans = 0 for h1 in h1_list: for h2 in h2_list: for h3 in h3_list: if h1[0]+h2[0]+h3[0] == num[3] and h1[1]+h2[1]+h3[1] == num[4] and h1[2]+h2[2]+h3[2] == num[5]: ans += 1 print(ans)
D - Union of Interval【AC】
開集合はソートしても答えは変わらない事に注意します．
どのような状態が成立したら開集合を合成できるか考えます．下の図で，上側の開集合を[L1, R1)下側の開集合を[L2, R2)とします．左のパターンでは2つの開集合を1つに合成できますが，右のパターンでは合成できません．
左右の違いは，L2の位置です．L1
import bisect N = int(input()) L = set() lr_dic = {} for _ in range(N): l, r = map(int, input().split()) L.add(l) lr_dic.setdefault(l, 0) lr_dic[l] = max(lr_dic[l], r) L = sorted(list(L)) L.append(10**6) lr_dic[10**6] = 10**7 ans = set() i = 1 now = L[0] if N == 1: print(now, lr_dic[now]) else: while True: if now < L[i] <= lr_dic[now]: lr_dic[now] = max(lr_dic[now], lr_dic[L[i]]) else: print(now, lr_dic[now]) now = L[i] i += 1 if i == len(L)-1 : print(now, lr_dic[now]) break
シェル・ワンライナー160本ノック week2 1.3.f~問題4
1.3.f
xargs
xargsはコマンドに引数を渡し実行するはたらきをします．以前は出力を横に表示させるはたらきをしていましたが，これはxargsの引数が指定されなかった場合はechoを実行する仕様を使った物です．
1.3.g
bash
bashをコマンドとして使う事でワンライナー上の出力をコマンドとして実行する事が出来ます．awkを使ってmkdir ...という文字列を出力します．
$ seq 4 | awk '{print "mkdir "($1%2 ? "odd_" : "even_")$1 }' mkdir odd_1 mkdir even_2 mkdir odd_3 mdkir even_4
これをコマンドとして実行させたいときはこれにbashを付けます．
$ seq 4 | awk '{print "mkdir "($1%2 ? "odd_" : "even_")$1 }' | bash $ ls -d odd_* even_* even_2 even_4 odd_1 odd_3
問題1
ファイルに記述された文字列から.exeとかかれた行のみを抜き出す問題でした．grepに検索する文字列を正規表現で表現します．ファイルの指定は末尾に記述します．（これが一番分からなかった）
$ grep '\.exe$' files.txt test.exe 画面仕様書.xls.exe
別解と言うほどでもありませんが，files.txtの検索から一括で行う方法を載せます．grep files.txtの出力をxargsで引数として受け取り，grep '\.exe$'とすれば良いです．
$ find shellgei160/ | grep files | xargs grep '\.exe$' test.exe 画面仕様書.xls.exe
また，問題2で習う$(コマンド)というコマンド置換を使えばこう書けます．
$ find shellgei160/ | grep '\.exe$' $(grep files) test.exe 画面仕様書.xls.exe
Atcoder 灰diff埋め AGC025~AGC054 振り返り
AGCも全て埋め終わって100%!と思いきやまだ-like系の問題が多く残ってました……
AGC037 A - Dividing a String【AC】
解説ではDPを使うパターンと漸化式を使うパターンが紹介されていましたが，ここではそのどちらでもない方法で解きます．（と言っても考え方は漸化式のパータンとほぼ同じですが）
S1S2...Skに文字列を分割し，Kの最大値を求めます．ここでSiの長さが3以上になることはありません．なぜなら，len(Si)=1ならlen(Si+1)=2の文字列を用意すれば必ずSi=Si+1とはならず，len(Si)=2ならばlen(Si+1)=1の文字列を用意すれば必ずSi=Si+1とはならないからです．分割数Kを大きくしたいのでlen(Si)は小さければ小さい方が良く，len(Si)>=3となるようなSiは考える必要がありません．
Sのi文字目をsiとします．si != si+1ならば，そのままSi, Si+1とするのが最適です．si = si+1ならば，Siの長さに合わせてSi+1を決定します．len(Si)=1ならば，si+1とsi+2を合わせてSi+1とします．これは長さが異なるので必ずSi != Si+1となります．同様にlen(Si)=2ならsi+1をSi+1とします．
以上の処理をSの末尾まで続ければ分割数の最大値Kが求まります．
S = list(input()) lis = [S[-1]] S.pop() while S: if S[-1] == lis[-1]: if len(S) == 1: lis[-1] += S.pop() else: s = S.pop() s += S.pop() lis.append(s) else: lis.append(S.pop()) print(len(lis))
統計学入門 第6章 練習問題 前半 解答まとめ
6.1
統計学入門 第6章 確率分布 離散編 まとめ - hirohirohirohirosのブログ
ここで証明済みである.
6.2
4人までなら不足しない．5人以上の救急患者が来たときに不足する．ポアソン分布は
\begin{align}
f(x) = \frac{e^{-λ}λ^x}{x!}
\end{align}
であり，λ=2.5であるため答えは1-(f(0)+f(1)+f(2)+f(3)+f(4))となる．答えをpythonで求めておく．eはmathモジュールのmath.eで，階乗は同様にmathモジュールのmath.factorialで求められる．
答えは0.1088である．
6.3
本書では幾何分布の一般化として負の二項分布が導出されていたが，名前にもあるように二項分布から負の二項分布を導出してみようと思う．
二項分布はSがx回，Fがn-x回起きる確率を
\begin{align}
f(x) = {}_nC_x p^x(1-p)^{n-x}
\end{align}
としていた．負の二項分布はSがk回起こるまでにFがx回出る確率である．
\begin{align}
f(x) = {}_{k+x-1}C_x p^k(1-p)^x
\end{align}
6.4
i)
表がn-1回裏が1回出るパターンと表が1回裏がn-1回出るパターンがあるので
\begin{align}
P = np^{n-1}q + npq^{n-1}
\end{align}
ii)
i)の試行を繰り返し，始めて確率Pを引いたときの試行回数は幾何分布に従うので，
\begin{align}
f(x) = P(1-P)^{x-1}
\end{align}
となる．幾何分布の期待値はなので，この期待値は
\begin{align}
E(x) = \frac{1}{np^{n-1}q + npq^{n-1}}
\end{align}
6.5
を確率密度関数にするにはこの式を積分したときに1になるようにすれば良いので，
\begin{align}
\int_{-\infty}^{\infty} f(x) &= \int_{-1}^1 c(1-x^2) \\
&= c[x-\frac{x^3}{3}]_{-1}^1 \\
&= c\frac{4}{3} = 1 \\
c &= \frac{3}{4}
\end{align}
期待値はであるので，
\begin{align}
E(x) &= \int_{-\infty}^{\infty}xf(x) \\
&= \int_{-1}^1 \frac{3}{4}x(1-x^2) \\
&= \frac{3}{4} (\int_{-1}^1 x - \int_{-1}^1 x^3) \\
&= \frac{3}{4} ([\frac{x^2}{2}]_{-1}^1 - [\frac{x^4}{4}]_{-1}^1) \\
&= 0
\end{align}
分散はなので，(計算式は一部略す)
\begin{align}
V(x) &= \int_{-\infty}^{\infty}(x-E(x))^2f(x) \\
&= \int_{-1}^1 x^2\frac{3}{4}x(1-x^2) \\
&= \frac{1}{5}
\end{align}
歪度はであるので，E(x) = μとすると，
\begin{align}
E(x^3) &= \int_{-1}^1 x^3\frac{3}{4}(1-x^2) \\
&= 0 \\
α_3 &= \frac{E(x - \mu)^3}{σ^3} \frac{1}{σ^3} \\
&= E(x^3) - 3\mu E(x^2) + 2\mu^3 \frac{1}{σ^3}\\
&= 0
\end{align}
尖度はから3引いた値であるので，
\begin{align}
E(x^4) &= \int_{-1}^1 x^4\frac{3}{4}x(1-x^2) \\
&= \frac{3}{4}(\frac{2}{5}-\frac{2}{7}) \\
&= \frac{3}{35}
α_4 &= \frac{E(x-E(x))^4}{σ^4} \frac{1}{σ^4}\\
&= E(x^4) -4\mu E(x^3) + 6\mu^2E(x^2) - 3\mu^4 \frac{1}{σ^4} \\
&= \frac{3}{35} \frac{1}{\frac{1}{25}} \\
&= \frac{15}{7}
\end{align}
尖度はである．
